前言

在生活中，排序是一个很重要的东西。比如你在洛谷题单刷题时，那些题目都是按难度从小到大排序的。排序可以将无序的杂乱无章的东西整理清楚，以便查询和利用。

十大排序

一、选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 $O(n^2)$ 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。具体来说，假设长度为 $n$ 的数组 $arr$，要按照从小到大排序，那么先从 $n$ 个数字中找到最小值 $min1$，如果最小值 $min1$ 的位置不在数组的最左端(也就是 $min1$ 不等于 $arr_1$)，则将最小值 $min1$ 和 $arr_1$交换，接着在剩下的 $n-1$ 个数字中找到最小值 $min2$，如果最小值 $min2$ 不等于$arr_1$，则交换这两个数字，依次类推，直到数组 $arr$ 有序排列。算法的时间复杂度为 $O(n^2)$。

选择排序算法的原理如下：

• $1$、首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

• $2$、再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

• $3$、重复第二步，直到所有元素均排序完毕。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

/* 选择排序 */
void selection_sort(int arr[], int len) {
    for (int i = 1; i < len; i++) {
        int Min = i;
        for (int j = i + 1; j <= len; j++) //  遍历未排序的元素
            if (arr[j] < arr[Min]) //找到目前最小值
                Min = j;   //记录最小值
        swap(arr[Min], arr[i]); //做交换
    }
}

int len, arr[1010];
int main() {
    cin >> len;
    for (int i = 1; i <= len; i++)
        cin >> arr[i];
    selection_sort(arr, len);
    for (int i = 1; i <= len; i++)
        cout << arr[i] << " ";
    return 0;
}

二、冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。假设长度为 $n$ 的数组 $arr$，要按照从小到大排序。则冒泡排序的具体过程可以描述为：首先从数组的第一个元素开始到数组最后一个元素为止，对数组中相邻的两个元素进行比较，如果位于数组左端的元素大于数组右端的元素，则交换这两个元素在数组中的位置。这样操作后数组最右端的元素即为该数组中所有元素的最大值。接着对该数组除最右端的 $n-1$ 个元素进行同样的操作，再接着对剩下的 $n-2$ 个元素做同样的操作，直到整个数组有序排列。

冒泡排序算法的原理如下：

• $1$、比较相邻的元素。如果第一个比第二个大，就交换他们两个。

• 2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

• $3$、针对所有的元素重复以上的步骤，除了最后一个。

• $4$、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

/* 冒泡排序 */
void BubbleSort(int arr[], int len) {
    for (int i = 1; i <= len; i++) //循环次数 
        for (int j = 1; j <= len -  i; j++) //遍历还没有排好序的元素 
            if (arr[j] > arr[j + 1]) //如果发现自己大于了右边的数 
                swap(arr[j], arr[j + 1]); //则交换连个数的位置 
}

int len, arr[1010];
int main() {
    cin >> len;
    for (int i = 1; i <= len; i++)
        cin >> arr[i];
    BubbleSort(arr, len);
    for (int i = 1; i <= len; i++)
        cout << arr[i] << " ";
    return 0;
}

三、插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。例如要将数组 $arr=[4,2,8,0,5,1]$ 排序，可以将 $4$ 看做是一个有序序列，将 $[2,8,0,5,1]$ 看做一个无序序列。无序序列中 $2$ 比 $4$ 小，于是将 $2$ 插入到 $4$ 的左边，此时有序序列变成了 $[2,4]$，无序序列变成了 $[8,0,5,1]$ 。无序序列中 $8$ 比 $4$ 大，于是将 $8$ 插入到 $4$ 的右边，有序序列变成了 $[2,4,8]$,无序序列变成了 $[0,5,1]$。以此类推，最终数组按照从小到大排序。该算法的时间复杂度为 $O(n^2)$。

插入排序算法的原理如下：

• $1$、从第一个元素开始，该元素可以认为已经被排序；

• $2$、取出下一个元素，在已经排序的元素序列中从后向前扫描；

• $3$、如果该元素（已排序）大于新元素，将该元素移到下一位置；

• $4$、重复步骤 $3$，直到找到已排序的元素小于或者等于新元素的位置；

• $5$、将新元素插入到该位置后；

• $6$、重复步骤 $2 \sim 5$。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

/* 插入排序 */
void insertion_sort(int arr[], int len) {
    for (int i = 2; i <= len; i++) { //遍历所有还没有排序的元素 
        int x = arr[i]; //把元素先记录下来 
        int j = i - 1; //往前面找插入的位置 
        while(j >= 1 && arr[j] > x) { //如果没有到数组最左边，或者还没有找到可插入的位置，接着找 
            arr[j + 1] = arr[j]; //把元素挪到后面 
            j--; //往下找 
        }
        arr[j + 1] = x; //把元素插入进去 
    }
}

