排序算法

首先要讨论的是O(n^2)的算法。主要有冒泡排序，选择排序，插入排序。冒泡排序比较常见这里不细说。

①选择排序

选择排序的思路很简单，比如有一个长数组：array = [2, 4, 5, 1, 7, 4, 8]
第一次迭代，寻找0到6个下标的数字哪个是最小的，找到最小的就和第一个交换，也就是2。第一次遍历所有array = [2, 4, 5, 1(minimum), 7, 4, 8]找到最小就是1了，由于是第一次迭代，自然就和第一个数交换了：
array = [1(exchange), 4, 5, 2(exchange), 7, 4, 8]这样就完成了第一次迭代。那么第二次迭代自然就是从第二个数字开始了，而且刚刚第一次迭代已经把第一个数字排好了，所以不必要考虑了。同样，寻找下标1到最后最小的数字：
array = [1, 4, 5, 2(minimum), 7, 4, 8]找到最小就是2了，所以和第二个数字交换：
array = [1, 2, 5, 4, 7, 4, 8]
以此类推，最后就排好了顺序。

②selectionSort代码实现

def selectionSort(arr, n):
    for i in range(n):
        '''find the smallest number in range[i, n)'''
        min = i
        for j in range(i+1, n):
            if arr[j] < arr[min]:
                min = j
        arr[min], arr[i] = arr[i], arr[min]
    return arr

比较简单，选择排序复杂度就是O(n^2)因为无论什么情况，都必须要全部遍历完，如果是n个元素，遍历次数就是:(1 + 2 + 3 + 4......+ n) = \frac {(1 + n)*n} {2}当然n方前面还有一个系数的，只不过当n很大的时候这个次数可以忽略，所以没有计算。

③插入排序

插入排序也很直观，直接比较j和第j-1个元素，如果是小于那就互相交换。
比如有一个数组：array = [2, 4, 5, 1, 7, 4, 8]首先第一次迭代，指向的是第二个数字，因为第一个数字相当于是自己和自己比的，所以不需要比较直接跳到第二个array = [2 <--> 4, 5, 1, 7, 4, 8]j和j-1比较，2和4比较，位置正确，没必要换。第二次迭代array = [2, 4, 5, 1, 7, 4, 8]也是一样的，直接进入到第三次迭代，这时候就是指向1了，所以5和1比，需要换：array = [2, 4, 1, 5, 7, 4, 8]1和4比，又有：array = [2, 1, 4, 5, 7, 4, 8]和2比，又有：array = [1, 2, 4, 5, 7, 4, 8]就是这样以此类推。所以如果这个数组是基本有序的话，那么插入排序是可以退化成O(n)的，因为基本每一次和前一次比较就够了。插入排序是可以终止某一次的循环的。

④insertSort代码实现

def insertSort(arr, n):
    for i in range(1, n):
        for j in range(i, 0, -1):
            '''insert sort can be stop ahead of time'''
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
            else:
                break
            pass

代码应该蛮好理解的。讲道理，虽然两个都是O(n^2)但是插入排序是可以退化成n的，来看看实际的效果。使用10000个数据进行排序（python实现本来就慢。）

插入排序还是比选择排序要慢。这是因为每一次的循环遍历过程中都会有比较和交换，交换需要三次赋值，还要访问下标，这就是导致了时间会增加，所以需要改进一下，使得只要一次赋值就好了。于是代码的改进如下。
还是有一个数组array = [2, 4, 5, 1, 7, 4, 8]从第三次迭代开始，因为第一第二次迭代每一任何的变化。第三次迭代开始使是指到1的，首先复制一份1，第j个和第j-1个比较，需要交换的，直接赋值array = [2, 4, \frac{5}{copy:1}, 5, 7, 4, 8]也需要交换，所以继续复制array = [2,\frac{4}{copy:1} , 4, 5, 7, 4, 8]继续比较，到边上的时候结束循环直接把j指向的赋值temp，也就是备份的那一项。改进的代码：

