下面的这些排序算法可以在leetcode 912. Sort an Array练习

Prerequisites

排序算法的稳定性：

数值相同的元素在排序前后相对位置不变，则称算法稳定。如果只是针对数值类型，谈论稳定性没有意义，稳定性针对有对个属性的对象类型而言。

基于比较的排序算法

基础排序算法

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
void bubbleSort(vector<int>& nums) {
    int N = nums.size();

    for (int i = 0; i < N - 1; i++) {
        for (int j = 1; j < N - i; j++) {
            if (nums[j - 1] > nums[j]) {
                swap(nums[j - 1], nums[j]);
            }
        }
    }
}

优化思路：如果在某一轮扫描中，没有发生元素交换，说明元素已经有序，提前终止程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bubbleSort(vector<int>& nums) {
    int N = nums.size();

    for (int i = 0; i < N - 1; i++) {
        bool sorted = true;
        for (int j = 1; j < N - i; j++) {
            if (nums[j - 1] > nums[j]) {
                swap(nums[j - 1], nums[j]);
                sorted = false;
            }
        }

        if (sorted) {
            return;
        }
    }
}

复杂度分析：

  • 时间复杂度：O(n2)O(n^2)

  • 空间复杂度：O(1)O(1)

稳定性: 算法稳定。

简单选择排序

1
2
3
4
5
6
7
8
9
10
void selectionSort(vector<int>& nums) {
    int len = nums.size();
    for (int i = 0; i < len - 1; i++) {
        int min = i;
        for (int j= i + 1; j < len && nums[j] < nums[min]; j++) {
            min = j
        }
        if (min != i) swap(nums[i], num[min]);
    }
}

优化方向：从未排好序的部分选出最值元素，可以利用优先队列快速找出最值。

复杂度分析：

  • 时间复杂度：O(n2)O(n^2)

  • 空间复杂度：O(1)O(1)

稳定性: 算法不稳定，不管待排序序列是否有序，时间复杂度恒定不变。

插入排序

  • Approach 1: 逐个交换

    逐个向左比较，交换到合适位置，缺点是交换次数太多

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void insertionSort(vector<int>& nums) {
        int N = nums.size();

        for (int i = 1; i < N; i++) {
            for (int j = i; j > 0 && nums[j - 1] > nums[j]; j--) {
                swap(nums[j - 1], nums[j]);
            }
        }
    }

  • Approach 2: 逐个赋值

    先暂存，前面比暂存元素严格小的元素逐个后移，只有比较和赋值，没有交换操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void insertionSort(vector<int>& nums) {
        int N = nums.size();

        for (int i = 1; i < N; i++) {
            int x = nums[i];
            int j = i - 1;             /* j表示已排序元素中最后一个不大于x的位置 */

            while (j >= 0 && nums[j] > x) {
                nums[j + 1] = nums[j];
                j--;
            }

            nums[j + 1] = x;
        }
    }

总结：

  • 优点：

    • 插入排序作用在接近有序的数组上效果较好。

    • 插入排序作用在规模较小的数组上效果较好。

  • 缺点：

    • 数值很小的元素排在很后面
    • 数值很大的元素排在很前面

  • 高级排序算法的底层会转向使用插入排序。

在绝大多数情况下，插入排序应用长度为6到16之间的任意值的排序任务上面都能令人满意。
——《Algorithms(4th Edition)》

复杂度分析：

  • 时间复杂度：O(n2)O(n^2)

  • 空间复杂度：O(1)O(1)

稳定性: 算法稳定。

希尔排序

本质：分组插入排序、带间隔的插入排序

利用了插入排序的优点，回避了插入排序的缺点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void shellSort(vector<int>& nums) {
    int len = nums.size();
    for (int delta = len / 2; delta > 0; delta /= 2) {
        for (int start = 0; start < delta; start++) {
            // 分组插入排序
            for (int i = start + delta; i < len; i += delta) {
                int temp = nums[i];
                int j;
                for (j = i; j - delta >= 0 && nums[j - delta] > temp; j -= delta) {
                    nums[j] = nums[j - delta];
                }
                nums[j] = temp;
            }
        }
    }
}

