[面试算法题模板]排序算法总结

2021-03-23 本文已影响0人闭门造折

一、引子

在面试的时候，很常见的是给你出一两道简单的算法题，让你去实现。或是直接说

“同学你对XX排序了解多少？”

当你叭叭叭回答完了之后，考官面带笑容，推过来一张纸

那你能实现一下吗？

所以今天打算把常考的排序算法总结一下，并且提供一两个模板，以供之后复习使用。

二、基本性质

排序算法	最好时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	$O(N)$	$O(N^2)$	$O(N^2)$	$O(1)$	稳定
选择排序	$O(N^2)$	$O(N^2)$	$O(N^2)$	$O(1)$	不稳定
插入排序	$O(N)$	$O(N^2)$	$O(N^2)$	$O(1)$	稳定
希尔排序	$O(N)$	$O(N^{1.3})$	$O(N^2)$	$O(1)$	不稳定
快速排序	$O(NlogN)$	$O(NlogN)$	$O(N^2)$	$O(logN - N)$	不稳定
归并排序	$O(NlogN)$	$O(NlogN)$	$O(NlogN)$	$O(n)$	稳定
堆排序	$O(NlogN)$	$O(NlogN)$	$O(NlogN)$	$O(1)$	不稳定
基数排序	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	$O(rd+n)$	稳定

r代表关键字基数，d代表长度，n代表关键字个数

三、冒泡排序

3.1 冒泡排序你了解吗？

答：冒泡排序的原理是（以升序为例）：比较相邻的两个元素，如果前一个数比后一个数大，将二者交换。

3.2 冒泡排序时间复杂度怎么算？

答：冒泡排序每轮交换结束后，可以最少使得一个数字达到有序，因此最多执行 $n-1$ 轮后，一定可以排好序。最差时间复杂度 $O(N^2)$ 。

添加 $flag$ 判断后，执行第一轮时，发现已经全局有序，直接跳出循环。因此最好时间复杂度为 $O(N)$ 。

平均时间复杂度为 $O(\frac{N^2}{2})$ = $O(N^2)$

3.3 冒泡排序空间复杂度多少？

答：仅需要常数个临时变量，用于交换前后两数字时使用。因此空间复杂度为 $O(1)$

3.4 冒泡排序稳定吗？

答：是稳定的。

稳定与否指的是如果数组中有相同的元素，那么排序后有没有可能，在最终结果中，原始数组中不同索引的相同元素的顺序是不固定的。
这里比较拗口，但是我们可以这样理解，一个数组[1,2,5,5,4]，有两个数字5，我们认为它们是不同的，不妨假设为[1,2, $5_1$ , $5_2$ ，4]。用两个不同下标，区分这两个5。假设排序后有可能得到[1,2,4, $5_1$ , $5_2$ ]，也可能得到[1,2,4,, $5_2$ , $5_1$ ]，那么我们认为这种排序是不稳定的。如果有且只有一种排序后结果，则说明该排序是稳定的。

由于冒泡排序排序过程中，最多两两交换位置，且相同元素遇到一起时，不会交换位置。因此最终排序结束后，原本索引在前的相等元素，排序后索引仍在前。即满足稳定的定义。

3.5 你能写一个冒泡排序吗？

// 假设数组arr做排序, len表示数组长度
bool flag = true; // 用于剪枝，排序好后提前结束
for(int i = 0; i < len - 1 && flag; i++){
    flag = false;
    // 注意这里j要反着遍历
    // 这样每轮结束后，当轮最小值将被放在arr[i]中
    // 并在之后轮中都不再参与排序
    for(int j = arr.size() - 1; j > i; j--){
        if(arr[j - 1] > arr[j]){
            flag = true;
            int tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
        }
    }
}

四、选择排序

4.1 选择排序你了解吗？

答：每一轮找到最小的元素，和第一个位置的元素做交换。然后每一轮都不再考虑之前放置好的位置。

4.2 选择排序时间复杂度怎么算？

答：每一轮选最小元素的时候，是 $O(N)$ 寻找的，每个位置都要执行一遍，也是 $O(N)$ 的，因此无论最优、平均、还是最好，都是不变的 $O(N^2)$

4.3 选择排序空间复杂度多少？

答：没什么需要额外存的，每轮会储存一个最小元素，需要 $O(1)$ 的空间。

