排序算法总结

(Updated: )
(6 mins to read)

插入排序

从前往后依次把当前元素插入到前缀的有序序列的相应位置即可。

$O(n^2)$，稳定

1
2
3
4
5
6
7
for (int i = 1; i < n; i++) {
    int key = a[i];
    for (int j = i - 1; j >= 0 && a[j] > key; j--) {
        a[j + 1] = a[j];
    }
    a[j + 1] = key;
}

希尔排序

对插入排序的优化，直观思想是当数组基本有序时，插入排序是很快的。

将一定间隔的元素组成一组进行插入排序，然后每一轮缩小间隔，直至间隔为1。（前期，乱序的元素可以大跨步地归位）。

通常增量序列选择$n/2, n/4, \dots, 1$（最坏仍然是$O(n^2)$），$2^k+1$/$3^k+1$（最坏是$O(n^{3/2}$），$2^p3^q$（最坏时$O(n\log^2 n$）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int gap = 1;
while (gap < n / 3) {
    gap = 3 * gap + 1;
}
while (gap >= 1)
    for (int i = gap; i < n; i++) {
        int key = a[i];
        for (int j = i - gap; j >= 0 && a[j] > key; j -= gap) {
            a[j + gap] = a[j];
        }
        a[j + gap] = key;
    }
    gap /= 3;
}

选择排序

按照数值从小到大依次归位。$O(n^2)$，稳定

1
2
3
4
5
6
7
for (int i = 0; i < n; i++) {
    int mn = i;
    for (int j = i + 1; j < n; j++)
        if (a[j] < a[mn])
                mn = j;
    std::swap(a[i], a[mn]);
}

冒泡排序

扫描n-1轮，在每一轮中，如果前一个数大于后一个数（即逆序），就进行交换，这样第i轮，第i大的数就归位了。 $O(n^2)$，稳定

1
2
3
4
for (int i = 0; i < n - 1; i++)
    for (int j = 0; j < n - 1 - i; j++)
        if (a[j] > a[j + 1])
            std::swap(a[j], a[j + 1]);

堆排序

升序需要先构建大顶堆，然后不断把堆顶移动数组的末尾，并维持大顶堆。$O(n\log n)$，不稳定

关键是堆的一些操作。

位置i的左儿子和右儿子分别是i<<1和i<<1|1

原地建堆

从最后一个非叶子节点开始往前调整，把当前点和儿子节点中最大的那个交换上来。$O(n)$

追加元素

先放在数组末尾，然后从下往上交换调整即可。$O(\log n)$

删除堆顶

从上往下交换调整即可。$O(\log n)$

快速排序

选择一个pivot，将小于pivot的元素移到前面，大于pivot的元素移到后面，然后递归分治即可。

关键点是pivot的选择，最坏可能导致$O(n^2)$，一般会用随机的方式选择。

一个细节是所有数字都相同，这时候不管怎么选都会是$O(n^2)$的，所以在递归的时候先跳过相同的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int partition(vector<int>& nums, int l, int r) {
    int pos = rand() % (r - l + 1) + l;
    swap(nums[l], nums[pos]); // pivote先交换到最左边或者最右边
    int pivot = nums[l];
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (nums[i] < pivot) { // 如果比pivote小就移动最前面
            swap(nums[i], nums[++j]);
        }
    }
    swap(nums[j], nums[l]); // 最后归位pivote
    return j;
}
void quickSort(vector<int>& nums, int l, int r) {
    if (l >= r) return;
    int p = partition(nums, l, r);
    while (p - 1 >= l && nums[p - 1] == nums[p]) --p;
    quickSort(nums, l, p - 1);
    while (p + 1 <= r && nums[p + 1] == nums[p]) ++p;
    quickSort(nums, p + 1, r);
}

std::sort

使用一种混合的introsort。

如果规模小于16，直接插入排序。

在快排深度大于一个阈值时，切换为堆排序，来避免快排最坏$O(N^2)$复杂度的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
procedure sort(A : array):
    maxdepth ← ⌊log2(length(A))⌋ × 2
    introsort(A, maxdepth)

procedure introsort(A, maxdepth):
    n ← length(A)
    if n < 16:
        insertionsort(A)
    else if maxdepth = 0:
        heapsort(A)
    else:
        p ← partition(A)  // assume this function does pivot selection, p is the final position of the pivot
        introsort(A[1:p-1], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)