排序II之快排堆排序和归并排序

快速排序

原理

分而治之思想：

• Divide：找到基准元素pivot，将数组A[p..r]划分为A[p..pivotpos-1]和A[pivotpos+1...q]，左边的元素都比基准小，右边的元素都比基准大;
• Conquer：对俩个划分的数组进行递归排序；
• Combine：因为基准的作用，使得俩个子数组就地有序，无需合并操作。

性能

快排的平均时间复杂度为O(NlogN），空间复杂度为O(logN)，但最坏情况下，时间复杂度为O(N^2)，空间复杂度为O(N)；且排序是不稳定的，但每次都能确定一个元素所在序列中的最终位置，复杂度与初始序列有关。

优化

当初始序列是非递减序列时，快排性能下降到最坏情况，主要因为基准每次都是从最左边取得，这时每次只能排好一个元素。
所以快排的优化思路如下：

• 优化基准，不每次都从左边取，可以进行三路划分，分别取最左边，中间和最右边的中间值，再交换到最左边进行排序；或者进行随机取得待排序数组中的某一个元素，再交换到最左边，进行排序。
• 在规模较小情况下，采用直接插入排序

代码

def partition(li, left, right):
    tmp = li[left]
    while left < right:
        while left < right and tmp <= li[right]:
            right -= 1
        li[left] = li[right]
        print(li)
        while left < right and tmp >= li[left]:
            left += 1
        li[right] = li[left]
        print(li)
    li[left] = tmp
    print(li)
    return left

def quick_sort(li, left, right):
    if left < right:
        mid = partition(li, left, right)
        quick_sort(li, left, mid-1)
        quick_sort(li, mid+1, right)

堆排序

原理

堆的性质：

• 是一棵完全二叉树
• 每个节点的值都大于或等于其子节点的值，为最大堆；反之为最小堆。

堆排序思想：

• 将待排序的序列构造成一个最大堆，此时序列的最大值为根节点
• 依次将根节点与待排序序列的最后一个元素交换
• 再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列

步骤

• 创建一个堆 H[0……n-1]；
• 把堆首（最大值）和堆尾互换；
• 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
• 重复步骤 2，直到堆的尺寸为 1。

性能

时间复杂度为O(NlogN)，空间复杂度为O(1)，因为利用的排序空间仍然是初始的序列，并未开辟新空间。算法是不稳定的，与初始序列无关。

使用场景

想知道最大值或最小值时，比如优先级队列，作业调度等场景。

代码

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

归并排序

原理

分而治之思想：

性能

时间复杂度总是为O(NlogN)，空间复杂度也总为为O(N)，算法与初始序列无关，排序是稳定的。

优化

优化思路：

• 在规模较小时，合并排序可采用直接插入；
• 在写法上，可以在生成辅助数组时，俩头小，中间大，这时不需要再在后边加俩个while循环进行判断，只需一次比完。

代码

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