• 0

  • 点赞

  • 收藏

经典排序算法和python详解(三):归并排序、快速排序、堆排序、计数

宋佳霖

欢迎交流

4个月前

目录

一、归并排序
二、快速排序
三、堆排序
四、计数排序
五、桶排序
六、基数排序

一、归并排序

归并排序就是利用归并的思想进行排序,也就是分而治之的策略,将问题分成一些小问题,然后递归求解,再将解决好的小问题合并在一起。和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。 归并排序的流程:

其中合并两个有序子问题的流程

归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。

Python代码:

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0));
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0));
    while right:
        result.append(right.pop(0));
    return result

我们以列表[5,4,7,9,3,8,2,1]为例:

  1. 首先middle = len(list) / 2 = 8 / 2 = 4,将列表递归分为两部分Left = [0: middle] = [5,4,7,9], Right = [3,8,2,1],继续将Left和Right细分下去,Left递归得到L1 = [5,4], L2 = [7,9],Right递归得到R1 = [3,8],R2 = [2,1];
  2. 此时L1,L2,R1,R2长度仍大于1,继续细分,L1递归得到L11 = [5],L12 = [4],L2递归得到L21 = [7],L22 = [9],R1递归得到R11 = [3],R12 = [8],R2递归得到R21 = [2],R22 = [1];
  3. 此时L11,L12,L21,L22,R11,R12,R21,R22长度不再大于2,直接返回原列表;
  4. 分别成对将【L11, L12】送入merge函数,此时L11和L12都不为空,判断L11[0] 大于L12[0],result 增加L12[0] = [4],L12为空,result 增加L11[0],=[4,5], L11为空;
  5. 同理将【L21,L22】、【R11,R12】、【R21,R22】送入merge函数,分别得到排好序的result为[7,9]、[3, 8]、[1, 2];
  6. 将【4,5】和【7,9】送入merge函数,得到排好序的result为[4, 5, 7, 9];
  7. 将【3,8】和【1,2】送入merge函数,得到排好序的result为[1, 2, 3, 8];
  8. 将【4,5,7,9】和【1,2,3,8】送入merge函数,得到排好序的result为[1,2,3,4,5,6,8,9];
  9. 最终排序完的结果为[1,2,3,4,5,6,8,9]。

二、快速排序

快速排序的方法是,首先挑出一个元素作为基准,通常采用第一个元素作为基准,重新排序,使得比基准小的值都在基准左边,比基准大的值都在基准右边,这样基准的位置就确定了,进而递归的把左右两边的子序列进行排序,得到最后的排序结果。

快速排序同样是采用分而治之的策略,将一个列表细分成2个列表,本质上是在冒泡排序基础上的递归应用,和冒泡排序相比其每次交换是跳跃式的,而冒泡排序只是交换相邻数,总的比较和交换次数减少,速度提高。在最坏的情况下,仍然需要交换相邻的数,此时最差时间复杂度和冒泡排序是一样的O(n^2),平均时间复杂度为O(nlog2n)。

Python代码:

def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(arr)-1 if not isinstance(right,(int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr

def partition(arr, left, right):
    pivot = left
    index = pivot+1
    i = index
    while  i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index+=1
        i+=1
    swap(arr,pivot,index-1)
    return index-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

我们用列表[6,1,2,7,9,3,4,5,10,8]为例进行快速排序,基准为6,left为0,right为9,进入partition函数:

  1. Index = left+1 = 1,i = index = 1,判断i=1 小于right=9,判断arr[i] = 1小于arr[0] = 6,交换arr[i] 和arr[index],列表不变;
  2. Index = index + 1 = 2,i = i + 1 = 2,判断i=2小于right=9,判断arr[i] = 2小于arr[0] = 6, 交换arr[i]和arr[index],列表不变; 3.Index = index + 1 = 3,i = i + 1 = 3,判断i=3小于right=9,判断arr[i] = 7不小于arr[0] = 6,列表不变;
  3. Index = index = 3,i = i + 1 = 4,判断i=4小于right=9,判断arr[i] = 9不小于arr[0] = 6,列表不变;
  4. Index = index = 3,i = i + 1 = 5,判断i=5小于right=9,判断arr[i] = 3小于arr[0] = 6, 交换arr[i=5]和arr[index=3],列表变为[6,1,2,3,9,7,4,5,10,8];
  5. Index = index + 1 = 4,i = i + 1 = 6,判断i=6小于right=9,判断arr[i] = 4小于arr[0] = 6, 交换arr[i=6]和arr[index=4],列表变为[6,1,2,3,4,7,9,5,10,8];
  6. Index = index + 1 = 5,i = i + 1 = 7,判断i=7小于right=9,判断arr[i] = 5小于arr[0] = 6, 交换arr[i=7]和arr[index=5],列表变为[6,1,2,3,4,5,9,7,10,8];
  7. Index = index + 1 = 6,i = i + 1 = 8,判断i=8小于right=9,判断arr[i] = 10不小于arr[0] = 6,列表不变;
  8. Index = index = 6,i = i + 1 = 9,判断i=9等于right=9,判断arr[i] = 8不小于arr[0] = 6,列表不变;
  9. 交换arr[0]和arr[5],列表变为[5,1,2,3,4,6,9,7,10,8],返回index-1=5此时,第一个基准6已经在准确的位置了,其左边的数都比自身小,右边的数都比自身大。

再将新的列表的左侧进行排序,列表为[5,1,2,3,4,6,9,7,10,8],基准为5,left为0,right 为partitionIndex-1=4,进入partition函数:

  1. Index = left+1 = 1,i = index = 1,判断i=1 小于right=4,判断arr[i] = 1小于arr[0] = 5,交换arr[i] 和arr[index],列表不变;
  2. Index = index+1 = 2,i = index = 2,判断i=2 小于right=4,判断arr[i] = 2小于arr[0] = 5,交换arr[i] 和arr[index],列表不变;
  3. Index = index+1 = 3,i = index = 3,判断i=3 小于right=4,判断arr[i] = 3小于arr[0] = 5,交换arr[i] 和arr[index],列表不变;
  4. Index = index+1 = 4,i = index = 4,判断i=4 等于right=4,判断arr[i] = 4小于arr[0] = 5,交换arr[i] 和arr[index],列表不变;
  5. Index = index+1 = 5,i = index = 5,判断i=5 不小于right=4,交换arr[0] 和arr[index-1=4],列表变为[4,1,2,3,5,6,9,7,10,8],返回partitionIndex = index – 1 = 4,基准5已经在合适的位置了,其左边的数都比自身小,右边的数都比自身大;
  6. 再将新的列表的左侧进行排序,列表为[4,1,2,3,5,6,9,7,10,8],基准为4,left为0,right 为partitionIndex-1=3,进入partition函数,就这样一直递归下去直到6左侧的数据都排序后,再对6右边的数进行排序,最终得到排序后的列表为[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]。

三、堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

1.大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;

2.小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列。 如下图:

升序堆排序的思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。 如此反复执行,便能得到一个有序序列了。

堆排序是一种选择排序,整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n),在交换并重建堆的过程中,需交换n-1次,而重建堆的过程中,根据完全二叉树的性质,[log2(n-1),log2(n-2)…1]逐步递减,近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。

Python代码:

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):
        heapify(arr,i)
def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1
        heapify(arr, 0)
    return arr

我们用列表[4,6,8,5,9]为例:
步骤一、构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)。 a. 假设给定无序序列结构如下:

b. 此时我们从最后一个非叶子结点开始(叶结点自然不用调整,第一个非叶子结点 arr.length/2-1=5/2-1=1,也就是下面的6结点),从左至右,从下至上进行调整。

c. 找到第二个非叶节点4,由于[4,9,8]中9元素最大,4和9交换。

d. 这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4和6。

此时,我们就将一个无需序列构造成了一个大顶堆。

步骤二、将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。

a. 将堆顶元素9和末尾元素4进行交换

b. 重新调整结构,使其继续满足堆定义

c. 再将堆顶元素8与末尾元素5进行交换,得到第二大元素8

d. 后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序

部分参考自:cnblogs.com/chengxiao/p

四、计数排序

计数排序过程中不存在元素之间的比较和交换操作,根据元素本身的值,将每个元素出现的次数记录到辅助空间后,通过对辅助空间内数据的计算,即可确定每一个元素最终的位置。 算法过程:
1.根据待排序集合中最大元素,申请额外空间,大小为最大值 +1;
2.遍历待排序集合,将每一个元素出现的次数记录到元素值对应的额外空间内;
3.对额外空间内数据进行计算,得出每一个元素的正确位置;
4.将待排序集合每一个元素移动到计算得出的正确位置上。

