[数据结构与算法]C++内部排序算法总结

C++内部排序算法总结

1. 算法的稳定性

权值相等的两个数再排序之后如果相对顺序会发生变化，则为不稳定排序，否则为稳定排序。

例如：将 2 1’ 1’’ 3进行排序

若排序后结果为 1’ 1’’ 2 3，则为稳定排序，若为1’’ 1’ 2 3，则为不稳定排序。

2. 插入排序

(1) 直接插入排序

算法原理

遍历一遍数组，第一个元素不动，第二个元素开始，从当前元素往前遍历，如果遍历的元素大于需要插入的元素，则让当前元素往后移一位，直到遇到不大于待插入数的时候，将待插入数插入当前位置。

例

有n = 5的数组3,1,2,4,5；用直接插入排序进行排序。

1. 从第二个元素开始遍历，即i = 1，因为a[0] > 1，所以a[0]往后移一位，a[1] = 3,将1插入到a[0]位置。此时数组为1,3,2,4,5。
2. 此时遍历到第三个元素a[2] = 2，往前遍历a[1]，因为a[1] > 2,所以将3往后移动一位，即a[2] = 3，再往前遍历，a[0] < 2，所以将2插入到a[1]，此时数组为1,2,3,4,5。
3. 此时遍历第四个元素a[3] = 4，前面的数都比它小，所以位置不变，过程省略，第五个元素亦是如此。

代码

void insert_sort(){ //直接插入排序
    for(int i = 1; i < n; i ++){
        int t = q[i];
        int j = i;
        while(j && q[j - 1] > t) {
            q[j] = q[j - 1];
            j --;
        }
        q[j] = t;
    }
}

a. 时间复杂度

[1] 最好情况：$O(n)$

[2] 平均情况：$O(n^2)$

[3] 最坏情况：$O(n^2)$

b. 辅助空间复杂度 $O(1)$

c. 稳定

(2) 折半插入排序

算法原理

在直接插入排序的基础上进行优化

已知当遍历到第i(i > 0)个元素的时候，i前面所有元素都已经为从小到大排序过的数，因此我们可以用二分法查找出大于a[i]的最小的数的下标r，将从此之后的所有数往后移一位，然后将a[i]插入到a[r]。

注意：如果前面所有数都小于a[i]，那么不需要操作a[i]，直接往后遍历即可。

代码

void binary_search_insert_sort(){ // 折半插入排序
    for(int i = 1; i < n;i ++){
        int t = q[i];// 将待插入数赋给t
        if(q[i - 1] <= q[i]) continue; // 假如前面一个数小于等于t，则不操作
        int l = 0,r = i - 1;// 二分查找
        while(l < r){
            int mid = l + r >> 1;
            if(q[mid] > t) r = mid; // 假如前面一个数大于t，说明大于t的最小的数不在q[mid]的后面，将r赋为mid
            else l = mid + 1; // 假如前面一个数小于等于t，说明大于t的最小的数在q[mid]的后面，将l赋为mid + 1
        }
        
        for(int j = r; j < i; j ++) 
        q[j + 1] = q[j]; // 将r到i - 1的所有数往后移动一位
        q[r] = t; // 将待插入数插入到r
    }
}

a. 时间复杂度

[1] 最好情况：$O(n)$

[2] 平均情况：$O(n^2)$

[3] 最坏情况：$O(n^2)$

b. 辅助空间复杂度 $O(1)$

c. 稳定

3. 冒泡排序（bubble sort）

算法原理

冒泡排序，顾名思义，就是将整个数组中最小的数冒泡到第一个位置上，然后将数组中第二小的数冒泡到第二个位置上，…，因此，我们只需要进行n - 1次迭代，因为当前n - 1个数都已经最小的时候，最后一个元素自然是最大值。

那么如何确定冒泡到最前面的那个数是最小的数呢，只需要从最后往前迭代，取出相邻两个数进行比较，如果前面的数大于后面的数，那么将两个数进行交换，当交换到最前面时，可以确定最前面的数一定是最小的数。

优化：假如一整个循环都没有进行交换那么我们就可以认为数组前面的数都比后面的数小，那么就可以直接结束排序。

例

有n = 5的数组a[n] = 3,1,2,4,5，首先从最后一个位置开始比较，因为4 < 5因此不进行操作，往前进一位，2 < 4，不操作，再往前进一位，1 < 2，不操作，再往前进一位，3 > 1，进行交换，得到的新数组为1,3,2,4,5，可以看到最小的数在最前面，依此类推即可。

代码

void bubble_sort(){ // 冒泡排序
    for(int i = 0; i < n - 1; i ++){ // 只需要遍历n - 1次即可
        bool has_swap = false; // 是否交换的标记
        for(int j = n - 1; j > i; j --)
            if(q[j] < q[j - 1]) { // 假如前面一个数大于这个数，则交换两个数
                swap(q[j],q[j - 1]);
                has_swap = true;//标记为交换过
            }
        if(!has_swap) break; //如果一整次循环都没有进行交换，说明数组已经排好序，结束排序
    }
}

(1) 时间复杂度

a. 最好情况：$O(n)$

b. 平均情况：$O(n^2)$

c. 最坏情况：$O(n^2)$

(2) 空间复杂度 $O(1)$

(3) 稳定

4. 简单选择排序(最慢的排序算法)

算法原理

遍历一遍数组，将最小的数和第一个数交换，再遍历一遍数组，将第二小的数和第二个数进行交换，进行n - 1次操作后，前n - 1个数已经是前n - 1小的数，最后一个数就是最大的数。

代码

void select_sort(){ // 选择排序
    for(int i = 0; i < n - 1; i ++){
        int k = i;// 用k记录下最小的数的下标
        for(int j = i + 1; j < n; j ++)
            if(q[j] < q[k]) k = j; // 假如第j个数小于最小的数，那么k的值更新为当前的下标j
        swap(q[i],q[k]); // 将最小的数与q[i]进行交换
    }
}

(1) 时间复杂度

a. 最好情况：$O(n^2)$

b. 平均情况：$O(n^2)$

c. 最坏情况：$O(n^2)$

(2) 空间复杂度 $O(1)$

(3) 不稳定

5. 希尔排序（shell sort）

算法原理

希尔算法类似于插入排序算法的优化，它是先将数组进行分组，分组中采用插入排序，再对整个数组进行插入排序。此处有一个插入排序的性质，就是插入排序对于部分有序的序列，排序效率很高。将数组分组公差设为n/2,n/4,n/8的时间复杂度较高，为$O(n^2)$,但是将数组分组公差设为n/3,n/9,n/27的时间复杂度为$O(n\sqrt{n})$。在每组间使用插入排序。

代码

// d = n/2时,可以确保d最后会变成1
void shell_sort(){ // 希尔排序
    for(int d = n / 2; d; d /= 2) // 设置公差d，d会慢慢变小直至1，确保会完整排序好
        for(int start = 0; start < d; start ++) // 从d开始到2d - 1
            for(int i = d + start; i < n; i += d){ // 对d + start,2d + start,3d + start...进行插入排序
                int t = q[i],j = i;
                while(j > start && q[j - d] > t){
                    q[j] = q[j - d];
                    j -= d;
                }
                q[j] = t;
            }
}

// d = n/3时，当最后d = 2时，2 / 3 == 0，所以我们需要对2进行特判，d == 2时，d最后等于1
void shell_sort(){ // 希尔排序
    for(int d = n / 3; d; d == d == 2 ? 1 : d / 3) // 设置公差d，d会慢慢变小直至1，确保会完整排序好
        for(int start = 0; start < d; start ++) // 从d开始到2d - 1
            for(int i = d + start; i < n; i += d){ // 对d + start,2d + start,3d + start...进行插入排序
                int t = q[i],j = i;
                while(j > start && q[j - d] > t){
                    q[j] = q[j - d];
                    j -= d;
                }
                q[j] = t;
            }
}

(1) 时间复杂度 $O(n^{\frac{3}{2}})$

(2) 空间复杂度 $O(1)$

(3) 不稳定

6. 快速排序(最快的排序算法)

算法原理

快速排序是从区间左端点l到右端点r中选出一个值x(一般选择中间的数，也可以是端点或者随机一个数)，称为哨兵，再使用双指针算法，令i = l，j = r，在i < j的前提下，将i从前往后移动，将j从后往前移动，再将小于哨兵值x的放到右边，大于哨兵值x的放到左边，这样就将哨兵值x的位置放好了，x左边的数都小于x，x右边的数都大于x，然后将x左边和x右边再分别进行快速排序，当l >= r时，说明只剩下一个元素，就不用排了。

代码

void quick_sort(int q[],int l,int r){ // 快速排序
    if(l == r) return; // 假如只剩下一个数，则不需要再排了
    
    int i = l - 1,j = r + 1,x = q[l + r >> 1]; // 因为do...while()循环是先进行再判断，所以我们让i = l - 1,j = r + 1，进行完后i = l,j = r
    
    while(i < j){ // 在i < j 的前提下进行(确保只遍历一遍，否则遍历两遍数组会还原)
        do i ++; while(q[i] < x);// 如果q[i] < x，那么不需要停下
        do j --; while(q[j] > x);// 如果q[j] > x, 那么不需要停下
        if(i < j) swap(q[i],q[j]); // 两个数都停下后，说明q[i] >= x,q[j] <= x,交换两个数
    }
    
    quick_sort(q,l,j);quick_sort(q,j + 1,r);//对左边和右边进行排序
}

(1) 时间复杂度

a. 最好情况：$O(nlogn)$

b. 平均情况：$O(nlogn)$

c. 最坏情况：$O(n^2)$

(2) 空间复杂度 $O(logn)$

(3) 不稳定

7. 堆排序