复杂度分析：

  • 时间复杂度：与选择的步长序列有关

  • 空间复杂度：O(1)O(1)

稳定性: 算法不稳定。

高级排序算法

快速排序

基本思想：分而治之

  1. 单路快排

  • 第一个数组元素作为pivot

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    void quickSort(vector<int>& nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int index = partition(nums, left, right);
        quickSort(nums, left, index - 1);
        quickSort(nums, index + 1, right);
    }

    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[left];
        int j = left;                       /* j表示小于等于pivot区间的最后一个元素 */
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] <= pivot) {        /* 大放过，小向前 */
                j++;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[left], nums[j]);
        return j;
    }

  • 最后一个数组元素作为pivot

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    void quickSort(vector<int>& nums, int lo, int hi) {
        if (lo >= hi) return;
        int index = partition(nums, lo, hi);
        quickSort(nums, lo, index - 1);
        quickSort(nums, index + 1, hi);
    }
      
    int partition(vector<int>& nums, int lo, int hi) {
        int pivot = nums[hi];
        int j = lo - 1;                    /* j表示小于等于pivot区间的最后一个元素 */
        for (int i = lo; i < hi; i++) {
            if (nums[i] <= pivot) {        /* 大放过，小向前 */
                j++;
                swap(nums[j], nums[i]);
            }
        }
        swap(nums[j + 1], nums[hi]);
        return j + 1;
    }

优化思路：

partition操作在「顺序数组」和「逆序数组」上表现很差，这一点与插入排序相反。理想快速排序类似于递归树平衡，每次划分完元素的最终位置尽可能靠中间。因此我们可以随机选择pivot元素，打破顺序性。但是随机选择切分元素还会遇到一些问题，例如数组中存在多元素值相同，这样随机选择就没有意义，如何处理值相同的元素又成为了一个问题，所以有了以下两种方法来解决这种问题。

  1. 双路快排

把与pivot相等的元素平均地放到数组的两侧

  • Approach 1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    void quickSort(vector<int>& nums, int lo, int hi) {
        if (lo >= hi) return;
        int index = partition(nums, lo, hi);
        quickSort(nums, lo, index - 1);
        quickSort(nums, index + 1, hi);
    }

    int partition(vector<int>& nums, int lo, int hi) {
        srand((unsigned) time(NULL));
        int randomIndex = lo + rand() % (hi - lo + 1);
        swap(nums[lo], nums[randomIndex]);
        int pivot = nums[lo];

        int le = lo + 1;            /* [lo+1, le) */
        int ge = hi;                /* (ge, hi] */

        while (true) {
            while (le <= hi && nums[le] < pivot) le++;
            while (ge >= lo && nums[ge] > pivot) ge--;
            if (le >= ge) break;
            swap(nums[le++], nums[ge--]);
        }
        swap(nums[lo], nums[ge]);
        return ge;
    }

  • Approach 2:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    void quickSort(vector<int>& nums, int lo, int hi) {
        if (lo >= hi) return;
        int pivot_index = partition(nums, lo, hi);
        quickSort(nums, lo, pivot_index - 1);
        quickSort(nums, pivot_index + 1, hi);

    }

    int partition(vector<int>& nums, int lo, int hi) {
        srand((unsigned) time(NULL));
        int randomInt = lo + rand() % (hi - lo + 1);
        swap(nums[lo], nums[randomInt]);

        int i = lo;                  /* i表示等于pivot元素区间的第一个位置 */ 
        int j = hi + 1;              /* j表示严格大于pivot区间的第一个元素的位置 */
        int pivot = nums[lo];
        while(true) {
            while (nums[++i] < pivot) if (i == hi) break;
            while (nums[--j] > pivot) if (j == lo) break;
            if (i >= j) break;
            swap(nums[i], nums[j];)
        }
        swap(nums[lo], nums[j]);
        return j;
    }

    From 《Algorithms, 4th Edition》

  1. 三路快排

