大话数据结构第九章—排序

大话数据结构第九章—排序马上要把大话数据结构这本书看完啦,现在已经对数据结构有了一种系统上的了解,后面的事情就疯狂练习力扣上的编程题目啦,第九章是本书的最后一章,却是以前我学数据结构最先学的部分—–排序。排序网页搜索之后的排序,商品页面的排序,是如何做到的呢?本章将介绍7种排序算法:冒泡排序,简单选择排序,直接插入排序属于简单算法。快速排序,归并排序(mergesort),希尔排序,堆排序属于…

大家好,又见面了,我是你们的朋友全栈君。

马上要把大话数据结构这本书看完啦,现在已经对数据结构有了一种系统上的了解,后面的事情就疯狂练习力扣上的编程题目啦,第九章是本书的最后一章,却是以前我学数据结构最先学的部分—–排序。

排序

网页搜索之后的排序,商品页面的排序,是如何做到的呢?

本章将介绍7种排序算法:

冒泡排序,简单选择排序,直接插入排序属于简单算法。

快速排序,归并排序(merge sort),希尔排序,堆排序属于改进算法。

本文中都是升序排序哦~

 

1.冒泡排序

#bubble sorted
def bubble(array):
    if array == None or len(array) == 0:
        return -1
    for i in range(len(array)-1):
        for j in range(len(array)-1):
            if array[j] > array[j+1]:
                array[j],array[j+1] = array[j+1],array[j]
    return array

时间复杂度:o(n^2)

空间复杂度:o(1)

2.简单选择排序

选择一个数作为最小数,(比如选第一个数作为min),在后续数组中找到最小的数字,并交换位置。若没有,跳到第二个数字,继续进行比较。

代码如下:

 

#selection sort
def select(array):
    if array == None or len(array) == 0:
        return -1
    for i in range(len(array)-1):
        min_index = i
        for j in range(i,len(array)):
            if array[min_index] > array[j]:
                array[min_index],array[j] = array[j],array[min_index]
    return array

 

时间复杂度:o(n^2)

 

空间复杂度:o(1)

3.直接插入排序

插入排序Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

所以insert需要的时间复杂度是o(n),排序(找插入空位)的时间复杂度是o(n),当然如果用binary search找空位的时间复杂度是o(logn),总体的时间复杂度为o(n^2)或者是o(nlogn)。

代码如下:

def insert(list_a):
    for i in range(1,len(list_a)):
        cur = list_a[i]
        k = i

        while cur < list_a[k-1] and k > 0:#寻找空位
           list_a[k] = list_a[k-1]
           k -= 1                        #k记录的当前空位的位置

        list_a[k] = cur#插入

    return list_a

插入排序由于需要挪动空位后的元素,所以需要游标(存储现在正在进行插入的数据元素),需要记录元素下标。寻找插入空位这个代码得记住,感觉可以用在其他地方。

前三种方法都是简单的排序算法,比较他们的最坏的时间复杂度(序列初始为逆序),直接插入算法性能比冒泡和简单选择排序的性能要好。

4 堆排序(heap)

堆是具有下列性质的完全二叉树:

每个节点的值都大于或等于其左右孩子节点的值,叫大顶堆;

每个节点的值都小于或等于其左右孩子节点的值,称为小顶堆。

堆排序算法的步骤:

以大顶堆为例

1 将待排序的序列构成大顶堆。

2 此时最大值就是堆顶的根节点,将其移走(其实是将其与堆数组的末尾元素交换,此时末尾元素就是最大值)

3 将剩余的n-1个序列重新构造成一个堆,这样就可以得到从小到大的排序的有序序列。

要解决的关键问题就是如何建立堆!

建立堆(以实现小顶堆为例)

如何用数组来表示一个完全二叉树?

完全二叉树孩子节点和父亲节点的数组索引关系是酱紫的:

left_node = parent_node * 2 + 1

right_node = parent_node * 2 + 2

parent_node = (child_node – 1) // 2

所以需要实现让完全二叉树的每个节点都小于孩子节点才能建立小顶堆。

将一个随机数组变成小顶堆的python代码如下:

def min_heap(array,i):
    left = i*2+1
    right = i*2+2
    smaller = i
    if left < len(array) and array[left] < array[smaller]:
        smaller = left
    if right < len(array) and array[right] < array[smaller]:
        smaller = right
    if smaller != i:
        array[smaller],array[i] = array[i],array[smaller]
        min_heap(array,smaller)