堆

堆的定义

堆是一个数据结构，一般用完全二叉树实现，堆又分为大根堆和小根堆，大根堆递归满足根的值大于等于节点的值，即爸爸的值大于等于儿子的值，因此大根堆的根节点的值就是整个数组的最大值。而小根堆则递归满足根的值小于等于节点的值，即爸爸的值小于等于儿子的值，因此小根堆的根节点就是整个数组的最小值

堆的存储

堆一般使用顺序存储，而非链式存储，顺序存储的效率较高
即用数组模拟二叉树，下标1存入根节点，下标为i的节点，它的左儿子为i * 2，右儿子为i * 2 + 1，例如：根节点为a[1]，它的左儿子为a[2]，右儿子为a[3],a[2]的左儿子为a[4]，右儿子为a[5]……

因此，一个节点i的父节点下标则为i / 2

down操作

假设有一个父节点和它的两个子节点，两个子节点分别为两个子树的根节点，这两棵子树已经排序过，对这个父节点和它的两个子节点进行操作，以大根堆为例，分别比较父节点和它两个儿子的值的大小，假设父节点的值不是最大值，那么交换父节点和值最大的那个节点的的值

堆的建立

将所有数存入数组后，从最下面一层开始往上进行down操作，因为最下面一层只有父节点没有子节点，因此可以从倒数第二层开始down，从下往上down到根节点的时候整个堆就建立完成了

堆的删除操作(删堆顶)

堆的删除操作可以删除任意一个元素，但是默认为删堆顶。因为堆由数组实现，因此在原点完成删除操作是很困难，但是删除最后一个元素很简单，只要让n --就可以了，因此删堆顶我们只需要将最后一个元素覆盖到堆顶，再将最后一个元素删掉即可，然后再down一遍堆顶，就等于将堆顶元素删除了

算法原理

因为建立的小根堆只能确保根节点为最小值，无法保证左儿子严格小于右儿子，因此只靠建立小根堆无法保证堆严格从小到大排，所以我们尝试建立大根堆，定义一个int型变量sz来维护大根堆的元素个数，然后进行n - 1次操作，每次将a[1]和a[sz]进行交换，可以确保数组最后一个值a[sz]为最大值，然后令sz --，down(1)，维护大根堆，再对前sz个数进行堆排序。

代码

void down(int u){ // u表示下标
    int t = u; // 将u赋给t
    if(u * 2 <= sz && q[u * 2] > q[t]) t = u * 2; // 如果它有左儿子且它的左儿子数值大于t的值，将t的值更新为左儿子的下标
    if(u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1; // 如果它有右儿子且它的右儿子数值大于t的值，将t的值更新为右儿子的下标
    if(u != t){ // 如果q[u]不是最大值
        swap(q[u],q[t]);//交换两个数
        down(t);//对下标t进行维护
    }
}

void heap_sort(){
	sz = n;
    for(int i = n / 2; i; i --) down(i); // 建立一个大根堆
    for(int i = 1; i < n; i ++) {//进行n - 1次操作
        swap(q[1],q[sz]);//交换堆顶和最后一个元素的值
        sz --;//长度减1
        down(1);//维护堆顶
    }
}

(1) 时间复杂度

a. 最好情况：$O(nlogn)$

b. 平均情况：$O(nlogn)$

c. 最坏情况：$O(nlogn)$

(2) 空间复杂度 $O(logn)$

(3) 不稳定

8. 二路归并排序（merge sort）

算法原理

二路归并排序也称归并排序，首先，它将数组从中间切开分为两半，再递归对左半数组和右半数组进行二路归并排序。

此时左半数组和右半数组已经分别为有序数组，对左半数组和右半数组进行合并，此时需要一个辅助数组w[N]，将左半数组和右半数组合并为数组w[N]

代码

void merge_sort(int l,int r){ // 二路归并排序
    if(l >= r) return; // 如果只剩一个元素，则跳出归并排序
    int mid = l + r >> 1;//确定中点
    merge_sort(l,mid),merge_sort(mid + 1,r); //递归对左半数组和右半数组进行归并排序
    
    int i = l,j = mid + 1,k = 0;
    while(i <= mid && j <= r) // 假如左半数组和右半数组没有合并完
        if(q[i] <= q[j]) w[k ++] = q[i ++];
        else w[k ++] = q[j ++];
    while(i <= mid) w[k ++] = q[i ++]; //假如合并完后左半数组还有剩，则直接加入w[N]
    while(j <= r) w[k ++] = q[j ++]; //假如合并完后右半数组还有剩，则直接加入w[N]
    
    for(int i = l,j = 0; j < k; i ++,j ++) q[i] = w[j];//将辅助数组复制回原数组
}

(1) 时间复杂度

a. 最好情况：$O(nlogn)$

b. 平均情况：$O(nlogn)$

c. 最坏情况：$O(nlogn)$

(2) 空间复杂度 $O(n)$

(3) 稳定