常见排序算法总结

冒泡排序：

基本思路：每次冒泡总会将当前数组最大数据通过相邻数据比较交换，排到数组尾，因此一次冒泡至少排好一个数 据的顺序，经过n次冒泡就会将当前数组排好顺序。

空间复杂度：O(1),因为只涉及相邻数据互换，所以只需要常量级的临时空间，是原地排序算法。

稳定性：在冒泡排序中只有交换才改变数据顺序，而为了保证数据稳定性，当两个数据相等时不进行数据互换。

时间复杂度：最好情况下，数据已经是有序的了，只需要进行一次冒泡，因此时间复杂度为O(n),最坏情况下数据 完全是倒叙的，因此需要N次冒泡，时间复杂度为O(n2)。平均时间复杂度为O(n2)

插入排序：

基本思路：将数据中的数组分为两个区间分别为已排序区间和未排序区间，每次将未排序区间中的一个元素挑出插 入已排序区间中的合适位置，直到未排序区间中的元素为空，排序结束。

空间复杂度：因为不需要额外的空间，所以空间复杂度为O(1),是原地排序算法。

稳定性：当未排序区间元素插入已排序区间时，碰到相同的元素，后排的元素插入已经排好元素的后方，就不会打 乱相同元素的原相对顺序，因此属于稳定排序。

时间复杂度：最好情况下，数组为有序的，因此不需要进行插入操作，只需从头到尾进行一次遍历比较即可，因此 时间复杂度为O(n),最坏情况下，数组为倒序，每次插入相当于在数组第一个位置插入新的数据，因 此时间复杂度为O(n2)。平均时间复杂度为O(n2)。

选择排序：

基本思路：选择排序与插入排序类似，也是分为已排序区间和未排序区间，不同的是选择排序选择未排序区间最小 值放在已排序区间末尾之后的一个元素也就是未排序区间开头，而未排序区间开头的元素放在原未排 序区间最小值的位置，简而言之选择未排序区间最小值与未排序区间首值进行互换。直到未排序区间 元素个数为零。

空间复杂度：因为不需要额外的空间，所以空间复杂度为O(1),是原地排序算法。

稳定性：不稳定，因为其中涉及到元素互换，所以会导致大小相同元素的相对位置被打乱。（为什么互换而不能插 入，因为空间复杂度为一，若像插入排序那样将最小值插入已排序区间末尾，会导致未排序首位值被覆 盖，造成数据丢失）

时间复杂度：最好，最坏，平均都为O(n2)。

归并排序：

基本思路：将整个数组分开成小部分，分别排序后再合并到一起。关键在于合并步骤，假设要合并的数组分别为A 和B，那么我们利用一个临时数组C，两个指针a,b初始位置分别位于A,B数组首位，然后将a,b所指内容 进行比较，将较小数据放入C中，然后将该指针后移一位，继续比较a,b直到某一数组为零，然后将另 一数组剩余数据拷贝进C中。C中的数据即为合并完成的数据，然后拷贝回原数组中。其实排序是在合 并步骤中完成的。

空间复杂度：不是原地排序算法，因为合并过程中需要临时数组C，所以需要额外空间，空间复杂度为O(n).

稳定性：稳定，是否稳定主要看合并过程，当我们对A,B 数组进行比较时，如果碰到相同数据，只需要将A数组数 据放入C中就会使相同数据原相对位置不变，也就达到了稳定排序。

时间复杂度：递归代码时间复杂度，假设求解A的时间为T(a),A分解为子问题B,C 求解时间分别为T(b)，T(c)，那么 T(a)=T(b)+T(c)+K,K为b与c合并的时间。假设A的长度为n，那么将A分为两等份的话时间为 2*T(n/2)，且合并两个有序数组的时间复杂度为O(n),所以分析长度为n的数组时间复杂度为：

T(n) = 2*T(n/2) + n

= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n

= 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n

= 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
......

= 2^k * T(n/2^k) + k * n

所以当n/2^k=1时，k=log2n,所以时间复杂度为O(nlogn).

快速排序：

基本思路：在数组A中选择一个随机数据a，令quick_sort()函数可以将数组A中大于a的数放在a的前方，小于a的数放在a的后方，那么递推公式为quick_sort(p.....r)=quick_sort(p.....q-1)+quick_sort(q-1.....r).截止条件为p>=r。

