排序

:material-circle-edit-outline: 约 1090 个字 :fontawesome-solid-code: 43 行代码 :material-clock-time-two-outline: 预计阅读时间 4 分钟

简单排序

前提说明

规范定义

void X_Sort(elementType A[], int N)

N只为正整数
只讨论基于比较的排序
只讨论内部排序
1. 即数据能够一次性进入内容完成排序
2. 外部排序即数据量大于内存时的操作
没有全能的排序，学的排序都是有存在的理由的

一些概念

稳定性：任意两个相等的数据，排序前后的相对位置不变

冒泡排序

选取一个方向，一个一个往后，与相邻的比较。

从第一个开始，如果目前的比下一个小，就两者对换，然后选取下一个，重复。

这样一轮下来，最大的那一定会排到最后。

如此再次重复对剩下的重复，每次都能将剩下的最大的排到正确位置。

代码

void bubble_Sort(int a[], int n, int *times){
    for(int i = 0; i<n;i++){
        int flag = 1;   //0 if sort is already correct
        for(int j = 0; j<n-i-1; j++)
            if(a[j]>a[j+1]){
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                flag = 0;
            }
        (*times)++;
        if(flag) break;
    }        
}

复杂度

最好：序列已经排好序了，只需扫描一次—— \(T=O(N)\)

最坏：完全逆序输入—— \(T=O(N^2)\)

优势

能操作链表
数相等时不交换，即有稳定性

插入排序

类似斗地主拿到牌后一张一张地排序

分为了手上已经排好序的牌，以及正等待插入的牌。每次排好序后再插入一张牌在手上的牌的最后，然后开始一张一张往前比，每次比较发现前面的大就将其往后移，如此为正确位置提供空位，直到找到正确的位置将其放入。

复杂度

最好：序列已经排好序了，只需扫描一次—— \(T=O(N)\)

最坏：完全逆序输入—— \(T=O(N^2)\)

逆序对（inversion）：对于下标i 、 j，如果A[i]>A[j]，则(i,j)为一对逆序对。

冒泡排序和交换排序每次交换实际是消去了一个逆序对。

插入排序时间复杂度： \(T(N,I)=O(N+I)\)

优势

稳定性
相对冒泡排序，省去了两两交换的步骤
序列基本有序时，插入排序非常快

逆序对定理

任意 \(N\) 个不同元素组成的序列，平均具有 \(\frac{N(N-1)}4\) 个 \(inversion\)
任何 仅以交换相邻元素 来排序的算法，其平均时间复杂度为 \(\Omega (N^2)\)
- 为了改进，需要实现每轮消去多个 \(inversion\)
  - 例如，一种思路是将两个较远的元素进行交换

选择排序

先找到最小的，与第一个交换，这样第一个就确定了，然后在剩下的继续如此重复

    int tmp = 0;

    for(int P = 0;P<N;P++){
        int minpos = P; //这里防止a[P]即最小时minpos未更新的bug
        for(int i = P;i<N;i++)
            if(a[i]<a[minpos]) minpos = i;
        tmp = a[minpos];
        a[minpos] = a[P];
        a[P] = tmp;

    }

复杂度

\(T=\Theta (N^2)\)

思考

观察可见，选择排序主体是一个大的for循环，里面分为两个部分，一个是寻找最小值的位置，一个是交换。显然交换的部分无法优化。

如果能减少寻找最小值这部分操作的复杂度，就能大大减少整体的复杂度。我们想到可以用最小堆存储数据。

于是就有了堆排序 (Heap Sort) 。

希尔（Shell）排序

利用了插入排序的简便的同时，实现每轮消去多个 \(inversion\)

取间距递减的多个间隔序列，对每个序列单独进行插入排序，直到间隔为1。

间距递减的多个间隔序列被称为希尔增量序列

原始Shell Sort

间隔每次减半

    for(int D = N/2;D>0;D/=2)   //stop after performing D=1
        //insertSort
        for(int i = D;i<N;i++){
            int tmp = a[i];
            int j;
            for(j = i;j>=D && a[j-D]>tmp;j-=D) 
                a[j] = a[j-D];
            a[j] = tmp;
        }

复杂度

最坏：\(T=\Theta (N^2)\)

问题

增量元素不互质，小增量可能不起作用
不稳定

解决方案

\(Hibbard\) 增量序列：\(D_k = 2^k-1\) —— 互质

堆排序

原始算法

利用堆排序，自然而然的思路就是将输入的排序建立为一个最小堆，然后将最小堆以此删除，即可得到排好序的数据。

BuildHeap(A);   //O(N)
for (i = 0;i<N;i++)
        tmpA[i] = DeleteMin(A); //O(logN * N), *N is from loop
for(i = 0;i<N;i++)
        a[i] = tmpA[i]; //O(N)

总复杂度：\(T=O(NlogN)\)

问题

需要额外的 \(O(N)\) 的空间，且复制元素需要时间

改进算法

建立最大堆，则最大元素处于root，再将root与最后一个位置的元素对换，则最大元素处于了正确位置。排除这最后一个元素，对剩下的循环操作。

注意，堆排序root下标为0，则parent与child的下标关系变化了

\(T=2N\log N-O(N\log \log N)\)

堆排序不稳定

归并排序

快速排序

最好：\(T(N)=O(N\log N)\)

快排不稳定

排序