4.4 选择排序稳定吗？

答：不是稳定的。

稳定与否指的是如果数组中有相同的元素，那么排序后有没有可能，在最终结果中，原始数组中不同索引的相同元素的顺序是不固定的。
这里比较拗口，但是我们可以这样理解，一个数组[1,2,5,5,4]，有两个数字5，我们认为它们是不同的，不妨假设为[1,2, $5_1$ , $5_2$ ，4]。用两个不同下标，区分这两个5。假设排序后有可能得到[1,2,4, $5_1$ , $5_2$ ]，也可能得到[1,2,4,, $5_2$ , $5_1$ ]，那么我们认为这种排序是不稳定的。如果有且只有一种排序后结果，则说明该排序是稳定的。

选择排序每一步中，会先选择一个最小值，和第一个数做交换。这里可能导致一些原有的潜在关系被破坏。比方说[1,2, $5_1$ , $5_2$ ，4]，第三轮中，我们想把4放在第三个位置，就需要交换 $5_1$ 和4，并得到一个结果[1,2,4,, $5_2$ , $5_1$ ]，忽略角标来看，数组已经有序了，但是原有的位置顺序被破坏了，所以我们认为选择排序不稳定。

4.5 你能写一个选择排序吗？

// 假设数组arr做排序, len表示数组长度
for(int i = 0; i < len - 1; i++){
    // 找到局部最小值对应索引
    int minIndex = i;
    for(int j = i + 1; j < len; j++){
        if(arr[j] < arr[minIndex]){
            minIndex = j;
        }
    }
    // 将最小值和开头元素交换
    if(minIndex != i){
        int tmp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = tmp;
    }
}

五、插入排序

5.1 插入排序你了解吗？

答：维护一个已经排好序的数组。每次取一个新的值，找到应该插入的位置，然后把新的值放进去。找位置的时候，是逆序寻找的（原因见5.2）。

5.2 插入排序时间复杂度怎么算？