1，关于放置方法，若不考虑空间复杂度，则可以类似于选择排序，设置两个临时数组B C ，将A数组的数据与a进行比较，将较大的数放在B，较小的数放在C，再将数组B与C的数据复制回A，将a放在中间。但是这种方法并不是原地排序方法。并不常用。

2，若要原地排序，则类似于插入排序，将数组A分为已排序区间与未排序区间，将未排序区间的数与a进行比较，若小于a，则将该数放在已排序区间末尾，这里可以选择将需要放置的数与被放置位置的数进行交换，从而避免插入过程中的数据搬移使得时间损耗上升，而由于交换操作会导致相同数据原位置被打乱，所以这种方法是不稳定的。

所以快排一般为原地，但并不稳定的排序方法。

空间复杂度：O(1)。

时间复杂度：由于这里也是用的递归思想，那么对于归并排序的思想这里同样适用，时间复杂度为O(nlogn)。但是在极端情况下会退化为O(n2).

优化：之所以会造成极端情况，是因为分区点选择不合理，合理的分区点选择是要数组数据在分区点两边数据数量差不多。分区点选择方法，一个是三数取中法，即在数据区间首，中，尾各取一数，选择中间数作为分区点，而如果数组数据较大，则可以“五数取中”“十数取中”。还有一个是随机法。

桶排序：

不基于比较，但是对数据又较为严格的要求：

1.要求数据可以很容易的分成m个桶，并且桶与桶之间有天然的大小关系，从而可以不用对桶进行排序，

2.要求数据在桶中分布式比较均匀的

3.桶排序比较适合外部排序，也就是数据存储在外部磁盘中，数据量很大无法全部加载到内存中进行排序。

基本思路：将全部数据均匀的分到桶中，然后对每个桶进行快排，之后按照桶的大小将其中数据依次取出。

时间复杂度：假设有n个数据，分在m个桶中，那么每个桶中的数据就为k=n/m个，对m个桶种

数据进行快排，时间复杂度为O(m*k log(n/m))也就是O(n log(n/m)),当m接近n时，时间复杂度也就较接近O(n)。

堆排序：

不稳定，原地，时间复杂度：O(nlogn)

基本思路：

1.建堆，就是将数组原地组建成堆的数据结构，这其中利用到了堆化操作，堆化就是将堆中子节点与其叶子节点尽行比较，将其中最大的（或最小）的数据放到子结点处，完成后比较下一个子节点，直到所有子节点全部完成该操作。

代码如下：

void  heapify(int a[], int n,int i)//堆化
{
    while (true)
    {
        int maxpos = i;
        if (i*2<=n && a[i] < a[2 * i]) maxpos = 2 * i;
        if (i*2 +1<= n && a[maxpos] < a[2 * i + 1]) maxpos = 2 * i + 1;
        if (maxpos == i) break;
        swap(a, i, maxpos);
        i=maxpos;//为了将使下降的原主节点进行下一轮堆化，直到最底层的叶节点
    }
}
void  buildheap(int a[], int n)//建立堆
{
    for (int i = n / 2; i >= 1; --i)
    {
        heapify(a,n,i);
    }
}

2.排序，这个过程有点类似于删除堆顶操作，将堆顶元素与堆底元素进行交换，这样该数组最大的数放在了位于n的位置，然后将剩下的n-1数据进行堆化，重复这个操作直到堆中剩下下标为1的一个元素，排序完成。

代码如下：

void heapsort(int a[], int n)
{
    for (int i = n; i > 1; --i)
    {
        swap(a, 1, i);
        buildheap(a, i-1);
    }
    return;
}

时间复杂度：每个节点堆化的过程都会与叶子节点进行比较与交换，所以每个节点的时间复杂度与该节点所在的高度成正比，堆化时间复杂度为O(n),排序时间复杂度为O(n/logn),所以整个堆排序的时间复杂度为O(n/logn)。

稳定度：不稳定，因为在排序过程中回进行数据交换。

为什么快排性能比堆排序好，主要有两个方面原因：

1.快速排序的数据访问顺序时顺序访问，但是堆排序的数据访问是跳着访问的，这样对CPU缓存不友好。

2.对于数据相同的数组，堆排序的数据交换次数多于快排。