面向研究生入学考试编程:排序算法 02 改进的排序算法 木灵的炼金工作室

选择排序改进:堆排序

我们之前提到过,选择排序可以优化的部分主要是“最小值的选取”,而最小值的选取我们可以通过二叉小堆来将其优化至$O(\log n)$。我们可以使用python3中默认的heapq库(其实就是因为懒得写小堆了)来实现:

堆排序

import heapq
def heapSort(arr):
    heap = []
    for i in arr:
        heapq.heappush(heap, i)
    for i in range(len(arr)):
        arr[i] = heapq.heappop(heap)
    return arr

对于一个长度为n的输入,堆排序的最差时间界是$O(n\log n)$,用了$O(n)$的额外空间。由于堆的底层实现,堆排序在算法上是不稳定的。

插入排序改进:希尔排序

怎样改进插入排序

在改进插入排序算法之前,我们首先也来考虑一下“为什么插入算法需要改进”
考虑一个极端情况:输入数组为[10, 9, 8, 7, 6, 5, 4, 3, 2, 1],我们需要将它从小到大排序:
我们发现,由于数组是反序的,对于越小的数,我们需要花费更多的次数来移动它。对于最远端的1,我们需要将它移动一整个数组的长度,这太慢了。
所以我们考虑首先将数组的一部分进行排序:比如将数组按奇数和偶数索引分为两部分,各自进行插入排序,这样,第一次排序之后的数组是 [2, 1, 4, 3, 6, 5, 8, 7, 10, 9],本次排序花费时间$2((n/2)^2)$。随后再对目前的数组进行插入排序:由于数组变得部分有序,所以我们插入的最差时间界变成了$O(n)$(对于每个数,最多需要移动1次),这样,我们有效地将插入排序所需的时间大约减少了一半。
但减少一半对于我们来讲并不够,减少一半之后的最坏时间界仍是$O(n^2)$,这个时间界是由第一次排序引入的 $2((n/2)^2)$ 时间,因此我们对于切割好的子数组继续这一过程:分别插入排序子数组[10, 6, 2] [9, 5, 1] [8, 4] [7, 3],这个排序时间大致(因为有两个子数组内元素是2)为 $4((n/4)^2)$ ,排序得到数组[2, 1, 4, 3, 6, 5, 8, 7, 10, 9],随后进行刚刚我们做的工作。我们发现,我们又将时间界减小了一半。

希尔排序

那么我们得到,如果一直这样细分,这个排序的效率将会变得很高。
希尔排序是把记录按下标的一定增量分组,对每组使用插入排序。当增量减至1时,算法终止。
但是,如何划分这一增量呢?有一个建议是倒着使用数列1, 4, 13, 40...,其中每一项都是前一项的三倍再加一:请看代码

def shellSort(arr):
    h = 1
    while h < len(arr) // 3: 
        h = 3 * h + 1
    while h >= 1:
        for i in range(h, len(arr)):
            nowValue = arr[i]
            insertPoint = i - h
            while insertPoint >= 0 and arr[insertPoint] > nowValue:
                arr[insertPoint + h] = arr[insertPoint]
                insertPoint -= h
            arr[insertPoint + h] = nowValue
        h //= 3
    return arr

对于希尔排序时间复杂度的讨论是复杂的且一直在进行,但可以肯定的是,希尔排序的时间复杂度要优于$O(n^{3/2})$,且使用$O(1)$的额外空间。
数组中相同键值的数完全可能被分为不同的组,所以希尔排序在算法上明显是不稳定的。


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn