常见排序算法总结

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 4.8k | 阅读时长 ≈ 4 分钟

重点对比一下快排与堆排,总结八个常用排序算法

八个常用排序算法思想

冒泡排序

1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3.针对所有的元素重复以上的步骤，除了最后一个；
4.重复步骤1~3，直到排序完成。

简单插入排序

1.从第一个元素开始，该元素可以认为已经被排序；
2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5.将新元素插入到该位置后；
6.重复步骤2~5。

希尔排序

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2.按增量序列个数k，对序列进行k趟排序；
3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

直接选择排序

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

1.初始状态：无序区为R[1..n]，有序区为空；
2.第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
3.n-1趟结束，数组有序化了。

堆排序

1.将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
2.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
3.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

1.从数列中挑出一个元素，称为 “基准”（pivot）；
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

1.把长度为n的输入序列分成两个长度为n/2的子序列；
2.对这两个子序列分别采用归并排序；
3.将两个排序好的子序列合并成一个最终的排序序列。

基数排序

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法稳定性与复杂度比较

算法稳定性

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面。

举例

选择排序: 序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法.

快速排序: 比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。

堆排序: 当相同元素被分配到不同的父节点下，在反复调整堆的过程中，可能会改变相同元素的相对顺序。

希尔排序: 一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

"da"

快速排序与堆排对比

从时间考虑

快速排序在最坏情况下时间复杂度会达到O(n^2),平均时间复杂度为O(nlogn);而堆排序最好最坏和平均情况下时间复杂度均为O(nlogn),但实际使用中快速排序的运行时间常常比堆排序短很多。

"da"

根本原因就是程序的局部性原理。
在堆排中，每一个操作都是不利于程序的局部性原理的，每次元素间的比较、数的调整等，都不是相邻或者附近的元素间的比较(堆调整每次都从堆底拿元素到堆顶然后向下进行调整），这就导致了经常在cache里面找不到要读取的数据，需要从内存中读出来，而当cache满了之后，以前读取的数据又要被剔除，那么这就需要不断地在cache和内存间换入换出数据。
反观快排，利用分而治之的方法，元素间的比较都在某个段内，局部性好。

快排的最坏时间虽然复杂度高，但是在统计意义上，这种数据出现的概率极小。

从空间考虑

快速排序是基于递归实现的，所以在数据量非常大的时候可能会发生堆栈溢出错误。
堆排序是在原输入数组上进行交换复制操作的(就地排序)，所以需要开辟的辅助空间跟输入数组的规模无关，空间复杂度为O(1)

堆排的应用场景

堆排适用于数组规模非常大(数百万或者更多)＋严格要求辅助空间的场景.
堆排序的典型应用是找数组内的最大/小的元素，topK之类，用堆排序可以在N个元素中找到top K，时间复杂度是O(NlogK)，空间复杂的是O(K)，而快速排序的时间复杂度是O(NlogN)，空间复杂度是O(N)

Question ——Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

具体实现：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 建立节点个数为k的堆,直接用前k个节点
        // 然后遍历剩下的节点,如果比堆的顶点都小的直接舍弃,大的则将堆的顶点用新的节点替换,然后再进行堆的调整
        // 所以时间复杂度为 O(nlgk)
        // 建立大小为k的堆
        for (int i = 0; i < k; i++) {
            MinHeapFixup(nums, i);
        }
        for (int i = k; i < nums.size(); i++) {
            if (nums[i] > nums[0]) {
                nums[0] = nums[i];
                MinHeapFixdown(nums, 0, k);
            }
        }
        return nums[0];
    }
    // 堆的插入
    void MinHeapFixup(vector<int>& nums, int i) {
        int j, tmp;
        tmp = nums[i];
        j = (i - 1) / 2;  //父节点
        while(j >= 0 && i != 0) {
            if (nums[j] < tmp)
                break;
            nums[i] = nums[j];
            i = j;
            j = (i - 1) / 2;
        }
        nums[i] = tmp;
    }
    // 堆的删除(堆的调整,从根部开始)
    // 堆删除的实际做法,就是将数组中的最后一个节点和根节点对换,删除最后一个元素,然后再把堆进行调整。
    void MinHeapFixdown(vector<int>&nums, int i, int k) {
        int j, tmp;
        tmp = nums[i];
        j = 2 * i + 1;  // 孩子节点
        while (j < k) {
            if (j + 1 < k && nums[j + 1] < nums[j]) //在左右孩子中找最小的孩子
                j++;
            if (nums[j] > tmp)
                break;
            nums[i] = nums[j];
            i = j;
            j = 2 * i + 1;
        }
        nums[i] = tmp;
    }
};

参考链接：
【1】十大经典排序算法（动图演示）
【2】稳定排序与不稳定排序
【3】为什么在平均情况下快速排序比堆排序要优秀？
【4】堆排序与快排比较
【5】堆与堆排序、Top k 问题

-------------本文结束感谢您的阅读-------------