十大排序总结

Posted on Edited on Symbols count in article: 11k Reading time ≈ 10 mins.

一、简单排序

1. 冒泡排序

  • 时间复杂度：O(N^2)
  • 空间复杂度：O(1)
  • 稳定 
    1
    2
    3
    4
    5
    6
    7
    8
    void bubbleSort(vector<int>& arr) {
        int n = arr.size();
        for (int i = 0; i < n - 1; ++i) {
            for (int j = 0; j < n - 1 - i; ++j) {
                if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
            }
        }
    }

2. 选择排序

  • 时间复杂度：O(N^2)
  • 空间复杂度：O(1)
  • 不稳定（是不是以为(arr[j] > arr[pos])改为>=就变成稳定的了？那看一下3, 2, 1, 2。所以若想选择排序稳定，需要开辟新的数组空间；或者进行大量移动位置操作；或者是对链表排序） 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void selectSort(vector<int>& arr) {
        int n = arr.size();
        for (int i = 0; i < n - 1; ++i) {
            int pos = 0;
            for (int j = 1; j < n - i; ++j) {
                if (arr[j] > arr[pos]) pos = j;
            }
            swap(arr[pos], arr[n - i - 1]);
        }
    }

3. 插入排序

  • 时间复杂度：O(N^2)
  • 空间复杂度：O(1)
  • 稳定 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void insertSort(vector<int>& arr) {
        int n = arr.size();
        for (int i = 1; i < n; ++i) {
            int cur = arr[i];
            int j = i - 1;
            for (; j >= 0 && arr[j] > cur; --j)
                arr[j + 1] = arr[j];
            arr[j + 1] = cur;
        }
    }

二、高级排序

4. 希尔排序

  • 时间复杂度：O(N^(4/3~3/2))复杂度非常难以估算
  • 空间复杂度：O(1)
  • 不稳定
  • 下面两个实现都一样，唯一区别就是插入排序外循环里面i增加的形式，第一种分开实现，第二种合并了

4.1 实现1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void shellSort(vector<int>& arr) {
    int n = arr.size();
    // 选择的增量序列是（2^k-1），可以跟随数组大小生成，但是为了简化算法代码，突出主题，在此固定长度了
    static vector<int> incre = { 1023, 511, 255, 127, 63, 31, 15, 7, 3, 1 };
    for (int u = 0; u <incre.size(); ++u) { // 增量循环
        int width = incre[u];
        if (width > n) continue;
        for (int v = 0; v < width; ++v) { // 当前增量循环
            for (int i = width + v; i < n; i += width) { // 插入排序外循环
                int cur = arr[i];
                int j = i - width;
                for (; j >= 0 && arr[j] > cur; j -= width) // 插入排序内循环
                    arr[j + width] = arr[j];
                arr[j + width] = cur;
            }
        }
    }
}

4.2 实现2（浙大陈姥姥代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void shellSort(vector<int>& arr) {
    int n = arr.size();
    // 选择的增量序列是（2^k-1），可以跟随数组大小生成，但是为了简化算法代码，突出主题，在此固定长度了
    static vector<int> incre = { 1023, 511, 255, 127, 63, 31, 15, 7, 3, 1 };
    for (int u = 0; u < incre.size(); ++u) { // 增量循环
        int width = incre[u];
        for (int i = width; i < n; ++i) { // 插入排序外循环
            int cur = arr[i];
            int j = i - width;
            for (; j >= 0 && arr[j] > cur; j -= width) // 插入排序内循环
                arr[j + width] = arr[j];
            arr[j + width] = cur;
        }
    }
}