def optimizedInsertSort(arr, n):
    for i in range(1, n):
        temp = arr[i]
        for j in range(i, -1, -1):
            if arr[j-1] > temp:
                arr[j] = arr[j-1]
            else:
                break
        arr[j] = temp
    pass

最后对比一下时间：

最后一个是优化的，其实就是看看执行时间，代码会在GitHub上。暂时来说是最快的。

---

O(n^2)的完了，下面就是O(nlog_2^{(n)})的了。

⑤自顶向下的归并排序

自顶向下的一种排序，有一个数组array = [3, 4, 1, 2, 7, 4, 5]首先要切分，这里是奇数，只能不均等了a1 = [3, 4, 1], a2 = [2, 7, 4, 5]再切分a1 = [3], a2 = [4, 1], a3 = [2, 7], a4 = [4, 5]最后一次a1 = [3], a2 = [4], a3 = [1], a4= [2], a5 = [7], a6 = [4], a7 = [5]这样就是最后的划分了，然后就是进行合并操作了，但是归并操作要注意范围，因为有时候如果是奇数的话可能会出现越界。

⑥mergeSort代码实现

def __merge(arr, start, mid, end):
    '''merge two order array,the temp array size must be bigger than (r - l + 1)'''
    tempArray = []
    for i in range(start, end+1):
        tempArray.append(arr[i])
    i = start
    j = mid + 1
    for k in range(start, end+1):
        if i > mid:
            arr[k] = tempArray[j - start]
            j += 1
        elif j > end:
            arr[k] = tempArray[i - start]
            i += 1
        elif tempArray[i - start] > tempArray[j - start]:
            arr[k] = tempArray[j - start]
            j += 1
        else:
            arr[k] = tempArray[i - start]
            i += 1
        pass

合并操作，把arr数组的start - mid 和 mid+1 - end合并起来。首先是需要一个缓存数组了，首先是把所有的数据扔到缓存数组temArray，然后需要确定范围的越界问题，如果越界了直接扔另外一个，如果没有就要确定哪个小了。而且，缓存数组和原数组是有偏移的，所有需要减去偏移量。接下来就递归了：

def __mergeSort(arr, start, end):
    '''order arr from start to end,[start, end]'''
    start = int(start)
    end = int(end)
    if start >= end:
        return
    mid = (start + end)/2
    mid = int(mid)
    __mergeSort(arr, start, mid)
    __mergeSort(arr, mid+1, end)
    if arr[mid] > arr[mid + 1]:
       __merge(arr, start, mid, end)
    pass

def mergeSort(arr, n):
    __mergeSort(arr, 0, n-1)
    pass

这里是设置了一下如果arr[mid] > arr[mid + 1]
才需要进行，否则就不要了，因为两边都是有序的，如果中间不一样那就真不一样了。最后同上面几个来对比一下时间：

事实上还可以再快点，我们是切分到一个数据的时候直接合并的，如果我们切分到小数据之后就拿插入排序，效果可能会更好，虽然插入排序是O(n^2)但是它前面还有一个系数，这个系数是比归并排序的系数大的，所以一开始小数据量插入排序是比归并排序要快的，只是到后面的增长超过了而已，所以可以切分到10或者20个然后插入排序即可。

⑦自底向上归并排序

思想其实就是反着过来，比如有一个数组array = [3, 4, 1, 2, 7, 4, 5]先两个两个的排，那么就是a1 = [3, 4], a2 = [2, 7], a3 = [4, 5]然后进行两个两个的排，a1, a2排，a3没有了，之后再合成一个。一开始先两个两个的排，之后就是四个四个的排，八个八个这样以此类推。

⑧自底向上归并排序的代码实现

def mergeSort_bottom_to_up(arr, n):
    '''bottom to up'''
    rangMent = range(1, n+1, )
    for sz in np.logspace(0, n-1, n, base=2):
        sz = int(sz)
        for i in range(0, n, sz+sz):
            if i + sz < n:
                __merge(arr, i, i + sz - 1, min(i + sz + sz - 1, n-1))
            else:
                break

np.logspace(0, n-1, n, base=2)这个句话就是生成一个等比数列
[1, 2, 4, 8, 16, 32......]等于就是先排序2个，然后4个以此类推。