int len, arr[1010];
int main() {
    cin >> len;
    for (int i = 1; i <= len; i++)
        cin >> arr[i];
    insertion_sort(arr, len);
    for (int i = 1; i <= len; i++)
        cout << arr[i] << " ";
    return 0;
}

四、希尔排序

希尔排序(Shell’s Sort)在插入排序算法的基础上进行了改进，算法的时间复杂度与前面几种算法相比有较大的改进，但希尔排序是非稳定排序算法。其算法的基本思想是：先将待排记录序列分割成为若干子序列分别进行插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行一次直接插入排序。该算法时间复杂度为 $O(nlogn)$。

希尔排序算法的原理如下：

• $1$、选择一个增量序列 $t_1$，$t_2$，……，$t_k$，其中 $i > j$ 并且 $t_i > t_j$, $t_k = 1$；

• $2$、按增量序列个数 $k$，对序列进行 $k$ 趟排序；

• $3$、每趟排序，根据对应的增量 $t_i$，将待排序列分割成若干长度为 $m$ 的子序列，分别对各子表进行直接插入排序。仅增量因子为 $1$ 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

代码如下：

#include <iostream>
#include <cstdio>
using namespace std;

/* 希尔排序 */
void shell_sort(int arr[], int len) {
    int templen = len;
    do {
        templen = templen / 3 + 1; //确定分组的增量
        for (int i = 1; i <= templen; i++) { //进行templen次排序 
            for (int j = i + templen; j <= len; j += templen) { //遍历每个元素 
                if (arr[j] < arr[j - templen]) { //进行插入 
                    int k, temp = arr[j]; //k表示插入位置，temp表示待插入元素 
                    for (k = j - templen; k >= 1 && temp < arr[k]; k -= templen)
                        arr[k + templen] = arr[k]; //移动元素 
                    arr[k + templen] = temp; //插入元素 
                }
            }
        }
    } while (templen > 1); //必须大于1，因为1个数的分组没有意义 
}


int len, arr[1010];
int main() {
    cin >> len;
    for (int i = 1; i <= len; i++)
        cin >> arr[i];
    shell_sort(arr, len);
    for (int i = 1; i <= len; i++)
        cout << arr[i] << " ";
    return 0;
}

五、归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。代价是需要额外的内存空间。若将两个有序表合并成一个有序表。 该算法时间复杂度为 $O(nlogn)$。

归并排序算法的原理如下：

• $1$、把长度为 $n$ 的输入序列分成两个长度为 $\frac{n}{2}$ 的子序列；

• $2$、对这两个子序列分别采用归并排序；

• $3$、将两个排序好的子序列合并成一个最终的排序序列。

代码如下：

#include <iostream>
#include <cstdio>
using namespace std;

// 归并排序
int temp[1010]; //辅助空间 
void MergeSort(int arr[], int start, int end) { //start和end分别是左边界和右边界
    if (start >= end) return;
    int mid = (start + end) / 2, i = start, j = mid + 1;
    MergeSort(arr, start, mid); //分成两个子序列 
    MergeSort(arr, mid + 1, end);

    // 合并两个有序序列
    int k = 1; // 表示辅助空间有多少个元素
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++]; //把剩下数的合并
    while (j <= end) temp[k++] = arr[j++]; //同上 
    // 把辅助空间的数据放到原空间
    for (int i = start; i <= end; i++)
        arr[i] = temp[i - start + 1];
}

int len, arr[1010];
int main() {
    cin >> len;
    for (int i = 1; i <= len; i++)
        cin >> arr[i];
    MergeSort(arr, 1, len);
    for (int i = 1; i <= len; i++)
        cout << arr[i] << " ";
    return 0;
}

六、快速排序

快速排序通常明显比其他 $Ο(nlogn)$ 算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。快速排序的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。一趟快速排序的具体过程可描述为：从待排序列中任意选取一个记录作为基准值，然后将记录中关键字比它小的记录都安置在它的位置之前，将记录中关键字比它大的记录都安置在它的位置之后。这样，以该基准值为分界线，将待排序列分成的两个子序列。它是处理大数据最快的排序算法之一了。该算法时间复杂度为 $Ο(nlogn)$。

快速排序算法的原理如下：

• $1$、从数列中挑出一个元素，称为 “基准”（pivot）;