5. 堆排序

  • 时间复杂度：O(NlogN)
  • 空间复杂度：O(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 downMethod(vector<int>& arr, int f, int sz) {
        int s = f * 2 + 1;
        int cur = arr[f];
        while(s < sz){
            if (s + 1 < sz && arr[s] < arr[s + 1]) // 兄弟值大，让位
                ++s;
            if (arr[s] <= cur) break; // 父亲值大，镇压
            arr[f] = arr[s]; // 儿子值大，禅位
            f = s; // 下一代的父亲
            s = f * 2 + 1; // 下一代的儿子
        }
        arr[f] = cur;
    }

    void heapSort(vector<int>& arr) {
        int n = arr.size();
        // 数组形成堆
        for (int p = (n - 2) / 2; p >= 0; --p)
            downMethod(arr, p, n);
        // 堆首尾交换进行排序
        for (int p = n-1; p > 0; --p) {
            swap(arr[0], arr[p]);
            downMethod(arr, 0, p);
        }
    }

6. 归并排序

  • 时间复杂度：O(NlogN)
  • 空间复杂度：O(N)
  • 稳定

6.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
26
27
28
29
// [l, m] [m+1, r]
void mergeTwoArray(vector<int>& arr, vector<int>& trr, int l, int m, int r) {
    int i = l, j = m + 1, k = l;
    while (i <= m || j <= r) { // k <= r 一样
        int a = i <= m ? arr[i] : INT_MAX;
        int b = j <= r ? arr[j] : INT_MAX;
        if (a < b) ++i; // 每次i和j只能有一个增加
        else ++j;
        trr[k++] = a < b ? a : b;
    }
    while (l <= r) { // 拷贝回去
        arr[l] = trr[l];
        ++l;
    }
}

void mergeRecursion(vector<int>& arr, vector<int>& trr, int l, int r) {
    if (l == r) return;
    int m = l + ((r - l) >> 1);
    mergeRecursion(arr, trr, l, m);
    mergeRecursion(arr, trr, m + 1, r);
    mergeTwoArray(arr, trr, l, m, r);
}

void mergeSort(vector<int>& arr) {
    int n = arr.size();
    vector<int> trr(arr); // 避免频繁创建子数组
    mergeRecursion(arr, trr, 0, n - 1);
}

6.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
26
27
28
29
30
31
32
33
34
35
36
// [l, m] [m+1, r]
void mergeTwoArray(vector<int>& arr, vector<int>& trr, int l, int m, int r) {
    int i = l, j = m + 1, k = l;
    while (i <= m || j <= r) { // k <= r 一样
        int a = i <= m ? arr[i] : INT_MAX;
        int b = j <= r ? arr[j] : INT_MAX;
        if (a < b) ++i; // 每次i和j只能有一个增加
        else ++j;
        trr[k++] = a < b ? a : b;
    }
    // 不用拷贝回去...
}

void mergeSort(vector<int>& arr) {
    int n = arr.size();
    int range = 1; // 半径
    vector<int> trr(arr); // 避免频繁创建子数组
    while (range < n) {
        for (int i = 0; i < n; i += range*2) { // arr -> trr
            int m = i + range - 1;
            if (m >= n - 1) m = n - 1; // 不能break
            int r = i + range * 2 - 1;
            if (r >= n - 1) r = n - 1;
            mergeTwoArray(arr, trr, i, m, r); // arr->trr
        }
        range <<= 1;
        for (int i = 0; i < n; i += range*2) { // trr -> arr
            int m = i + range - 1;
            if (m >= n - 1) m = n - 1; // 不能break
            int r = i + range * 2 - 1;
            if (r >= n - 1) r = n - 1;
            mergeTwoArray(trr, arr, i, m, r); // trr->arr
        }
        range <<= 1;
    }
}

7. 快速排序

  • 时间复杂度：O(NlogN)
  • 空间复杂度：栈上O(logN)
  • 不稳定
  • 注意1：遇到l和r指向相等时，需要交换，不然遇到全1的数组，退化为n^2
  • 注意2：快排在数据范围较小时（r-l<threshold）直接使用插入排序可有效优化速度

7.1 实现1（朴素版）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void quickRecursion(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int oldl = l, oldr = r;
    // 选 [枢纽]
    int pivot = arr[l];
    // 排序
    ++r;
    while (l < r) {
        while (l < r && arr[--r] > pivot); // 右侧先动是安全的
        while (l < r && arr[++l] < pivot); // 左侧后动
        if (l < r) swap(arr[l], arr[r]);
    }
    swap(arr[oldl], arr[l]);
    quickRecursion(arr, oldl, r - 1);
    quickRecursion(arr, r + 1, oldr);
}

void quickSort(vector<int>& arr) {
    int n = arr.size();
    quickRecursion(arr, 0, n - 1);
}

7.2 实现2（改进朴素版）

1
2
3
4
5
int pivot = arr[l];
// 改为
int randomPos = l + rand()%(r-l+1);
swap(arr[l], arr[randomPos]);
int pivot = arr[l];

7.3 实现3（中间值枢纽）

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
// 三数选中间数并将最小值放在l，最大值放在r，中间值(pivot)放在l+1
// 陈姥姥代码里是放在r-1的，这样肯定正确因为m肯定<r
// 我为了兼容朴素版的大部分代码，选择放在l+1，这样由于m可能等于l，所以需要多一次特殊点判断
int median3(vector<int>& arr, int l, int r) {
    int m = l + ((r - l) >> 1);
    if (arr[l] > arr[m])
        swap(arr[l], arr[m]);
    if (arr[l] > arr[r])
        swap(arr[l], arr[r]);
    if (arr[m] > arr[r])
        swap(arr[m], arr[r]);
    if (l == m) return arr[l]; // 特殊点
    swap(arr[m], arr[l + 1]);
    return arr[l + 1];
}

void quickRecursion(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int oldl = l, oldr = r;
    // 选 [枢纽]
    int pivot = median3(arr, l, r);

    // 排序
    ++l; // 注意：两端收缩了一位
    while (l < r) {
        while (l < r && arr[--r] > pivot); // 右侧先动是安全的
        while (l < r && arr[++l] < pivot); // 左侧后动
        if (l < r) swap(arr[l], arr[r]);
    }
    swap(arr[oldl + 1], arr[l]); // 注意：pivot枢纽放在了l+1位置
    quickRecursion(arr, oldl, r - 1);
    quickRecursion(arr, r + 1, oldr);
}

void quickSort(vector<int>& arr) {
    int n = arr.size();
    quickRecursion(arr, 0, n - 1);
}

7.4 实现4（有限制）

虽然代码看起来很简洁，但是有如下问题： 1. 极端情况会退化为n^2算法 2. 正因如此，在我的实验中，对3w个分布0~99的数字排序，会栈溢出（异常结束，main函数return 非0）。其实前面的方法里，移动i和j时如果>改为>=、<改为<=也会出现这种问题哦。因此在数据分布较窄时，这种方法无疑是低效的 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void quickRecursion(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    // 选 [枢纽] 可改进随机化但效果还是差
    int pivot = arr[l];

    // 排序
    int j = l;
    for (int i = l + 1; i <= r; ++i) {
        if (arr[i] < pivot) {
            ++j;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[j], arr[l]);

    quickRecursion(arr, l, j - 1);
    quickRecursion(arr, j + 1, r);
}

void quickSort(vector<int>& arr) {
    int n = arr.size();
    quickRecursion(arr, 0, n - 1);
}

三、特殊排序

8. 计数排序

  • 时间复杂度：O(B+N)，B是数据范围一般较小，可认为是O(N)
  • 空间复杂度：栈上O(B+N) -> O(N)
  • 稳定（实现的不好则不稳定，比如从前往后填） 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void countingSort(vector<int>& arr) {
        int n = arr.size();
        int maxV = INT_MIN;
        for (auto& e : arr) maxV = maxV > e ? maxV : e;
        vector<int> counting(maxV + 1); // 计数数组
        vector<int> trr(arr); // 留作中转拷贝
        for (auto& e : arr) ++counting[e]; // 计数
        for (int i = 1; i < counting.size(); ++i) // 累加计数
            counting[i] = counting[i - 1] + counting[i];
        for (int i = n - 1; i >= 0; --i) { // 从后向前填：稳定的排序
            int pos = --counting[arr[i]];
            trr[pos] = arr[i];
        }
        for (int i = 0; i < n; ++i) // 拷回去
            arr[i] = trr[i];
    }

9. 基数排序

  • 时间复杂度：O(Rs * N)，Rs是数据最大值的位数一般较小，可认为是O(N)
  • 空间复杂度：栈上O(10 + N) -> O(N)
  • 稳定（实现的不好则不稳定，比如从前往后填）
  • 经常利用计数排序实现

9.1 LSD基数排序

  1. 最低位优先(Least Significant Digit first, LSD)，先排低位；再排高位
  2. 由于每一位介于0~9，所以对每一个基位排序时都可看做是分为10个桶的桶排序 
    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
    // 获得一个int的某一位的数字
    // 例如13247 r=0 -> 7 | r=1 -> 4 | r=2 -> 2 | r=3 -> 3 | r=4 -> 1 | r = 5 -> 0 
    int getRadix(int num, int r) {
        static int radices[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
        num %= radices[r + 1];
        return num / radices[r];
    }

    void radixSortLSD(vector<int>& arr) {
        int n = arr.size();
        int maxV = INT_MIN;
        for (auto& e : arr) maxV = maxV > e ? maxV : e;
        int radixNum = 0;
        while (maxV) {
            ++radixNum;
            maxV /= 10;
        }
        vector<int> trr(arr); // 留作中转拷贝
        for (int r = 0; r < radixNum; ++r) {
            vector<int> counting(10); // 计数数组
            for (auto& e : arr) ++counting[getRadix(e, r)]; // 计数
            for (int i = 1; i < counting.size(); ++i) // 累加计数
                counting[i] = counting[i - 1] + counting[i];
            for (int i = n - 1; i >= 0; --i) {
                int pos = --counting[getRadix(arr[i], r)];
                trr[pos] = arr[i];
            }
            for (int i = 0; i < n; ++i) // 拷回去
                arr[i] = trr[i];
        }
    }

9.2 MSD基数排序

  • 最高位优先(Most Significant Digit first, MSD)，先排高位；再排低位
  • MSD一般采用递归写法：按高位分组，形成连续区段，然后在区段内递归处理低一位 
    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
    // 获得一个int的某一位的数字
    // 例如13247 r=0 -> 7 | r=1 -> 4 | r=2 -> 2 | r=3 -> 3 | r=4 -> 1 | r = 5 -> 0 
    int getRadix(int num, int r) {
        static int radices[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
        num %= radices[r + 1];
        return num / radices[r];
    }

    void radixRecursion(vector<int>& arr, vector<int>& trr, int l, int r, int d) {
        if (l >= r || d < 0) return;
        vector<int> counting(10);
        for (int i = l; i <= r; ++i) 
            ++counting[getRadix(arr[i], d)]; // l~r 计数
        for (int i = 1; i < counting.size(); ++i) 
            counting[i] = counting[i - 1] + counting[i]; // 累加计数
        for (int i = r; i >= l; --i) {
            int pos = --counting[getRadix(arr[i], d)] + l; // + l 偏移别忘了
            trr[pos] = arr[i];
        }
        for (int i = l; i <= r; ++i) // 拷回去
            arr[i] = trr[i];
        for (int i = 0; i < 10; ++i) {
            if (i == 0) radixRecursion(arr, trr, l, l + counting[0] - 1, d - 1);
            else radixRecursion(arr, trr, l + counting[i - 1], l + counting[i] - 1, d - 1);
        }
    }

    void radixSortMSD(vector<int>& arr) {
        int n = arr.size();
        int maxV = INT_MIN;
        for (auto& e : arr) maxV = maxV > e ? maxV : e;
        int radixNum = 0;
        while (maxV) {
            ++radixNum;
            maxV /= 10;
        }
        vector<int> trr(arr); // 留作中转拷贝
        radixRecursion(arr, trr, 0, n - 1, radixNum-1);
    }

10. 桶排序

  • 桶排序的时间复杂度和空间复杂度以及是不是稳定都看你采取的子排序算法
  • 桶排序一般用于数据分布均匀的
  • 桶排序用于遏制N^2、NlogN等复杂度的算法因数据量太大而带来的速度问题 
    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
    void insertSort(vector<int>& arr) {
        int n = arr.size();
        for (int i = 1; i < n; ++i) {
            int cur = arr[i];
            int j = i - 1;
            for (; j >= 0 && arr[j] > cur; --j)
                arr[j + 1] = arr[j];
            arr[j + 1] = cur;
        }
    }

    void bucketSort(vector<int>& arr) {
        int n = arr.size();
        int maxV = INT_MIN;
        for (auto& e : arr) maxV = maxV > e ? maxV : e;
        ++maxV;
        int bckNum = 10; // 分十个桶
        vector<vector<int>> buckets(bckNum, vector<int>());
        for (auto& e : arr) {
            int pos = e * 10 / maxV;
            buckets[pos].push_back(e); // 放进桶里
        }
        for (auto& b : buckets) { // 随意选取排序算法
            insertSort(b);
        }
        int k = 0;
        for (int i = 0; i < buckets.size(); ++i)
            for (int j = 0; j < buckets[i].size(); ++j)
                arr[k++] = buckets[i][j]; // 从桶里面拿出来
    }

四、辅助代码

  • 获取数据、判断排序合格、显示已排序frontN等 
    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
    40
    #pragma once
    #include <iostream>
    #include <vector>
    #include <fstream>
    #include <string>
    using namespace std;

    class Data{
    public:
        Data(string fn, int _n) : arr(_n) {
            fstream file;
            file.open(fn, ios::in);
            if (!file) {
                throw string("ERROR!");
            }
            for (auto& e : arr)
                file >> e;
            file.close();
        }
        vector<int>&& getData() { return move(arr); }
    private:
        vector<int> arr;
    };

    bool isSorted(vector<int>& arr) {
        for (int i = 1; i < arr.size(); ++i)
            if (arr[i] < arr[i - 1]) return false;
        return true;
    }

    void showFrontN(vector<int>& arr, int n) {
        n = n > arr.size() ? arr.size() : n;
        for (int i = 0; i < n;) {
            int cnt = 0;
            for (; cnt < 10 && i + cnt < n; ++cnt) // 每行十列显示
                cout << arr[i + cnt] << "\t";
            cout << endl;
            i += cnt;
        }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int main() {
        Data dataGenerator("Data.txt", 1000);
        vector<int> arr = dataGenerator.getData();

        // yourSort(arr);
        showFrontN(arr, 100);

        if (isSorted(arr)) cout << "排序完成" << endl;
        else cout << "排序出错" << endl;
        return 0;
    }