答：每次寻找插入位置，需要 $O(N)$ 的时间。其实这里做题多的朋友一看就知道，可以用二分优化到 $O(logN）$ ，但是插入排序最基础的就是 $O(N)$ 的方法。我们就用 $O(N)$ 来讨论。总共 $N$ 个数，因此，共需要执行 $O(N)$ 轮。总共的时间复杂度是 $O(N^2)$

最坏情况是一开始数组是单减的，那么每次都需要逆序找到开头，才知道原来应该放在数组开头，需要 $O(N)$ 时间来查找位置；并且还需要用 $O(N)$ 时间来做插入后的移动（所有值往后挪一位），最坏时间复杂度为 $O(N^2)$

最好的情况，数组一开始就是单增的，逆序判断，需要 $O(1)$ 时间来查找位置，用 $O(1)$ 时间来插入后的移动(不需要移动)，最好时间复杂度为 $O(N)$

引申问题：为什么要逆序寻找。个人理解是这样的：
假设我们顺序寻找，那么对于一个一开始就升序的数组，每个新的值进来的时候，都需要 $O(N)$ 时间来查找位置，然后用 $O(1)$ 时间来插入后的移动（不需要任何移动）。总的时间复杂度是 $O(N^2)$
而对于一开始就降序的数组，每个新的值进来的时候，都需要 $O(1)$ 时间来查找位置，但是需要用 $O(N)$ 时间来插入后的移动（所有值往后挪一位）。总的时间复杂度是 $O(N^2)$
而如果逆序的话，按照上面所说，最好情况下，时间复杂度是 $O(N)$ ，比正序要小。

5.3 插入排序空间复杂度多少？

答：插入排序需要一个额外的空间来做挪移操作，所以空间复杂度为 $O(1)$

5.4 插入排序稳定吗？

答：是稳定的。

稳定与否指的是如果数组中有相同的元素，那么排序后有没有可能，在最终结果中，原始数组中不同索引的相同元素的顺序是不固定的。
这里比较拗口，但是我们可以这样理解，一个数组[1,2,5,5,4]，有两个数字5，我们认为它们是不同的，不妨假设为[1,2, $5_1$ , $5_2$ ，4]。用两个不同下标，区分这两个5。假设排序后有可能得到[1,2,4, $5_1$ , $5_2$ ]，也可能得到[1,2,4,, $5_2$ , $5_1$ ]，那么我们认为这种排序是不稳定的。如果有且只有一种排序后结果，则说明该排序是稳定的。

由于是逆序搜索插入位置，因此后来的同等值，必定处于后方。整体算法是稳定的。

5.5 你能写一个插入排序吗？

// 假设数组arr做排序, len表示数组长度
for(int i = 0; i < len - 1; i++){
    for(int j = i + 1; j > 0; j--){
        // 从后往前尝试放置，直到到正确位置
        if(arr[j - 1] > arr[j]){
            int tmp = arr[j - 1];
            arr[j - 1] = arr[j];
            arr[j] = tmp;
        }
        else{
            break;
        }
    }
}

六、希尔排序

喜欢图解的朋友可以移步这篇博客《排序算法之希尔排序》，里面绘制的非常清晰易懂。这个也不错《理解希尔排序的排序过程》

6.1 希尔排序你了解吗？

答：希尔排序是优化版本的插入排序，我们知道在插入排序过程中，最高需要 $O(N)$ 的时间，来寻找插入位置及移动需要插入的项。希尔排序的思想是，首先按照 n/2 的步长，把数组分为 n/2 组，组内执行插入排序。然后再按照 n/4 的步长分成 n/4 组，组内执行插入排序。这样一直减少步长，直到最终变成1组。

举个例子，假设此时步长是3，那么arr[0]需要和arr[3]，arr[6]等数做比较，并把排序后结果依次放在arr[0], arr[3], arr[6]中。

6.2 希尔排序时间复杂度怎么算？

答：希尔排序的时间复杂度实际上是 $O(N^s)$ 这里的 $s \in [1,2)$ ，具体的证明太数学了，可以看这篇知乎介绍《究竟是怎么打破二次时间屏障的？浅谈希尔排序的思想和复杂度证明》

Hibbard提出了著名的Hibbard增量：1, 3, 7, ..., $2^k-1$ 。使用这个增量的希尔排序最坏运行时间是 $O(N^{3/2})$

6.3 希尔排序空间复杂度多少？

答：希尔排序实际上是变种的插入排序，同样只需要一个额外空间做交换就够了，因此空间复杂度是 $O(1)$

6.4 希尔排序稳定吗？

答：不是稳定的。

稳定与否指的是如果数组中有相同的元素，那么排序后有没有可能，在最终结果中，原始数组中不同索引的相同元素的顺序是不固定的。
这里比较拗口，但是我们可以这样理解，一个数组[1,2,5,5,4]，有两个数字5，我们认为它们是不同的，不妨假设为[1,2, $5_1$ , $5_2$ ，4]。用两个不同下标，区分这两个5。假设排序后有可能得到[1,2,4, $5_1$ , $5_2$ ]，也可能得到[1,2,4,, $5_2$ , $5_1$ ]，那么我们认为这种排序是不稳定的。如果有且只有一种排序后结果，则说明该排序是稳定的。

希尔排序中，根据划分尺度的不同，可能导致原本有序的数字在组内移动，使得排序不再稳定。

6.5 你能写一个希尔排序吗？

// 假设数组为arr
for(int gap = arr.size() / 2; gap > 0; gap /= 2;){
    // 当前正处理第i个数字
    for(int i = gap; i < arr.size(); i++){
        for(int j = i; j >= gap; j -= gap){
            // 插入排序
            if(arr[j] > arr[j - gap]){
                swap(arr[j], arr[j - gap]);
            }
            else{
                break;
            }
        }
    }
}

七、快速排序

7.1 快速排序你了解吗？

答：从数组中选出一个数，比他小的统统放到他左边，比他大的统统放到他右边。此时把整个数组分为了两部分，用分治的思想，递归排序两个子数组。

7.2 快速排序时间复杂度怎么算？

答：每次选取一个数字，将数组分为两部分的过程，时间复杂度是 $O(N)$ ，递归求解每个子部分的时候，时间复杂度是 $O(logN)$ （分治法时间复杂度）。

当整个数组排列很散乱的情况下，假设每次切分后，都能得到两个相等长度的子数组，那么最终的时间复杂度为 $O(logN)$ ，和平均时间复杂度相等。

当整个数组已经有序，而你的快排实现的时候，每次又是取第一个数字来做切分，那么你每一步都会切分得到一个长度为 0 的子数组，和一个长度为 $len-1$ 的子数组。共需要切分 $len$ 轮，最坏时间复杂度为 $O(N^2)$

7.3 怎么规避7.2中出现的问题？

答：问题实际上出在了，我们在快排中，每次都是取第一个数字来做切分，这里引入随机取数即可。

随机快排指的是，在每次选取切分的 $key$ 时，不再固定选择数组第一个元素，或数组最后一个元素，而改为取数组一个随机索引 $r$ 对应元素。
实现时也很简单，在每次选取 $key$ 的时候，找一个随机索引值，然后把这个元素和数组第一个元素交换位置，接着以他做划分。这样一来，大部分代码都可以复用简单的普通头部取数快排了。

7.4 快速排序空间复杂度多少？

答：最深递归几层，就用到了几个额外的变量来存临时变量，因此最优情况下空间复杂度为 $O(logN)$ ，最差情况下空间复杂度为 $O(N)$

7.5 快速排序稳定吗？

答：不是稳定的。

稳定与否指的是如果数组中有相同的元素，那么排序后有没有可能，在最终结果中，原始数组中不同索引的相同元素的顺序是不固定的。
这里比较拗口，但是我们可以这样理解，一个数组[1,2,5,5,4]，有两个数字5，我们认为它们是不同的，不妨假设为[1,2, $5_1$ , $5_2$ ，4]。用两个不同下标，区分这两个5。假设排序后有可能得到[1,2,4, $5_1$ , $5_2$ ]，也可能得到[1,2,4,, $5_2$ , $5_1$ ]，那么我们认为这种排序是不稳定的。如果有且只有一种排序后结果，则说明该排序是稳定的。

快速排序每一步中，会选择一个数字做为基准元素，如果取到了不同位置相同的基准元素，可能最终排序数字上没有变化，但是相对顺序发生了改变，因此快速排序是不稳定的。

7.5 你能写一个快速排序吗？

挖坑法：不需要交换元素，每次直接赋值，参考资料《快速排序|菜鸟教程》，这个方法不能很方便的取任意位置做划分，想做的话需要把其他位置先和第一个元素做交换。

void quick_sort(vector<int>& arr, int left, int right){
    // 如果已经排好序，直接返回
    if(l >= r) return;
    int i = left;
    int j = right;
    int k = arr[left]; // 以第一个元素做划分
    // 这里相当于把left作为第一个坑位
    while(i < j){
        // 先从后往前找，找到第一个小于key值的，填进第一个坑里
        while(i < j && arr[j] >= k){
            j--;
        }
        // 把小于key值得项，填进坑i中，此时j形成新的坑位
        arr[i] = arr[j];
        //从前往后，找到第一个大于key的，填进j坑中
        while(i < j && arr[i] <= k){
            i++;
        }
        arr[j] = arr[i];
    }
    // 结束后，还剩下一个坑位，就是k的位置
    arr[i] = k;
    //递归排序子数组
    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
}

swap交换法：不用挖坑，每次把两个元素交换位置，省去了一步赋值。这个模板可以很方便地取任意位置来做划分。

void quick_sort(vector<int>& arr, int left, int right){
    // 如果已经排好序，直接返回
    if(l >= r) return;
    int i = left;
    int j = right;
    int k = arr[left]; // 以第一个元素做划分
    while(i < j){
        // 先从后往前找，找到第一个小于key值的，交换位置
        while(i < j && arr[j] >= k){
            j--;
        }
        swap(arr[i], arr[j]);
        //从前往后，找到第一个大于key的，交换位置
        while(i < j && arr[i] <= k){
            i++;
        }
        swap(arr[i], arr[j]);
    }
    //递归排序子数组
    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
}

竞赛模板：还参考这篇帖子《常用代码模板1——基础算法》找了一个不错的模板，这个模板可以很方便的取任意位置的元素作为划分。

void quick_sort(int a[], int l, int r) {
    if (l >= r) {
        return;
    }
    // 这里取的是数组中间元素，取其他的问题也不大
    int i = l, j = r, x = a[l + r >> 1];
    while (i < j) {
        do i ++ ; while(a[i] < x);
        do j -- ; while(a[j] > x);
        if (i < j) {
            swap(a[i], a[j]);
        }
    }
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}

八、归并排序

8.1 归并排序你了解吗？

答：基础思想是将大问题拆解为有关联的小问题求解。归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素或者2个序列，然后把各个有序的短序列合并成一个有序的长序列，不断合并直到原序列全部排好序。上述表达援引自《在快速排序、堆排序、归并排序中,什么排序是稳定的?_百度知道》

8.2 归并排序时间复杂度怎么算？

答：无论一开始数组排列如何，归并排序总是将大数组拆分成 $2$ 个小数组，分别排序后再执行归并，因此时间复杂度最好、平均、以及最坏情况下，都是拆分： $O(logN)$ ，合并： $O(N)$ ，总共 $O(NlogN)$

8.3 归并排序空间复杂度多少？

答：归并排序需要一个 $O(N)$ 长度的空间，用来做合并操作。

8.4 归并排序稳定吗？

答：是稳定的。

稳定与否指的是如果数组中有相同的元素，那么排序后有没有可能，在最终结果中，原始数组中不同索引的相同元素的顺序是不固定的。
这里比较拗口，但是我们可以这样理解，一个数组[1,2,5,5,4]，有两个数字5，我们认为它们是不同的，不妨假设为[1,2, $5_1$ , $5_2$ ，4]。用两个不同下标，区分这两个5。假设排序后有可能得到[1,2,4, $5_1$ , $5_2$ ]，也可能得到[1,2,4,, $5_2$ , $5_1$ ]，那么我们认为这种排序是不稳定的。如果有且只有一种排序后结果，则说明该排序是稳定的。

对于相同值的两个元素，如果被分在了左右不同的两个子区间中，则合并时仍然是索引值靠前的元素在前，因此满足稳定的定义。

8.5 你能写一个归并排序吗？

归并排序最重要的有两个过程：

分治排序
排序合并

void merge_sort(vector<int>& arr, int left, int right){
    // 区间较小或已排序，直接返回
    if(left >= right) return;
    // 这里采用left+的形式，而不采用(left + right) / 2
    // 是为了防止left + right超过限度。当然大部分情况下不会遇到
    int mid = left + (right - left) / 2;
    // 递归排序两个子数组
    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);
    // 现在对整个区域排序
    vector<int> tmp;
    // 双指针法
    int i = left;
    int j = mid + 1;
    while(i <= mid && j <= right){
        if(arr[i] <= arr[j]){
            tmp.push_back(arr[i]);
            i++;
        }
        else{
            tmp.push_back(arr[j]);
            j++;
        }
    }
    while(i <= mid) tmp.push_back(arr[i++]);
    while(j <= right) tmp.push_back(arr[j++]);
}

