排序基础

本文主要讨论基于数组的基础排序算法，包括冒泡排序，选择排序，插入排序，归并排序，快速排序，堆排序。

为了代码的可读性，定义交换数组中交换两个位置的元素的工具函数（虽然用python写起来也非常方便）

def swap(array, l, r):
    array[l], array[r] = array[r], array[l]

冒泡排序

排序过程

为数组[6, 3, 5, 7, 0, 4, 1, 2]排序为例。首先排序的范围是[0, n-1]，如果前面的数比后面的数大，则交换位置，直到最大的数位于数组的最后；然后第二轮排序的范围变为[0, n-2]，第二轮结束后，数组第二大的数会放置在数组的倒数第二个位置；依次进行这样的排序过程，直到待排序的范围变成数组的第一个数，此时整个数组的排序完成，数组变的有序。

代码实现

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1, -1, -1):
        for j in range(i, -1, -1):
            if arr[i] < arr[j]:
                swap(arr, i, j)

复杂度分析

时间复杂度： $O(n^2)$
空间复杂度： $O(1)$

---

选择排序

排序过程

同样以数组[6, 3, 5, 7, 0, 4, 1, 2]为例。首先在数组[0, n-1]范围上选出一个最小值放在数组0位置；然后在数组[1, n-1]范围上选出一个最小值放在数组1位置；直到最后待排序范围只剩下数组最后一个数时，此时整个数组的排序完成，数组变的有序。

代码实现

def select_sort(arr):
    min_index = 0
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i, n):
            if arr[j] < arr[min_index]:
                min_index = j
        swap(arr, i, min_index)

复杂度分析

时间复杂度： $O(n^2)$
空间复杂度： $O(1)$

---

插入排序

排序过程

同样以数组[6, 3, 5, 7, 0, 4, 1, 2]为例。首先位置1上的数和位置0上的数进行比较，如果位置1上的数更小，则和位置0上的数交换；接下来考察位置2上面的数，如果位置2上的数比位置1小，则交换，然后继续和位置0上的数比较。假设当前考察的是数组第k个元素m，首先比较位置k-1上的数和m的大小，若大于m则交换，继续将m和位置k-2上的数比较，直到位置k-x上的数，小于等于m；直到考察完数组中所有的元素。
note: 假如当前考察位置k上的元素，则位置[0,k-1]上的数一定是有序的。所以每一轮的排序实质是将当前数插入到该位置之前的有序数组中，使得增加该数后数组仍热有序。

代码实现：

def insert_sort(arr):
    n = len(arr)
    for i in range(1, n):
        j = i
        while j>0 and arr[j] < arr[j-1]:
            swap(arr, j, j - 1)
            j -= 1

复杂度分析

时间复杂度： $O(n^2)$
空间复杂度： $O(1)$

---

归并排序

排序过程

以数组[6, 5, 2, 1, 4, 3, 8, 7]为例。首先让数组中的每一个数单独成为长度为1的有序区间。然后把相邻的长度为1的有序区间进行合并，得到最大长度为2的有序区间。接下来再把相邻有序区间进行合并，得到最大长度为4的有序区间。依次这样进行下去，直到两个长度为n/2的有序区间合并成为长度为n的有序区间，此时整个数组有序。

代码实现

def merge_sort(arr):

    # 数组arr的[l, m]和[m+1, r]已经有序，合并两个区间，使其[l, r]范围有序
    def merge(arr, l, m, r):
        temp = []
        p1 = l
        p2 = m + 1
        while p1 <= m and p2 <= r:
            if arr[p1] <= arr[p2]:
                temp.append(arr[p1])
                p1 += 1
            else:
                temp.append(arr[p2])
                p2 += 1
        # p1和p2必有且只有越界
        while p1 <= m:
            temp.append(arr[p1])
            p1 += 1
        while p2 <= r:
            temp.append(arr[p2])
            p2 += 1
        for i in range(len(temp)):
            arr[l+i] = temp[i]
    
    def merge_sort(arr, l, r):
        if l == r: # 范围内只有一个数
            return
        mid = (l + r) // 2
        merge_sort(arr, l, mid)
        merge_sort(arr, mid+1, r)
        merge(arr, l, mid, r)
    n = len(arr)
    merge_sort(arr, 0, n-1)

复杂度分析

时间复杂度： $O(nlog(n))$
空间复杂度： $O(n)$

---

快速排序

排序过程

随机在数组中选择一个数，然后让小于等于该数的元素放在该数的左边，大于这个该数的元素放在该数的右边，接下来对该数左右两边的数分别递归的调用上述排序过程，直到整个数组都有序。关于数组划分的方法可以参考另一篇文章

代码实现