Python代码如下:

def countingSort(arr, maxValue):
    bucketLen = maxValue+1
    bucket = [0]*bucketLen
    sortedIndex =0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]]=0
        bucket[arr[i]]+=1
    for j in range(bucketLen):
        while bucket[j]>0:
            arr[sortedIndex] = j
            sortedIndex+=1
            bucket[j]-=1
    return arr

假设带排序列表为[0,2,5,3,7,9,10,3,7,6],图例如下:

 

最终按顺序将value对应数量的index排列可得[0,2,3,3,5,6,7,7,9,10] 在列表取值范围不是很大的时候,其性能要比O(nlogn)更快。
但计数排序也有明显的缺点:当列表最大值和最小值差距过大时,需要创建的额外空间过大,造成时间复杂度和空间复杂度很高,不适用;当列表元素不只是整数时,无法创建对应的额外空间,也就不能用计数排序了。

五、桶排序

桶排序是计数排序的升级版,利用了函数映射关系,通过映射关系将输入的N个数据均匀的分配给K个桶里。桶排序解决了计数排序无法处理小数的问题。
为避免列表最小值很大,最大值更大的情况,如[99,100,103,105],桶排序的申请额外空间,大小为最大值-最小值 +1,向桶数组填数时不再是一个桶一个数,而是相近的几个数,之后对每个桶进行排序后得到最终排序结果。由算法过程可知,桶排序的时间复杂度为

O(N+N(log2N−log2M))O(N+N(log2N−log2M)) \\

其中M表示桶的个数。由于需要申请额外的空间来保存元素,并申请额外的数组来存储每个桶,所以空间复杂度为O(N+M)。算法的稳定性取决于对桶中元素排序时选择的排序算法。由桶排序的过程可知,当待排序集合中存在元素值相差较大时,对映射规则的选择是一个挑战,可能导致元素集中分布在某一个桶中或者绝大多数桶是空桶的现象,对算法的时间复杂度或空间复杂度有较大影响,所以同计数排序一样,桶排序适用于元素值分布较为集中的序列。

Python代码:

def bucket_sort(s):
    """桶排序"""
    min_num = min(s)#2
    max_num = max(s)#8
    # 桶的大小
    bucket_range = (max_num-min_num) / len(s)
    # 桶数组6/8
    count_list = [ [] for i in range(len(s) + 1)]
    # 向桶数组填数
    for i in s:
        print(int((i-min_num)//bucket_range), i)
        count_list[int((i-min_num)//bucket_range)].append(i)
    print('count_list', count_list)
    s.clear()
    # 回填,这里桶内部排序直接调用了sorted
    for i in count_list:
        for j in sorted(i):
            s.append(j)

六、基数排序

基数排序(Radix Sort)是桶排序的扩展,它的基本思想是:将整数按位数切割成不同的数字,然后按每个位数分别比较。 具体做法是:将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。时间复杂度:O(n*k),空间复杂度:O(n+k)。

通过基数排序对数组{53, 3, 542, 748, 14, 214, 154, 63, 616},它的示意图如下:

Python代码:

def RadixSort(list):
    i = 0                                    #初始为个位排序
    n = 1                                     #最小的位数置为1(包含0)
    max_num = max(list) #得到排序数组中最大数
    while max_num > 10**n: #得到最大数是几位数
        n += 1
    while i < n:
        bucket = {} #用字典构建桶
        for x in range(10):
            bucket.setdefault(x, []) #将每个桶置空
        for x in list: #对每一位进行排序
            radix =int((x / (10**i)) % 10) #得到每位的基数
            bucket[radix].append(x) #将对应的数组元素加入到相 #应位基数的桶中
        j = 0
        for k in range(10):
            if len(bucket[k]) != 0: #若桶不为空
                for y in bucket[k]: #将该桶中每个元素
                    list[j] = y #放回到数组中
                    j += 1
        i += 1
    return  list
本文作者赵杰,未经允许禁止转载。
免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

0

相关文章推荐

未登录头像

暂无评论