九、堆排序

9.1 堆排序你了解吗？

答：构建一颗完全二叉树，存储数组的值。如果是大顶堆，那么每个节点的值，都一定会大于等于他所有孩子节点的值。但如果没有亲缘关系，则节点间不一定有相互关系。

堆排序的基本思想是，构造这样一个大顶堆，然后不断取出头部的最大元素，把数组末尾元素放到头部，重新调整堆，不断完成交换、重建

大致步骤为：首先将无序数组，看成是一个大顶堆的前序遍历结果。则一个索引 $i$ 的元素对应的两个子孩子的索引分别是 $2i + 1$ 和 $2i + 2$ 。

然后以最后一个分叶子节点开始，判断该节点是否大于等于他的所有孩子节点的值：

如果满足：继续找到上一个非叶子节点。

如果不满足：交换该非叶节点最大的叶结点与该非叶节点。然后继续找到上一个非叶子节点。

上述操作后，会得到一个大顶堆，此时堆顶元素就是局部最大值

取出大顶堆最顶端元素，把大顶堆末尾元素放到开头，弹出数组最后一位。重新构建大顶堆

不断重复上述过程，即得到一个排序好的数组。

详细解答可以参看《图解排序算法(三)之堆排序》

9.2 堆排序时间复杂度怎么算？