def build_heap(arr):
    for i in range(len(arr)//2,-1,-1):
        min_heap(arr,i)
    return arr

时间复杂度o(nlogn)。

如果你要往已经生成的小顶堆中加入数据元素:

def push(array,i):
#这里的i是输入序列的最后一位的索引值,也是你要插入的数据。
    parent = (i-1)//2
    large = i
    if parent >= 0 and array[parent] > array[i]:
        large = parent
    if large != i:
        array[large],array[i]= array[i],array[large]
        push(array,large)

时间复杂度都是o(logn)。

python中heapq包,专门完成堆的一些操作。

import heapq

heap = []                  #生成的是小顶堆

heappush(heap,item)

item = heappop(heap)

item = heap[0]

heapify(x) #将list转换为heap

item = heapreplace(heap,item) #先pop再插入item

有了这些可以应用它做一些编程题目:

比如实现堆排序,寻找序列中的最小k项,合并k个有序序列等。

5 归并排序

先分割序列,再将分割后的序列进行合并

def merge(a,b):
    c = []
    index_a,index_b = 0,0
    while index_a < len(a) and index_b < len(b):
        if a[index_a] > b[index_b]:
            c.append(b[index_b])
            index_b += 1
        elif a[index_a] <= b[index_b]:
            c.append(a[index_a])
            index_a += 1

    if index_a < len(a):
        c.extend(a[index_a:])
    if index_b < len(b):
        c.extend(b[index_b:])

    return c

def merge_sort(list_a):

    if len(list_a) == 0 or len(list_a) == 1:
        return list_a

    mid = len(list_a)//2
    a = merge_sort(list_a[:mid])
    b = merge_sort(list_a[mid:])

    return merge(a,b)

时间复杂度:o(nlogn)

6 快速排序

通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。这是不稳定的算法,因为时间复杂度最坏o(n^2),最好和平均情况是o(nlogn)。

def paixu(a,b):
    c = a+b
    p = (len(a)+len(b))//2
    end = len(a)+len(b)-1
    for start in range(p):
        for i in range(p, end + 1):
            if c[start] >= c[i] and start <= len(a) - 1:
                c[start], c[i] = c[i], c[start]
    return c


def q_paixu(a):
    if len(a) <= 1:
        return a
    else:
        p = len(a)//2
        j = q_paixu(a[0:p])
        b = q_paixu(a[p:len(a)])

    return paixu(j,b)

7 希尔排序

它就是直接插入排序的进阶、这个网址解释的很清楚。

https://blog.csdn.net/u014745194/article/details/72783357

关于这七个排序算法的稳定性和时间复杂度:

https://www.cnblogs.com/nannanITeye/archive/2013/04/11/3013737.html

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,

冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。再简单具体一点,如果A i == A j,Ai 原来在 Aj 位置前,排序后 Ai  仍然是在 Aj 位置前。 

 

插入排序:第n趟前n+1个有序

选择排序:第n趟前n个位置正确

快速排序:第n趟有n个元素位置正确

堆排序:第n趟前或后n个位置正确

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/152568.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Java static关键字与static{}语句块

    Java static关键字与static{}语句块目录直通车一、类的加载特性与时机1、 类加载的特性2、类加载的时机二、static的三个常用1、修饰成员变量2、修饰成员方法3、 静态块(static{})一、类的加载特性与时机在进入static之前,先补一下关于类的脑。1、 类加载的特性在JVM的生命周期里,每个类只会被加载一次。类加载的原则:延迟加载,能少加载就少加载,因为虚拟机的空…

  • 递归和迭代的区别「建议收藏」

    递归和迭代的区别「建议收藏」递归的基本概念:程序调用自身的编程技巧称为递归,是函数自己调用自己.一个函数在其定义中直接或间接调用自身的一种方法,它通常把一个大型的复杂的问题转化为一个与原问题相似的规模较小的问题来解决,可以极大的减少代码量.递归的能力在于用有限的语句来定义对象的无限集合.使用递归要注意的有两点:1)递归就是在过程或函数里面调用自身;2)在使用递归时,必须有一个明确的递归结束条件,称为递归出口.

  • 什么是 Hook 技术

    什么是 Hook 技术一、什么是Hook技术  Hook技术又叫做钩子函数,在系统没有调用该函数之前,钩子程序就先捕获该消息,钩子函数先得到控制权,这时钩子函数既可以加工处理(改变)该函数的执行行为,还可以强制结束消息的传递。简单来说,就是把系统的程序拉出来变成我们自己执行代码片段。  要实现钩子函数,有两个步骤:  1.利用系统内部提供的接口,通过实现该接口,然后注入进系统(特定场景下使用)  2.动态代理(使用所有场景)二、Hook技术实现的步骤  Hook技术实现的步骤也分为两步  1.找到ho

  • 谈谈CListCtrl 扩展风格设置方法-SetExtendedStyle和ModifyStyleEx 比較

    谈谈CListCtrl 扩展风格设置方法-SetExtendedStyle和ModifyStyleEx 比較谈谈CListCtrl扩展风格设置方法————————————–SetExtendedStyle和ModifyStyleEx比較对于刚開始学习的人来说,当他须要设定listctrl的扩展风格时,经常想到用ModifyStyleEx来设定,代码例如以下:ModifyStyleEx(0,LVS_EX_GRIDLINES)…

  • SQLServer图数据库一些优点

    SQLServer图数据库一些优点

    2021年11月26日
  • Springboot+netty实现Web聊天室

    Springboot+netty实现Web聊天室Web聊天室的实现一、项目的创建一、项目的创建新建Spring项目:选择JDK版本:选择SpringWeb:项目名称和位置的设置:

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号