自顶向下和自底向上的其实差不多的效率，但是自底向上在代码实现中并没有看到有缓存，所以空间的复杂度要小一点，之所以时间会长一点点，是因为生成数组那里慢了一点。

⑨快速排序

quick sort是一种比较有效率的排序。思路也很简单。

现在有一个数组，我们要处理第一个元素，那么快速排序的做法就是找到这个元素的位置。

找到正确的元素其实就是相当是这个元素前面的所有元素要小于，后面的所有的元素要大于：
所以quick sort的核心就是要找到每一个元素应该在的位置。
比如现在要看一下第i位e是大于v的还是小于的，如果是大于v的，那就直接覆盖：

如果是小于v，那就和小于那一段的最后一个换：

最后结束之后：

最后再把v和j指向的位置交换即可：

这样完成了一个寻找一个元素的过程。

⑩quick sort代码实现

def quickSort(arr, n):
    __quickSort(arr, 0, n-1)
    pass

归并排序还是使用一种接口的形式，主要就是实现__quickSort的方法。

def __quickSort(arr, start, end):
    if start >= end:
        return
    p = __partition(arr, start, end)
    __quickSort(arr, start, p-1)
    __quickSort(arr, p+1, end)
    pass

如果是切到一个元素那直接返回就好了。__partition就是对于[start, end]这个区间的数字排序，这里的排序不是指从小到大，而是把start下标的数字排到应该的位置上。然后就是排start到p-1和p+1到end，递归操作。

def __partition(arr, start, end):
    v = arr[start]
    '''make arr[start + 1......j] < v,arr[j + 1......i) > v,
    factor i is what we ready to define'''
    j = start
    for i in range(start + 1, end+1):
        if arr[i] < v:
            arr[j+1],arr[i] = arr[i], arr[j+1]
            j += 1
            pass
    arr[j], arr[start] = arr[start], arr[j]
    return j

最后对比效果，由于bottom-up的merge算法是使用迭代，这就意味着可能会出现溢出的情况，因为sz是指数增长的。这里就不拿来测试了。
比较一下效果：

快速排序还是很快的。但是这是一个完全打乱的的数组，如果这个数组是近乎有序的话，效率是很低的。快速排序和归并是O(nlog^{n})，归并是因为：
快排也差不多是如此，正常的快排：

接近O(nlog^{n})但是不是完全是，如果是近乎有序的数组：

基本每次就是第一个了，这样差不多是遍历，就退化回了O(n^2)

⑪块排改进，随机快排

总是选取第一个不行，那就选取随机的，只需要在__partition里面修改就好了。

def rand_quickSort(arr, n):
    __quickSort_rand(arr, 0, n - 1)
    pass
def __quickSort_rand(arr, start, end):
    if start >= end:
        return
    p = __partition_rand(arr, start, end)
    __quickSort(arr, start, p-1)
    __quickSort(arr, p+1, end)
    pass
def __partition_rand(arr, start, end):
    np.random.seed(0)
    arr[np.random.randint(start, end+1)], arr[start] = arr[start], arr[np.random.randint(start, end+1)]
    v = arr[start]
    '''make arr[start + 1......j] < v,arr[j + 1......i) > v,
    factor i is what we ready to define'''
    j = start
    for i in range(start + 1, end+1):
        if arr[i] < v:
            arr[j+1],arr[i] = arr[i], arr[j+1]
            j += 1
            pass
    arr[j], arr[start] = arr[start], arr[j]
    return j

生成一个有序数组的做法就是先生成一个有序的，之后在随机交换100个。
对于一个基本有序的数组，origin版本的quick sort：

对于随机：

块一点，效果不明显。但是从理论分析还是可以知道大量的数组随机是更有效率的，只不过这里再大就爆内存了，python有堆栈大小限制。
事实上还是有改进空间，如果是一个大量重复的数组，也就是0到10的范围内有1000个，这种1000的数组是很多重复的。看一下排序的效率。

这种情况下merge的排序更加快速。所以很明显还是有改进空间的。于是还有第三种改进的方法。

⑫快排改进version3

对于上一个版本的quick sort其实还是有改进空间的。上面的一个例子的数组是这个数组有很多的重复元素

效果就是会是这样，因为只有小于我们才处理，所以大于等默认是right这边了，所以当排序完之后：

数组是不平衡的，这个时候快速排序就会退化成O(n^2)级别的了，因为如果这个数组很长的话基本一边有一边可以忽略了，比如上面的1000个数组，990个是重复的。
新的思路是这样的，之前都是大于和小于的连在一起，现在就把他们拆开到两边，一左一右。如图：

首先，先从i开始扫描，如果这个元素还是小于，那就i++继续下一步，如果大于的，那就停止。

同样，右边也是一样，扫描到小于的那就停止。

这个时候i和j都是指向的两个元素都不应该在当前的位置上，所以自然就是交换一下就好了：

⑬quickSort_version2代码实现

其他其实都不用变：

def quickSort_version2(arr, n):
    __quickSort_version2(arr, 0, n-1)
    pass

def __quickSort_version2(arr, l, r):
    if l >= r:
        return
    p = __partition_version2(arr, l, r)
    __quickSort_version2(arr, l, p-1)
    __quickSort_version2(arr, p+1, r)

    pass

主要就是是直线partition这个函数：

def __partition_version2(arr, l, r):
    np.random.seed(0)
    arr[np.random.randint(l, r+1)], arr[l] = arr[l], arr[np.random.randint(l, r+1)]
    v = arr[l]
    '''arr[l+1......i] <= v , arr[j......r] >= v'''
    i = l+1
    j = r
    while True:
        while i <= r and arr[i] < v:
            i += 1
        while j >= l+1 and arr[j] > v :
            j -= 1
        if i > j:
            break
        arr[i], arr[j] = arr[j], arr[i]
        i += 1
        j -= 1
    arr[l], arr[j] = arr[j], arr[l]
    return j
    pass

思路和之前的一样，要注意，i <= r和j >= l+1的判断一定要在前面先判断，也就是arr[i]while那段，因为不断的增长是有可能越界的，因为是增加了自进行判断，比如这个数组可能是9，9符合i <= r，但是加完就不行了。
最后看一下效果，使用的还是上面的重复比较多的数组：

可以看到是增加了很多，再看看正常打乱数组的排序时间：

这是排序1000个完全打乱基本没有相同的数组，效果还是很好，主要原因还是这种方法减少了数组里面的赋值交换操作，所以相应提高了不少的时间。

⑭quick sort version3——3ways

其实解决重复键值还有一种方法，三路快排。之前的都是2路排序，因为只是分成了arr[i] >= v \&\& arr[i] < v || arr[i] > v \&\& arr[i] <= v而三路其实就是分成三部分，= > <。具体如下：

现在要判断的元素是arr[i],i是指向当前要判断的一个元素，如果是等于v，那就直接i++即可：

把e纳入相等那块。如果是小于v，那就只需要和等于v这部分的第一个元素交换即可：
然后lt++。如果是对于大一v的：

需要和>v的前一个元素交换，也就是gt-1指向的元素交换

注意看一下i，i的下标还是指向了未判断的数据，所以i是不需要维护的，所以整个过程我们要维护的只有lt和gt。
最后应该是三部分：

⑮三路快排代码实现

def quickSort3ways(arr, n):
    __quickSort3ways(arr, 0, n-1)
    pass

这个操作还是很常规的，接下来就是内部实现了，因为这里的操作没有什么太复杂的，所以直接写在一个函数了：

def __quickSort3ways(arr, l, r):
    if l >= r:
        return

    '''partition'''
    arr[np.random.randint(l, r+1)], arr[l] = arr[l], arr[np.random.randint(l, r+1)]
    v = arr[l]
    lt = l #arr[l+1......lt] < v
    gt = r+1 #arr[gt......r] > v
    i = l+1 #arr[lt+1......i] == v
    while i < gt:
        if arr[i] < v:
            arr[lt+1], arr[i] = arr[i], arr[lt+1]
            lt += 1
            i += 1
        elif arr[i] > v:
            arr[gt-1], arr[i] = arr[i], arr[gt-1]
            gt -= 1
        elif arr[i] == v:
            i += 1
        pass
    arr[lt], arr[l] = arr[l], arr[lt]
    __quickSort3ways(arr, l, lt-1)
    __quickSort3ways(arr, gt, r)
    pass

lt,gt,i和上面的图片是一一对应的，小于v交换两个都需要加一，大于i不需要改变，等于i加一，都是和上图对应。最后对比一下结果，对于一个有大量重复的数组：

还是块了一点点，但是随着数组的增长这个增幅会越来越大的。
对于一个正常打乱的数组：

效果相差不大，但是还是可以看得出一点点区别。虽然都是O(nlog^{(n)})但是quick sort还是比merge sort要快很多。

⑯merge sort和quick sort衍生的一些问题

这个两个算法都是使用了分治的思想，分治就是将原问题分解成同等结构的子问题最后通过求解子问题间接求解原问题。merge sort没有太多的考虑分割的位置，直接平均，quick sort是按照了当前元素的位置来划分。从merge sort和quick sort衍生出来有两个问题：

1.逆序对

首先声明是逆序对，比如array = [3, 7, 2, 6, 8, 1, 5, 4]那么像[3, 4]这些就是顺序对。而像[5, 4], [7, 5]这种就是逆序对了。逆序对一个最典型的的作用就是可以衡量这个数组的有序程度。
寻找逆序对，最简单的解法就是进行暴力求解了，两层循环遍历，这样的时间复杂度就是O(n^2)但是可以使用merge sort的思想来解决，使得时间复杂度是O(nlog^{n})
对于上面的数组求一下逆序对，我们对上面这个数组最归并的时候，中间是有一个合并的步骤：array1 = [2, 3, 6, 7], array2 = [1, 4, 5 , 8]我们需要把这两个数组合并，首先看一下2和1，很明显是选1，那么1是可以和2后面的所有数字[2, 1][3, 1][6, 1][7, 1]组成逆序对的，然后2和4比，2和4及4后面的数字都可以组成逆序对，以此类推最后可以很快速的找到。
具体的操作其实就是在归并排序分成两边之后分别进行逆序对的操作然后相加即可。有点像Leecode里面的493，但是简单点，Leecode里面的493是需要用到二进制树。

'''look for the number of the reverse pair'''
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns

class Solution:

    def __init__(self):
        self.number = 0

    def reversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        number = self.mergeSort(arr=nums)
        return number

    def __merge(self, arr, start, mid, end, n):
        '''merge two order array,the temp array size must be bigger than (r - l + 1)'''
        tempArray = []
        number = 0
        for i in range(start, end+1):
            tempArray.append(arr[i])
        i = start
        j = mid + 1
        for k in range(start, end+1):
            if i > mid:
                arr[k] = tempArray[j - start]
                j += 1
            elif j > end:
                arr[k] = tempArray[i - start]
                i += 1
            elif tempArray[i - start] > tempArray[j - start]:
                number += (mid+1 - i)
                arr[k] = tempArray[j - start]
                j += 1
            else:
                arr[k] = tempArray[i - start]
                i += 1
            pass
        return number


    def __mergeSort(self, arr, start, end, n):
        '''order arr from start to end,[start, end]'''
        start = int(start)
        end = int(end)
        if start >= end:
            return 0
        mid = (start + end)/2
        mid = int(mid)
        self.__mergeSort(arr, start, mid, n)
        self.__mergeSort(arr, mid+1, end, n)
        self.number += self.__merge(arr, start, mid, end, n)
        return self.number
        pass

    def mergeSort(self, arr):
        '''top to down'''
        number = 0
        n = len(arr)
        number = self.__mergeSort(arr, 0, n-1, n)
        if number != None:
            return number
        pass

if __name__ == '__main__':
    a = Solution()
    print(a.reversePairs([3,1,2,6,3,3]))

2.最小的N个数