把与pivot相等的元素挤到中间

  • Approach 1: 交换的同时处理pivot元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    void quickSort(vector<int>& nums, int lo, int hi) {
        if (lo >= hi) return;

        srand((unsigned) time(NULL));
        int randomIndex = lo + rand() % (hi - lo + 1);
        swap(nums[lo], nums[randomIndex]);

        int pivot = nums[lo];

        int lt = lo;                /* lt表示严格小于pivot元素区间的后一个位置 */
        int gt = hi;                /* gt表示严格大于pivot元素区间的前一个位置 */
        int i = lo + 1;

        while (i <= gt) {
            if (nums[i] < pivot) {
                swap(nums[lt++], nums[i++]);
            } else if (nums[i] > pivot) {
                swap(nums[i], nums[gt--]);
            } else {
                i++;
            }
        }

        quickSort(nums, lo, lt - 1);
        quickSort(nums, gt + 1, hi);   
    }

  • Approach 2: 先处理其它元素，最后交换pivot

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    void quickSort(vector<int>& nums, int lo, int hi) {
        if (lo >= hi) return;

        srand((unsigned) time(NULL));
        int randomIndex = lo + rand() % (hi - lo + 1);
        swap(nums[lo], nums[randomIndex]);
        
        int pivot = nums[lo];
        
        int lt = lo + 1;
        int gt = hi;
        int i = lo + 1;

        while (i <= gt) {
            if (nums[i] < pivot) {
                swap(nums[lt++], nums[i++]);
            } else if (nums[i] == pivot) {
                i++;
            } else {
                swap(nums[i], nums[gt--]);
            }
        }
        swap(nums[lo], nums[lt - 1]);
        quickSort(nums, lo, lt - 2);
        quickSort(nums, gt + 1, hi);
    }

三路快排针对存在大量重复的pivot元素

复杂度分析：

  • 时间复杂度：O(nlogn)O(nlogn)

  • 空间复杂度：O(nlogn)O(nlogn)

稳定性: 算法不稳定，最快的排序算法。

归并排序

基本思想：分而治之，按照「深度优先遍历」的顺序「拆分子问题」与「组合子问题的解」

  • Approach 1: 合并的时候处理辅助数组，后处理待排序数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    void mergeSort(vector<int>& nums, int lo, int hi, vector<int>& aux) {
        if (lo >= hi) return;

        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, lo, mid, aux);
        mergeSort(nums, mid + 1, hi, aux);
        merge(nums, lo, mid, hi, aux);
    }

    void merge(vector<int>& nums, int lo, int mid, int hi, vector<int>& aux) {
        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i <= mid && (j > hi || nums[i] <= nums[j])) {
                aux[k] = nums[i++];
            } else {
                aux[k] = nums[j++];
            }
        }

        for (int k = lo; k <= hi; k++) {
            nums[k] = aux[k];
        }
    }

  • Approach 2: 先处理辅助数组，合并的时候处理待排序数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    void mergeSort(vector<int>& nums, int lo, int hi, vector<int>& aux) {
        if (lo >= hi) return;

        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, lo, mid, aux);
        mergeSort(nums, mid + 1, hi, aux);
        merge(nums, lo, mid, hi, aux);
    }

    void merge(vector<int>& nums, int lo, int mid, int hi, vector<int>& aux) {
        int i = lo;
        int j = mid + 1;
        
        for (int k = lo; k <= hi; k++) aux[k] = nums[k];

        for (int k = lo; k <= hi; k++) {
            if (i > mid)                   nums[k] = aux[j++];
            else if (j > hi)               nums[k] = aux[i++];
            else if (aux[j] < aux[i])      nums[k] = aux[j++];
            else                           nums[k] = aux[i++];
        }
    }

优化思路：

  • 在小区间使用插入排序

  • 合并之前判断数组是否已经有序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void mergeSort(vector<int>& nums, int lo, int hi, vector<int>& aux) {
    if (hi - lo < 16) {                            /* optimization 1 */
        insertionSort(nums, lo, hi);
        return;
    }

    int mid = lo + (hi - lo) / 2;
    mergeSort(nums, lo, mid, aux);
    mergeSort(nums, mid + 1, hi, aux);

    if (nums[mid] <= nums[mid + 1]) return;       /* optimization 2 */

    merge(nums, lo, mid, hi, aux);
}