答：建立大顶堆过程，需要遍历所有的非叶子节点，时间复杂度为 $O(N)$ ，建立好后，每次取出最大值，共取出 $N$ 次，时间复杂度为 $O(N)$ 。每次取出最大值后，调整堆，时间复杂度为 $O(logN)$ ，所以总的时间复杂度为 $O(NlogN)$

无论数据如何排布，都需要执行上述过程，因此最优、平均、最差时间复杂度均为 $O(NlogN)$

9.3 堆排序空间复杂度多少？

答：将原有的数组看作是一个大顶堆，不需要额外去申请空间，因此空间复杂度仅需要 $O(1)$

9.4 堆排序稳定吗？

答：不是稳定的。

稳定与否指的是如果数组中有相同的元素，那么排序后有没有可能，在最终结果中，原始数组中不同索引的相同元素的顺序是不固定的。
这里比较拗口，但是我们可以这样理解，一个数组[1,2,5,5,4]，有两个数字5，我们认为它们是不同的，不妨假设为[1,2, $5_1$ , $5_2$ ，4]。用两个不同下标，区分这两个5。假设排序后有可能得到[1,2,4, $5_1$ , $5_2$ ]，也可能得到[1,2,4,, $5_2$ , $5_1$ ]，那么我们认为这种排序是不稳定的。如果有且只有一种排序后结果，则说明该排序是稳定的。