选择最小的n个数字也是可以使用分而治之的方法来实现。可以先随机找到一个数字是属于第几个，如果要找的是大于这个数字的索引，那就只需要找递归后面一部分的了，小于才递归前面一部分。快速排序是可以实现的，比如array = [2,1,5,3,4,2]先随机找一个数字，比如是3，那么排完之后array = [2,1,2,3,4,5]如果我刚刚好就是找第四个小的，那就是这个数字了，如果是找第3个小的，那就只需要递归array = [2,1,2]即可。由于只需要区分两种情况。使用双路快排就好了。

'''Look for the NTH small number'''
import numpy as np
import pandas as pd
import seaborn as sns
def quickSort_version2(arr, n):
    m = len(arr)
    print(__quickSort_version2(arr, 0, m-1, n-1))
    pass

def __quickSort_version2(arr, l, r, n):
    if l >= r:
        return arr[l]
    p= __partition_version2(arr, l, r)
    if n == p:
        return arr[p]
    elif n < p:
        return __quickSort_version2(arr, l, p-1, n)
    elif n > p:
        return __quickSort_version2(arr, p+1, r, n)
    pass

def __partition_version2(arr, l, r):
    np.random.seed(0)
    swap(arr, np.random.randint(l, r+1), l)
    v = arr[l]
    '''arr[l+1......i] <= v , arr[j......r] >= v'''
    i = l+1
    j = r
    while True:
        while i <= r and arr[i] < v:
            i += 1
        while j >= l+1 and arr[j] > v :
            j -= 1
        if i > j:
            break
        swap(arr, i, j)
        i += 1
        j -= 1
    swap(arr, l, j)
    return j
    pass

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


if __name__ == '__main__':
    b = [1,4,2,3,5]
    a = [1,12,53,23,2,78,63]
    c = [45,23,67,21,34,21,54,75]
    quickSort_version2(c, 2)

在双路快排的基础上改进一下而已。

⑰堆排序heapSort

首先得有一个堆，先得实现一个堆，已经实现了一个，堆是属于数据结构里面的，在数据结构这篇文章里面有详解，这里使用的堆也是引那里实现的。堆的性质：1.是一棵完全二叉树。2.当前节点必须是不小于或者是不大于父节点，因为堆也分最小堆和最大堆。堆的基本方法insert，插入一个元素，插入了这个元素之后要将这个元素和父节点进行大小比较，大了就交换，小就这样了。extractMax是出堆，出堆的一定是最大的元素，也就是最顶端的元素，所以出堆之后要记得下浮操作已保证堆的性质。所以只要extract，一定是元素大到小，排序就很简单了，直接出就好了。

def heapSort(arr, n):
    heap = maxheap()
    for i in range(n):
        heap.insert(arr[i])
    for i in range(n-1, -1, -1):
        arr[i] = heap.extractMax()

    print(arr)
    pass

和其他排序对比一下：

if __name__ == '__main__':
    sys.setrecursionlimit(1000000000)
    n = 1000
    start = 1
    end = 10000
    array = tool.generateRandomArray(n,start, end)
    #array = tool.generateNearlyOrderArray(n, start, end)
    mergetime = tool.testSort(mergeSort, array, n)
    quicktime = tool.testSort(quickSort, array, n)
    quicktime_random = tool.testSort(rand_quickSort, array, n)
    quicktime_version2 = tool.testSort(quickSort_version2, array, n)
    quicktime_version3 = tool.testSort(quickSort3ways, array, n)
    heapsortTime = tool.testSort(heapSort, array, n)
    print('mergeSort', mergetime, 's')
    print('quickSort', quicktime, 's')
    print('quickSort_rand', quicktime_random, 's')
    print('quickSort_version2', quicktime_version2, 's')
    print('quickSort3ways', quicktime_version3, 's')
    print('heapSort', heapsortTime, 's')

1000个正常的打乱的数组：

1000个差不多有序的数组：

无论哪种方法堆排序效率都不够高。很明显还有改进方法，这和之前学的堆排序也不太一样。

⑱堆排序的改进