• $2$、重新排序数列，所有元素比基准值小的摆放在基准左边，所有元素比基准值大的摆在基准的右边（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

• $3$、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码如下：

#include <bits/stdc++.h>
using namespace std;

// 快速排序
void QuickSort(int arr[], int start, int end) {
    if (start >= end) return; //分完了 
    int i = start, j = end, pivot = arr[(start + end + 1) / 2]; //基准数
    while (i <= j) {
        while (arr[i] < pivot) i++; //从左向右找比基准数大的数
        while (arr[j] > pivot) j--; //从右向左找比基准数小的数
        if (i <= j) swap(arr[i++], arr[j--]); //进行交换
    }
    //分成两个子序列接着进行快速排序 
    if(start < j) QuickSort(arr, start, j); //遍历左边 
    if(i < end) QuickSort(arr, i, end); //遍历右边 
}

int len, arr[100010];
int main() {
    cin >> len;
    for (int i = 1; i <= len; i++)
        cin >> arr[i];
    QuickSort(arr, 1, len);
    for (int i = 1; i <= len; i++)
        cout << arr[i] << " ";
    return 0;
}

七、堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：每个结点的值都大于等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于等于其左右孩子结点的值，称为小顶堆。该算法时间复杂度为 $O(nlogn)$。

堆排序算法的原理如下：

• $1$、每次往堆里面插入一个数，首先先放在堆低（即第 $R[len+1]$）。

• $1$、之后向这个元素的父节点进行访问，如果父节点的值大于它，则交换两个值。一直重复操作，直到父节点的值比它小。

• $3$、如果要进行删除，先把堆顶元素（即 $R_1$）变成 $R_{len}$，长度 $-1$（即 $len-1$）。

• $4$、之后与它的儿子进行判断。如果它有两个儿子，则访问值较小的那个儿子，如果它的值比它儿子的值大，则交换，否则结束。如果它只有一个儿子，如果它的值比它儿子的值大，则交换，否则结束。如果它没有儿子，则直接结束。

• $5$、每次向找到最小值，可以拿出堆顶元素（即 $R_1$） ，每次查找完毕后，进行删除，删除 $n$ 次之后，排序结束。

代码如下：

#include <bits/stdc++.h>
using namespace std;

//堆排序
int heap[1010], length;
void up(int x) {
    heap[++length] = x;
    int temp = length;
    while (temp > 1 && heap[temp] < heap[temp / 2]) {
        swap(heap[temp / 2], heap[temp]);
        temp /= 2;
    }
}

void down() {
    heap[1] = heap[length--];
    int temp = 1;
    while (temp * 2 <= length) {
        if (temp * 2 + 1 <= length && heap[temp * 2] < heap[temp * 2 + 1]) temp = temp * 2;
        else if (temp * 2 + 1 <= length && heap[temp * 2] >= heap[temp * 2 + 1]) temp = temp * 2 + 1;
        else if (temp * 2 + 1 > length && temp * 2 <= length) temp = temp * 2;
        else break;
        if (heap[temp / 2] < heap[temp]) break;
        else swap(heap[temp / 2], heap[temp]);
    }
}

void heap_sort(int arr[], int len) {
    for (int i = 1; i <= len; i++)
        up(arr[i]);
    for (int i = 1; i <= len; i++) {
        arr[i] = heap[1];
        down();
    } 
} 

int len, arr[1010];
int main() {
    cin >> len;
    for (int i = 1; i <= len; i++)
        cin >> arr[i];
    heap_sort(arr, len);
    for (int i = 1; i <= len; i++)
        cout << arr[i] << " ";
    return 0;
}

八、计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。计数排序不是基于比较的排序算法。而是作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。当输入的元素是 $n$ 个 $0$ 到 $k$ 之间的整数时，它的运行时间是 $O(n + k)$。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组 $C$ 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。该算法时间复杂度为 $O(n+k)$。

计数排序算法的原理如下：

• $1$、找出待排序的数组中最大和最小的元素。

• $2$、统计数组中每个值为 $i$ 的元素出现的次数，存入数组 $C$ 的第 $i$ 项。

• $3$、对所有的计数累加（从 $C$ 中的第一个元素开始，每一项和前一项相加）。

• $4$、反向填充目标数组：将每个元素i放在新数组的第 $C(i)$ 项，每放一个元素就将 $C(i)$ 减去 $1$。

#include <bits/stdc++.h>
using namespace std;

