各类排序算法汇总

前言：排序按照所占用的计算机内部存储设备，可以分为：内部排序和外部排序

• 内部排序：占用的是内存，待排序序列全部放在内存加以排序处理
• 外部排序：占用的是外存，数据量比较大，内存空间不足以一次性全部容纳数据的情况

本文章暂时总结内部排序的各种算法。

图：各种内部排序方法的比较
**

一、插入类排序

将无序的子序列插入到有序序列中

直接插入

将元素序列走一遍，走到某个元素时，将其插入到已走过的已排序序列中，这样可以保证走完所有元素，然后所有的元素都是排序好的。

数据结构选用的时顺序表

/* 直接插入排序 */
void insertSort(SqList &S) {
    for (int i = 2; i <= S.length;++i) {
        if (S.data[i]< S.data[i-1]){
            S.data[0] = S.data[i];
            S.data[i] = S.data[i - 1];
            int j;
            for (j = i - 2; S.data[0] <= S.data[j];--j)
                S.data[j + 1] = S.data[j];
            S.data[j + 1] = S.data[0];
        }
    }
}

折半插入

在直接插入的过程中，找到一个元素，然后再需要从后往前依次查找“该在”的位置，对其查找进行了折半优化

/* 折半插入排序 */
void BinsertSort(SqList &S) {
    for (int i = 2; i <= S.length;i++) {
        S.data[0] = S.data[i];
        int low = 1;
        int high = i - 1;
        while (low <= high) {
            int m = (low + high) / 2;
            if (S.data[0]<S.data[m]) high = m - 1;
            else low = m + 1;
        }
        int j;
        for (j = i - 1; j >= high + 1;--j)
            S.data[j + 1] = S.data[j];
        S.data[high + 1] = S.data[0];
    }
}

希尔排序

/* 希尔排序 */
void ShellInsert (SqList &L, int dk) {
    for (int i = dk + 1; i <= L.length;++i) {
        if (L.data[i]<L.data[i-dk]) {
            L.data[0] = L.data[i];
            int j;
            for (j = i - dk; j > 0 && L.data[0] < L.data[j]; j -= dk)
                L.data[j + dk] = L.data[j];
            L.data[j + dk] = L.data[0];
        }
    }
}
void ShellSort (SqList &L, int dt[],int t) {
    for (int k = 0; k < t;++k) {
        ShellInsert(L, dt[k]);
    }
}

二、交换类排序

冒泡排序

/* 冒泡排序 */
void BubbleSort(SqList &L) {
    int m = L.length - 1;
    int flag = 1;
    while ((m>0) && (flag == 1)) {
        flag = 0;
        for (int j = 1; j <= m;j++ )
            if (L.data[j]>L.data[j+1]) {
                flag = 1;
                int t = L.data[j];
                L.data[j] = L.data[j + 1];
                L.data[j + 1] = t;
            }
        --m;
    }
}

快速排序

/* 快速排序 */
int Partition (SqList &L, int low, int high) {
    L.data[0] = L.data[low];
    int pivotkey = L.data[low];
    while (low < high) {
        while (low<high && L.data[high]>=pivotkey)
            --high;
        L.data[low] = L.data[high];
        while (low<high && L.data[low]<=pivotkey)
            ++low;
        L.data[high] = L.data[low];
    }
    L.data[low] = L.data[0];
    return low;
}
void Qsort(SqList &L, int low, int high) {
    if (low<high){
        int pivoloc = Partition(L, low, high);
        Qsort(L, low, pivoloc - 1);
        Qsort(L, pivoloc + 1, high);
    }
}
void QuickSort(SqList &L) {
    Qsort(L, 1, L.length);
}

三、选择类排序

参考：ata.biancheng.net/view/72.html

简单选择排序

/* 简单选择排序 */
void SelectSort(SqList &L) {
    for (int i = 1; i < L.length;i++) {
        int k = i;
        for (int j = i + 1; j <= L.length;++j)
            if (L.data[j]<L.data[k])
                k = j;
            if (k != i) {
                int t = L.data[i];
                L.data[i] = L.data[k];
                L.data[k] = t;
            }
    }
}

树形选择排序

堆排序

四、归并排序

2-路归并排序

给定一个序列，从左往右两两子序列进行归并

子序列归并的算法：加入有两个靠着的 a、b 序列，由上面可知，a、b 各自都是有序序列，现在就是将这两个合并为一个有序序列 k，将 a 和 b 序列的各个元素进行比较，小的依次放入 k 序列，当 a、b 两个中有一个序列为空了，就将那个不为空的序列直接加入到 k 序列即可，最后 k 序列就是目的序列。

五、分配类排序

基数排序

TODO: 扑克牌的花色排序

六、外部排序

基本方法

多路平衡归并

基本思想是内部排序中的 2-路归并排序

置换-选择排序

最佳归并树

参考

文章的动画演示

• https://blog.csdn.net/Hk_john/article/details/79888992（js）
• https://www.itrhx.com/2020/10/23/A91-sorting-algorithm/（python）