之前构建堆的方法是整个数组一个一个的插入，太耗费时间了，有一种heapify方法是可以很快的把这个数组构建成一个堆的。具体流程如下：

首先得找到第一个非叶子的节点，从图中找规律可以看到就是节点总数count/2，这里的除法是计算机除法，向下取整。
先看看第一个非叶子节点是不是符合属性要求的。不符合属性交换，也就是下浮操作。如图就是先交换第5个节点，然后第4个，直到1个为止。





这样就是heapify完成了。算法的改进，其实只是需要把数组的赋值也就是insert那块变成heapify即可。

    def heapify(self, arr):
        for i in range(len(arr)):
            self.__array.append(arr[i])
        self.__count = len(arr)
        for i in range(int(self.__count/2), 0, -1):
            self.__shifDown(i)
        pass

这部分的代码是在DataStructure中。

def heapSort_version2(arr, n):
    heap = maxheap()
    heap.heapify(arr)
    for i in range(n-1, -1, -1):
        arr[i] = heap.extractMax()
    pass

对比效果：

对比来说是快了不少。
对于version1版本的heapsort插入复杂度其实是O(nlog^n)因为shifup的是log^n所以，n个数乘上就好了。改进之后的heapify其实n/2，忽略系数就是n所以heapify插入时间复杂度是O(n)对比来说确实是快了不少。

⑲原地堆排序

这个算法是在数组的原基础是进行堆排序，而我们之前都是从1开始，所以要改变一下从0开始了：

首先，把一个数组通过heapify的方式变成堆。

那么第一个元素就是整个数组最大值的元素，所以可以和最后一个元素交换，那么最后一个元素就变成了最大值。

由于把最大值放到了后面，那么前面那段东西就不再是最大堆了。
依照上图类似的方法，我们可以再次进行一个heapify的操作，前半部分（不包括v）的数组再做一次shiftdown操作变成一个最大堆。这样第一个和倒数第二个元素交换。

重复几次就可以了。主要的步骤其实就是：先对整一个数组进行一个heapify操作变成一个最大堆，然后对0索引下的元素进行shiftdown操作，和倒数的几位交换即可。

代码实现：

之前的shiftdown算法都是在类里面的，而且是对于1开始的，现在改变一下：

def __shifdown(arr, n, k):
    while 2 * k + 1 < n:
        j = 2 * k + 1
        if j + 1 < n and (arr[j + 1] > arr[j]):
            j += 1
        if arr[k] >= arr[j]:
            break
        tool.swap(arr, k, j)
        k = j
    pass

对于排序操做：

def heapSort_version3(arr, n):
    for i in range(int((n-1)/2), -1, -1):
        __shifdown(arr, n, i)
        pass

这是heapify操作，变成最大堆。

    for i in range(n-1, 0, -1):
        tool.swap(arr, 0, i)
        __shifdown(arr, i, 0)
    pass

这里就是对0位置进行shiftdown操作，交换倒数几位了，n-1到1是因为最后只剩下一位就不再需要换了，直接返回即可。
对比一下效果：

还是块了一点。

⑳summary of the sort algorithm

sort algorithm	平均时间复杂度	原地排序	额外空间	稳定性
insertion sort	O(n^2)	是	O(1)	好
merge sort	O(nlog^n)	否	O(n + log^n) = O(n)	好
quick sort	O(nlog^n)	是	O(log^n)	不好
heap sort	O(nlog^n)	是	O(1)	不好

对于额外空间：merge sort可以使用递归实现，递归实现每一次开logn的空间，logn次中每次又是n空间。但是merge算法可以自底向上实现，不用递归，所以是n + logn。quick sort就简单了，递归logn次。
稳定性：相同的元素，如果排序后相同元素之间的相对顺序是改变了，那就是不稳定的。比如array = [1,4,2,3(a),6,3(b),6]排序后如果是array = [1,2,3(a),3(b),4,6,6]那么这样就是稳定的，如果是array = [1,2,3(b),3(a),4,6,6]那就是不稳定的了。

最后附上所有GitHub代码：https://github.com/GreenArrow2017/DataStructure