void merge(vector<int>& nums, int lo, int mid, int hi, vector<int>& aux) {
    int i = lo;
    int j = mid + 1;
    
    for (int k = lo; k <= hi; k++) aux[k] = nums[k];

    for (int k = lo; k <= hi; k++) {
        if (i > mid)                   nums[k] = aux[j++];
        else if (j > hi)               nums[k] = aux[i++];
        else if (aux[j] < aux[i])      nums[k] = aux[j++];
        else                           nums[k] = aux[i++];
    }
}

void insertionSort(vector<int>& nums, int lo, int hi) {
    for (int i = lo + 1; i <= hi; i++) {
        int key = nums[i];
        int j;
        for (j = i; j > lo && nums[j - 1] > key; j--) {
            nums[j] = nums[j - 1];
        }
        nums[j] = key;
    }
}

复杂度分析：

  • 时间复杂度：O(nlogn)O(nlogn)

  • 空间复杂度：O(n)O(n)

稳定性: 算法稳定。

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void heapSort(vector<int>& nums) {
    int N = nums.size() - 1;

    for (int i = (N - 1) / 2; i >= 0; i--) {
        sink(nums, i, N);
    }

    while (N > 0) {
        swap(nums[0], nums[N--]);
        sink(nums, 0, N);
    }
}

void sink(vector<int>& nums, int k, int N) {
    while (k * 2 + 1 <= N) {
        int i = k * 2 + 1;
        if (i < N && nums[i] < nums[i + 1]) {
            i++;
        }
        if (nums[k] >= nums[i]) break;
        swap(nums[k], nums[i]);
        k = i;
    }
}

注意：

二叉树（堆）中，如果有效元素从下标0开始算起，位置为k的节点的父节点位置为⌊(k−1)/2⌊\lfloor (k - 1) / 2 \lfloor，而它的两个子节点的位置分别为2k+12k + 1和2k+22k + 2。

如果有效元素从下标0开始算起，二叉树（堆）中最后一个非孩子节点元素下标为⌊(length−1)/2⌋\lfloor(length - 1) / 2\rfloor

二叉树（堆）中，如果有效元素从下标1开始算起，位置为k的节点的父节点位置为⌊k/2⌊\lfloor k / 2 \lfloor，而它的两个子节点的位置分别为2k2k和2k+12k + 1。

复杂度分析：

  • 时间复杂度：O(nlogn)O(nlogn)

  • 空间复杂度：O(1)O(1)

稳定性: 算法不稳定。

非比较的排序算法

计数排序

feature: 数组中的元素都是正整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void countingSort(vector<int>& nums) {
    int k = *max_element(nums.begin(), nums.end());
    int n = nums.size();

    vector<int> count(k + 1, 0);
    vector<int> output(nums.size(), 0);

    for (int i = 0; i < n; i++)                     /* step1: 计数 */
        count[nums[i]]++;

    for (int i = 1; i < k + 1; i++)                /* step2: 统计小于等于nums[i]的元素个数 */
        count[i] += count[i - 1];

    for (int i = nums.size() - 1; i >= 0; i--)     /* step3: 将每个元素放到正确位置 */
        output[--count[nums[i]]] = nums[i];

    nums.assign(output.begin(), output.end());
}

Q&A:

  • count[nums[i]]表示小于等于nums[i]的元素个数，所以将nums[i]放到count[nums[i]] - 1的位置

  • nums[i]中可能存在多个相等的元素，所以取出nums[i]后需要将count[nums[i]]减1，使后面的元素能放到正确的位置上面

  • for循环从后往前遍历，是为了是值相等的元素也是从后往前放到最终的数组中，从而保证算法的稳定性

复杂度分析：

  • 时间复杂度：O(n+k)O(n + k)

  • 空间复杂度：O(k)O(k)，其中k表示元素的取值范围

稳定性: 算法稳定。

基数排序

桶排序

References:

[1] 《Algirithms, 4th Edition》第二章：排序

[2] 《算法不好玩》专题六：快速排序