排序算法总结（Python）

常见的八大排序算法

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序
• 快速排序
• 归并排序
• 堆排序
• 基数排序
• 排序算法性质总结

冒泡排序

冒泡排序是最基础和简单的排序算法，算法的思想是通过遍历数组，比较相邻俩个数的大小，将大的数放置于后面。

第一次能将最大的数置换至数组末尾，经过n次遍历替换就能完成整体的排序。

故算法的复杂度为0( n 2 n^2 n2)。

由于冒泡排序过程中，大的数才会被替换至后面，保证了算法的稳定性。

冒泡排序算法的实现

def maopao(lis):
    for k in range(len(lis)-1):
        count = 0
        for i in range(len(lis)-1):
            if lis[i]>lis[i+1]:
                lis[i],lis[i+1] = lis[i+1],lis[i] 
                count += 1
        if count==0:
            break
    return lis
#排序算法稳定
#最坏时间复杂度为O（n2）

但是每次排序至少将一个元素的位置排好，故每次排序中只需排序n-k个数，k为排序的次数，改进的冒泡排序算法的如下

def maopao(lis):
    for k in range(len(lis)-1):
        count = 0
        for i in range(len(lis)-1-k):
            if lis[i]>lis[i+1]:
                lis[i],lis[i+1] = lis[i+1],lis[i] 
                count += 1
        if count==0:
            break
    return lis
#排序算法稳定
#最坏时间复杂度为O（n2）

选择排序

选择排序算法的算法思想比较简单，首先选取数组中最小的数与数组第一个元素交换，然后再选取n-1个数中最小的数与数组第二个元素交换，最终在第n-1次遍历后完成数组的排序。

由于选取最小元素的交换过程中无法保证元素的相对位置，故该算法是不稳定的。

算法需要经过n-1次遍历，每次遍历都要寻找最小值并交换，故算法的复杂度为0( n 2 n^2 n2)。

选择排序算法的实现

def select(lis):
    for i in range(len(lis)-1):
        minimize,index = lis[i],i
        for k in range(i+1,len(lis)):
            if lis[k]<minimize:
                minimize = lis[k]
                index = k
        if index!=i:
            lis[i],lis[index] = lis[index],lis[i]
    return lis
#时间复杂度为O（n2）
#算法不稳定   

插入排序

插入排序算法类似于纸牌，我们一张一张拿起纸牌，将纸牌置于正确的位置。

插入排序算法就是基于这个思想，将前k个数认为是已排好序，然后将第k+1个数与排好序的数组进行比较从而寻找其正确的位置。

该算法是通过遍历将数插入，数的相对位置不会发生变化，故该算法是稳定的。

算法的复杂度
为0( n 2 n^2 n2)

插入排序算法的实现

def insert(lis):
    for i in range(1,len(lis)):
        value,index = lis[i],i
        while(index>0 and lis[index-1]>value):
            lis[index] = lis[index-1]
            index -= 1
        lis[index] = value
    return lis

#时间复杂度为O（n2）        
#算法是稳定的

希尔排序

希尔排序是建立在插入排序的基础上的，由于插入排序在数组基本有序的情况下，排序效率较高。

故我们将数组拆分为若干个子序列，每次对子序列进行排序，最终进行排序时数组则基本有序，这样排序效率大大提升。

希尔排序实现时，是通过对等间距的序列进行排序，故会导致排序结果存在相对位置改变的情况，即该算法是不稳定的。

算法的平均复杂度为O( n 1.5 n^{1.5} n1.5)或O( n 1.3 n^{1.3} n1.3)（这取决于增量的选择）。

希尔排序算法的实现

def xiersort(lis):
    length = len(lis)
    gap = length//2
    while gap>0:
        #子序列组数
        for i in range(0,gap):
            #插入排序
            for index in range(i+gap,length,gap):
                target,pos = lis[index],index
                while index>0 and lis[index-gap]>target:
                    lis[index] = lis[index-gap]
                    index -= gap
                lis[index] = target
        gap //= 2
    return lis
#算法不稳定                             

快速排序

快速排序算法是通过选择一个目标，然后将比目标小的数置于目标左边，将比目标大的数置于目标右边，然后采取分治的思想，实现每一个小数组都是有序的，从而得到结果数组是有序的。

快排算法的最坏复杂度为O( n 2 n^2 n2)，但是其平均复杂度为O(nlogn)。

算法过程中的交换不考虑位置的相对位置，故该算法是不稳定的。

快排算法首先是将第一个目标作为target，然后加入左右俩个指针，先遍历右指针，当右指针指向比target小的数时将左指替换为右指针指向的数，然后遍历左指针，当左指针指向比target大的数时将右指针替换为左指针指向的数，然后这样子循环，当左右指针相遇时，在将target放入。

然后通过这个思想，分别治理target的左右子序列，最终完成排序。

快排算法的实现

def quick(lis,begin,end):
    if begin<end:
        left,right,value = begin,end,lis[begin]
        while left<right:
            while left<right and lis[right]>value:
                right -= 1
            lis[left] = lis[right]
            while left<right and lis[left]<=value:
                left += 1
            lis[right] = lis[left]
        if left == right:
            lis[left] = value
        quick(lis,begin,left-1)
        quick(lis,left+1,end)