//计数排序 
void counting_sort(int arr[], int len) {
    int t[110], k = 1;
    memset(t, 0, sizeof(t));
    for (int i = 1; i <= len; i++)
        t[arr[i]]++;
    for (int i = 0; i <= 100; i++)
        while(t[i]--) arr[k++] = i;
}

int len, arr[1010];
int main() {
    cin >> len;
    for (int i = 1; i <= len; i++)
        cin >> arr[i];
    counting_sort(arr, len);
    for (int i = 1; i <= len; i++)
        cout << arr[i] << " ";
    return 0;
}

九、桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。为了使桶排序更加高效，我们需要做到这两点：在额外空间充足的情况下，尽量增大桶的数量；使用的映射函数能够将输入的 $N$ 个数据均匀的分配到 $K$ 个桶中。该算法时间复杂度为 $O(n+k)$。

桶排序算法的原理如下：

• $1$、设置一个定量的数组当作空桶；

• $2$、遍历输入数据，并且把数据一个一个放到对应的桶里去；

• $3$、对每个不是空的桶进行排序；

• $4$、从不是空的桶里把排好序的数据拼接起来。

代码如下：

#include <bits/stdc++.h>
using namespace std;

//桶排序 
void Bucket_sort(int arr[], int len) {
    int t[1010], k = 1;
    memset(t, 0, sizeof(t));
    for (int i = 1; i <= len; i++)
        t[arr[i]]++;
    for (int i = 0; i <= 1000; i++)
        while(t[i]--) arr[k++] = i;
}

int len, arr[1010];
int main() {
    cin >> len;
    for (int i = 1; i <= len; i++)
        cin >> arr[i];
    Bucket_sort(arr, len);
    for (int i = 1; i <= len; i++)
        cout << arr[i] << " ";
    return 0;
}

十、基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。该算法时间复杂度为 $O(n+k)$。

基数排序算法的原理如下：

• $1$、取得数组中的最大数，并取得位数；

• $2$、$arr$ 为原始数组，从最低位开始取每个位组成radix数组

• $3$、对 $radix$ 进行计数排序（利用计数排序适用于小范围数的特点）。

代码如下：

#include <bits/stdc++.h>
using namespace std;

/* 基数排序
 * 1.求出数组中最大的元素
 * 2.求出最大元素是几位数, 设为i位
 * 3.对所有的数进行i轮排序. 
 *   首先排个位, 然后是十位, 然后百位
 * 4.每一轮的排位都需要分桶, 桶是有顺序的,
 *   然后把桶里的数按顺序放入原来的数组中.
 * 5.直到i轮排序结束后, 数组排序完成.      */

/*获取数字的位数*/
int figure(int num) {
    int sum = 0, temp = num;
    while(temp) {
        sum++;
        temp /= 10;
    }

    return sum;
}

/*查询数组中的最大数*/
int MAX(int *a, int n) {
    int Max = a[0];
    for (int i = 1; i < n; i++)
        if(a[i] > Max) Max = a[i];
    return Max;
}

/*将数字分配到各自的桶中, 然后按照桶的顺序输出排序结果*/
void sort2(int *a, int n, int loop) {
    int *buckets[10] = {NULL};
    int c[10] = {0};
    int d[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
    int k = 0, row, temp = d[loop-1];
    /*统计每个桶的元素个数*/
    for (int i = 0; i < n; i++) {
        row = (a[i] / temp) % 10;
        c[row]++;
    }
    /*为每个桶分配空间*/
    for (int i = 0; i < 10; i++)
        buckets[i] = (int *)malloc(c[i]*sizeof(int));
    memset(c, 0x00, sizeof(c));
    /*将数组中的数据分配到桶中*/
    for (int i = 0; i < n; i++) {
        row = (a[i] / temp) % 10;
        buckets[row][c[row]] = a[i];
        c[row]++;
    }
    /*将桶中的数, 倒回到原有数组中*/
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < c[i]; j++) 
            a[k++] = buckets[i][j];
    /*释放桶内存*/
    for (int i = 0; i < 10; i++) {
        free(buckets[i]);
        buckets[i] = NULL;
    }
}

/*基数排序*/
void sort3(int *a, int n) {
    int m = MAX(a, n);
    int loop = figure(m);
    for (int i = 1; i <= loop; i++)
        sort2(a, n, i);
}

int a[1010], len;
int main() {
    cin >> len;
    for (int i = 0; i < len; i++)
        cin >> a[i];
    int *p = a;
    sort3(p, len);
    for(int i = 0; i < len; i++)
        cout << a[i] << " ";
    return 0;
}

制作不易（早饭都没吃，写了三个多小时），点个赞吧！球球啦！