def quick_sort(arr):
    if not arr or len(arr) < 2:
        return
    
    def partition(arr, l, r):
        pivot = arr[r]
        small = l - 1
        big = r + 1
        cur = l
        while cur != big:
            if arr[cur] < pivot:
                small += 1
                swap(arr, cur, small)
                cur += 1
            elif arr[cur] > pivot:
                big -= 1
                swap(arr, cur, big)
            else:
                cur += 1
        return small + 1, big - 1
    
    def quick_sort(arr, l, r):
        if l < r:
            ll, rr = partition(arr, l, r)
            quick_sort(arr, l, ll-1)
            quick_sort(arr, rr+1, r)
    
    quick_sort(arr, 0, len(arr)-1)

复杂度分析

时间复杂度： $O(nlog(n))$
空间复杂度： $O(log(n))$~$O(n)$取决于划分的具体情况

---

堆排序

堆

概念： 堆通常是一个可以被看做一棵完全二叉树的数组对象。堆总是满足下列性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

其中若某个节点的值总是不大于其父节点的值，这样的堆称为大根堆，反之称为小根堆
因为堆的存储结构通常是数组，所以可以通过数组的索引表示二叉树节点间的关系

• array[i]的左孩子节点为array[2*i+1]，右孩子节点为array[2*i+2]
• array[i]的父节点为array[(i-1)/2]

堆的构建

假设数组[0, i-1]范围的元素已经构成大根堆，将i位置的元素加入到大根堆。若i位置的数比其父节点的数大，则与其父节点交换位置，然后继续与其新的父节点比较，直到该元素小于其父节点为止，此时，数组i位置的元素成功插入大根堆，大根堆的范围变为[0, i]。
参考代码

# 将arr[i]插入到大根堆，使数组[0, i]范围构成大根堆
def insert(arr, i):
        while arr[i] > arr[int((i-1)/2)]:
            swap(arr, i, int((i-1)/2))
            i = int((i-1)/2)

堆的调整

假设数组[0, size]范围的元素已经构成大根堆，假设数组index位置的值发生改变，调整堆结构，使其重新构成大根堆。假设该节点存在左孩子，且同时存在右孩子，则取左右孩子的最大值，与该节点的值比较，若该节点的值大于最大的孩子节点，则不用调整，否则与较大的孩子交换位置，然后继续与新的孩子节点的值比较大小，判断是否需要继续下沉，直到该节点大于所有的孩子节点，重新调成为堆结构。
参考代码

def heapify(arr, index, size):
    # 左孩子的索引
    left =  2 * index + 1
    while left < size:
        right = left + 1
        # 若右孩子存在，返回两个孩子中较大的索引，否则返回左孩子索引
        max_children = right if (right<size and arr[right]>arr[left]) else left
        # 若当前节点的值大于孩子中的最大值，则不需要调整，否则交换
        if arr[index] > arr[max_children]:
            break
                
        swap(arr, index, max_children)
        # 更新该值的新索引，以进一步判断是否需要继续调整
        index = max_children
        left = 2 * index + 1

排序过程

首先将数组中的n个数构造成为一个大根堆，我们知道堆顶是所有元素的最大值，我们将堆顶元素和堆的最后一个元素进行交换，然后把最大值脱离整个堆结构，放在数组的最后的位置，作为数组的有序部分保存下来；接下来重新将数组[0, n-2]范围的n-1个数重新调整为大根堆，然后将新堆顶元素和堆的最后一个元素进行交换，然后把最大值脱离整个堆结构，放在数组的倒数第二的位置，作为数组的有序部分保存下来。这样每次从堆顶弹出一个元素，堆的大小也依次减1，当堆的大小减为1时，整个数组有序。

代码实现

def heap_sort(arr):

    if not arr or len(arr) < 2:
        return

    def insert(arr, i):
        while arr[i] > arr[int((i-1)/2)]:
            swap(arr, i, int((i-1)/2))
            i = int((i-1)/2)

    def heapify(arr, index, size):
        left =  2 * index + 1
        while left < size:
            right = left + 1
            max_children = right if (right<size and arr[right]>arr[left]) else left
            if arr[index] > arr[max_children]:
                break

            swap(arr, index, max_children)
            index = max_children
            left = 2 * index + 1

    n = len(arr)
    for i in range(n):
        insert(arr, i)
    heap_size = n

    while heap_size > 0:
        heap_size -= 1  # 从堆顶弹出一个元素，堆大小减一
        swap(arr, 0, heap_size) # 将元素放置堆外作为数组的有序部分
        heapify(arr, 0, heap_size)  # 堆顶元素变化，重新调整堆结构

复杂度分析

时间复杂度： $O(nlog(n))$
空间复杂度： $O(1)$

排序稳定性

概念： 假定待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，称这种排序算法是稳定的，否则称为不稳定的。

稳定：冒泡排序 插入排序 归并排序
不稳定：选择排序 快速排序 堆排序