#算法不稳定


lis = [49,38,65,97,76,13,27,49,55,4]
quick(lis,0,len(lis)-1)
print(lis)

归并排序

归并排序是使用分治的方法，将数组分为多个小数组，然后不断地将小数组合并为升序数组，最终得到有序数组，由于数组是通过切分小数组，故合并过程中元素的相对位置并没有受到影响，故该算法是稳定的。

算法的复杂度为O(nlogn)。

归并排序算法的实现

def merge_lis(lis_left,lis_right):
    result = []
    left,right = 0,0
    for i in range(len(lis_left)+len(lis_right)):
    	#判断是否有一边已经排序完
        if right==len(lis_right):
            result.extend(lis_left[left:])
            return result
        elif left==len(lis_left):
            result.extend(lis_right[right:])
            return result
        if lis_left[left]<=lis_right[right]: #等于保证了算法的稳定性
            result.append(lis_left[left])
            left += 1
        elif lis_left[left]>lis_right[right]:
            result.append(lis_right[right])
            right += 1
    return result
def lis_sort(lis):
    if len(lis)<=1:
        return lis
    mid = len(lis)//2
    lis_left_sort = lis_sort(lis[:mid])
    lis_right_sort = lis_sort(lis[mid:])
    return merge_lis(lis_left_sort,lis_right_sort)  
#算法复杂度为O(nlogn)
#算法是稳定的   

堆排序

堆排序是将数组看作一个堆，然后从最后一个父节点（(n-2)/2 向下取整）开始调整堆，最后使堆成为一个最大堆，然后每一次将堆顶的元素与数组后一个元素进行替换，再更新堆，重复这个过程，使数组成为有序数组。

由于堆排排序中存在交换且未考虑相对位置，故堆排是不稳定的。

堆排序的实现

def heapadjust(lis,par,length):
    temp = lis[par]
    child = 2*par+1
    while child<length:
    	#查找最大子节点
        if child+1<length and lis[child]<lis[child+1]:
            child += 1
        if temp > lis[child]:
            break
        lis[par] = lis[child]
        par = child
        child = par*2+1
    lis[par] = temp

def heapsort(lis):
    #从最后一个父节点开始建立堆，保证了父节点比子节点大
    for i in range(int((len(lis)-2)/2),-1,-1):
        heapadjust(lis,i,len(lis)) 
    #将堆顶元素置于队尾，队尾元素置于堆顶，再还原堆
    for i in range(len(lis)-1,0,-1):
        lis[i],lis[0] = lis[0],lis[i]   
        heapadjust(lis,0,i)

基数排序

基数排序的思想就是通过比较数组元素的个位数，根据个位数进行比较排序，再根据十位数进行比较排序，再对百位数，直至最高位数，最终完成数组的排序。

该算法在排序时是稳定的。

算法的复杂度为O(d(n+k)) 其中k为桶数也就是10，d为最高位数，当n较大时，算法复杂度为O(n)。

#寻找最大的位数，虽然python中有更简单的方法，但是这个方法可以在其他语言实现
def searchmaxlength(lis):
    maxlen = 1
    gap = 10
    for i in lis:
        while i//gap !=0:
            maxlen +=1
            gap *= 10
    return maxlen
def redixsort(lis):
    maxlen = searchmaxlength(lis)
    #生成二维数组，然后从个位数排到最高位数，最终完成排序
    for i in range(maxlen):
        result = [[] for k in range(10)] #生成空桶
        for value in lis:
            result[value//(10**i)%10].append(value) #将数据放入对应的位置
        #按从左到右从下到上的规则放回列表，这也保证了算法的稳定性
        count = 0
        for m in result:
            if len(m)==0:
                continue
            for key in m:
                lis[count] = key
                count += 1
    return lis

排序算法性质总结

算法	平均复杂度	最坏复杂度	最好复杂度	稳定性
冒泡排序	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( n ) O(n) O(n)	稳定
选择排序	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	不稳定
插入排序	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( n ) O(n) O(n)	稳定
希尔排序	O ( n 1.3 ) O(n^{1.3}) O(n1.3)或 O ( n 1.5 ) O(n^{1.5}) O(n1.5)	O ( n 2 ) O(n^2) O(n2)	O ( n ) O(n) O(n)	不稳定
快速排序	O ( n l o g n ) O(nl og n) O(nlogn)	O ( n 2 ) O(n^2) O(n2)	O ( n l o g n ) O(nlogn) O(nlogn)	不稳定
归并排序	O ( n l o g n ) O(nlogn) O(nlogn)	O ( n l o g n ) O(nlogn) O(nlogn)	O ( n l o g n ) O(nlogn) O(nlogn)	稳定
堆排序	O ( n l o g n ) O(nlogn) O(nlogn)	O ( n l o g n ) O(nlogn) O(nlogn)	O ( n l o g n ) O(nlogn) O(nlogn)	不稳定
基数排序	O ( d ( n + k ) ) O(d(n+k)) O(d(n+k))	O ( d ( n + k ) ) O(d(n+k)) O(d(n+k))	O ( d ( n + k ) ) O(d(n+k)) O(d(n+k))	稳定

以上总结是个人的学习理解，若有错误，请指出。