堆排序过程中，相同数字间并没有明确的先后顺序，甚至可能不存在直接的亲缘关系（分在两个不同子杈上），因此排序后并不一定仍保持原有的先后出现次序。

9.5 你能写一个堆排序吗？

代码选自《堆排序的模板》

// 待排序数组为arr，长度为n
void heap_sort(vector<int>& arr, int& n){
    // 对所有非叶子节点执行建立最大堆
    for(int i = len / 2 - 1; i >= 0; i--){
        max_heap(arr, i, len - 1);
    }
    // 执行排序过程
    for(int i = len - 1; i > 0; i--){
        // 交换堆顶元素到末尾
        swap(arr[0], arr[i]);
        max_heap(arr, 0, i - 1);
    }
}

// 在指定区间建立一个最大堆
void max_heap(vector<int>& arr, int left, int right){
    // 父节点为开头元素
    int dad = left;
    // 找到左孩子
    int son = dad * 2 + 1;
    // 如果左孩子存在
    while(son <= right){
        if(son + 1 <= right && arr[son] < arr[son + 1]){
            son++; // 如果右孩子存在且更大，更新son
        }
        if(arr[dad] > arr[son]){
            return; // 已经成为最大堆
        }
        else{
            // 交换并递归判断子树是否合法。
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

9.6 额外扩展

实际上，在大多数做题的时候，可以采用优先队列来替代实现一个堆。

    priority_queue<类型, vector<类型>, 比较函数> pq;
    pq.push(...)  // 推入一个值
    pq.pop(...)   // 弹出一个值
    pq.top()      // 取队列顶元素

以存储 $int$ 型变量的优先队列为例，优先队列的特点是，当你推入一个新元素后，他会根据你预设的比较函数，悄悄地把队列排个序，找到里面最大 / 最小的那个值放到头部。也就是帮你实现一个大 / 小顶堆，你完全可以使用它，来模拟创建一个堆
需要注意的是，在优先队列的比较函数中，往往是和我们常用的比较函数正相反的，比如说想实现一个大顶堆，那么我需要return a < b，如此一来，a 的优先级将比 b的优先级要低，也就是后弹出来。

十、基数排序

10.1 基数排序你了解吗？

答：基数排序（十进制下）是首先通过个位，将所有数分成10堆，然后依次弹出形成新的数组。接着通过十位，将所有数分成10堆，再依次弹出。直到所有位数都处理过一遍，此时得到的序列就是有序的了。

喜欢动图的朋友可以看这里《1.10 基数排序 | 菜鸟教程》

10.2 基数排序时间复杂度怎么算？

答：遍历每一位的过程，时间复杂度是 $O(d)$ 其中 $d$ 是最大的数据位数。排序过程每一步需要先将所有数依次放进 $r$ 个基数组里，时间复杂度为 $O(N)$ ；然后将所有组中的元素依次取出并连接在一起，如果是链式基数排序的话，此处时间复杂度为 $O(r)$ 。那么总共的时间复杂度为 $O(d(r + N))$

无论一开始基数排序排成什么样，最终总要执行所有的上述操作，也就是说最好、平均、最差时间复杂度均相等，为 $O(d(r + N))$

10.3 基数排序空间复杂度多少？

答：基数排序需要一个 $O(rd)$ 的空间来作为 “桶”，用于每次将所有数字依次放在桶中。还需要 $O(N)$ 的空间，来临时存储桶中的 $N$ 个元素。所以总的空间复杂度为 $O(rd + N)$

10.4 基数排序稳定吗？

答：稳定的。

稳定与否指的是如果数组中有相同的元素，那么排序后有没有可能，在最终结果中，原始数组中不同索引的相同元素的顺序是不固定的。
这里比较拗口，但是我们可以这样理解，一个数组[1,2,5,5,4]，有两个数字5，我们认为它们是不同的，不妨假设为[1,2, $5_1$ , $5_2$ ，4]。用两个不同下标，区分这两个5。假设排序后有可能得到[1,2,4, $5_1$ , $5_2$ ]，也可能得到[1,2,4,, $5_2$ , $5_1$ ]，那么我们认为这种排序是不稳定的。如果有且只有一种排序后结果，则说明该排序是稳定的。

基数排序过程中，对于某一位相同的两个元素，总是排位靠前的元素，仍然排在前方。因此对于完全相同的两个数字，排序后仍然保持一开始的排位顺序，是稳定的。

10.5 你能写一个基数排序吗？

// 用于找出最大长度
int maxbit(vector<int>& arr){
    // 找到最大值
    int maxnum = arr[0];
    for(auto p : arr){
        if(p > maxnum) maxnum = p;
    }
    // 找到最大值的最大长度
    // 这里取巧，转成string再返回长度。也可以用while循环 ÷ 10判断
    return to_string(maxnum).length();
}

// 假设待排序数组为arr，长度为n
void radix_sort(vector<int>& arr, int n){
    // d是最大位数，r是当前取的位数
    int d = maxbit(arr);
    int r = 1;
    for(int i = 1; i <= d; i++){
        // 这里使用动态长度数组vector做处理
        // 开一个10 * 0的空数组
        vector<vector<int>> list(10, vector<int>(0));
        for(auto p : arr){
            // 找到当前数字p对应位值，插入
            int t = (p / r) % 10;
            list[t].push_back(p);
        }
        // 拷贝回arr中
        int index = 0;
        for(int i = 0; i < 10; i++){
            for(auto p : list[i]){
                arr[index++] = p;
            }
        }
        // 增大r的值
        r *= 10;
    }
}

[面试算法题模板]排序算法总结

一、引子

二、基本性质

三、冒泡排序

3.1 冒泡排序你了解吗？

3.2 冒泡排序时间复杂度怎么算？

3.3 冒泡排序空间复杂度多少？

3.4 冒泡排序稳定吗？

3.5 你能写一个冒泡排序吗？

四、选择排序

4.1 选择排序你了解吗？

4.2 选择排序时间复杂度怎么算？

4.3 选择排序空间复杂度多少？

4.4 选择排序稳定吗？

4.5 你能写一个选择排序吗？

五、插入排序

5.1 插入排序你了解吗？

5.2 插入排序时间复杂度怎么算？

5.3 插入排序空间复杂度多少？

5.4 插入排序稳定吗？

5.5 你能写一个插入排序吗？

六、希尔排序

6.1 希尔排序你了解吗？

6.2 希尔排序时间复杂度怎么算？

6.3 希尔排序空间复杂度多少？

6.4 希尔排序稳定吗？

6.5 你能写一个希尔排序吗？

七、快速排序

7.1 快速排序你了解吗？

7.2 快速排序时间复杂度怎么算？

7.3 怎么规避7.2中出现的问题？

7.4 快速排序空间复杂度多少？

7.5 快速排序稳定吗？

7.5 你能写一个快速排序吗？

八、归并排序

8.1 归并排序你了解吗？

8.2 归并排序时间复杂度怎么算？

8.3 归并排序空间复杂度多少？

8.4 归并排序稳定吗？

8.5 你能写一个归并排序吗？

九、堆排序

9.1 堆排序你了解吗？

9.2 堆排序时间复杂度怎么算？

9.3 堆排序空间复杂度多少？

9.4 堆排序稳定吗？

9.5 你能写一个堆排序吗？

9.6 额外扩展

十、基数排序

10.1 基数排序你了解吗？

10.2 基数排序时间复杂度怎么算？

10.3 基数排序空间复杂度多少？

10.4 基数排序稳定吗？

10.5 你能写一个基数排序吗？

参考文献

猜你喜欢

热点阅读