格言：自立才能自主，靠人更须靠己。有志之人立长志，无志之人常立志。千里之行，始于足下；艰难困苦，玉汝于成。少壮不努力，老大徒伤悲。✊✊✊
如果您觉得文章里有错误的地方，欢迎指正！和大家一起学习，共同进步
如果感觉博主的文章还不错的话，还请关注、点赞、收藏三连支持一下博主哦

目录

一.冒泡排序（时间复杂度为O（n^2））

什么是冒泡排序？

举个例子：把2 4 3 1通过冒泡排序变成1 2 3 4

二.插入排序（时间复杂度为O(n^2)或O(n)）

什么是插入排序？

举个例子：把2,4,3,1用插入排序的方法进行从小到大的排序

三.选择排序（时间复杂度为O(n^2)）

什么是选择排序？

还是这个例子：把2,4,3,1用选择排序的方法进行从小到大的排序

四.快速排序（时间复杂度为O(nlogn)~ O(n^2)）

什么是快速排序？

先来看个动图吧

又是这个例子：把2,4,3,1用快速排序的方法进行从小到大的排序

五.归并排序（时间复杂度为O(n log n)）

什么是归并排序？

又又是这个例子：把2,4,3,1用归并排序的方法进行从小到大的排序

六.堆排序（时间复杂度为O(nlogn)~ O(n^2)）

什么是堆排序？

解释一下什么是堆

又又又是这个例子（看今天我能打出多少个又字（这个又字不算））：把2,4,3,1用堆排序的方法进行从小到大的排序（这个有点难）

七.希尔排序（时间复杂度为O(n^(2/3))）

什么是希尔排序？

动图展示：

又又又又是这个例子：把2,4,3,1用希尔排序的方法进行从小到大的排序

八.计数排序（时间复杂度为O(n*log(n))）

什么是计数排序？

计数排序的思想

计数排序的方法步骤

动图：

又又又又又是这个例子：把2,4,3,1用计数排序的方法进行从小到大的排序

九.桶排序（时间复杂度为O(n)）

什么是桶排序？

基本思想

动图：

又又又又又是这个例子：把2,4,3,1用桶排序的方法进行从小到大的排序（六个又，嘿嘿）

十.基数排序（时间复杂度为O (nlog(r)m)，最后一个了，挺住）

什么是基数排序？

动图

方法

把103,11,9,3,25这五个数按照基数排序的方法进行从小到大的输出

看完这个博客，估计大家得对2 4 3 1这四个数产生心理阴影了

有点小长，但希望大家可以耐心看完，一定会对你的编程之路有所帮助(#^.^#)

一.冒泡排序（时间复杂度为O（n^2））

什么是冒泡排序？

依次比较两个相邻的子元素，如果他们的顺序错误就把他们交换过来，重复地进行此过程直到没有相邻元素需要交换，即完成整个冒泡

举个例子：把2 4 3 1通过冒泡排序变成1 2 3 4

首先我们先定义一个数组来存放这四个数据：

int arr[] = {2, 4, 3, 1};

这个大家应该都能看得懂，然后比较第一个元素和第二个元素，如果后面的大就把这两个数交换，反之则不变。很显然，这里应该是不用交换的。最后就是这样的（没有变化）：

2 4 3 1

交换可以用以下代码：

int tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;

然后我们再来处理第二个元素以及第三个元素，可以发现是前面的大，所以需要交换，交换后为：

2 3 4 1

最后比较第三个元素以及第四个元素，可以发现前面的元素大，所以需要交换，交换后为：

2 3 1 4

这样我们就完成了第一次冒泡排序，但你再仔细看看，答案是我们理想状态下的1 2 3 4么？？？

注意我刚刚说的话，这仅仅是第一次，下面进行第二次冒泡排序：

因为4已经在末尾了，是我们的理想位置，所以这次我们只需要对前面三个数进行冒泡排序就行了

这次排序的数值为以下三个数：

2 3 1

前面两个数因为第二个元素比第一个元素大，所以不需要交换，但是第二个元素比第三个元素大，所以需要交换，交换完成后也就是：

2 1 3

加上刚刚没算的4就是：

2 1 3 4

这四个数的位置好像也不是我们的理想答案，下面进行第三次冒泡排序：

这次只看前两位就行，因为后两位的位置已经是理想位置了，来看前两位，2和1，第一个元素更大，所以需要交换，加上后面的3,4就是

1 2 3 4

这样一个简单的冒泡排序就完成了，以下是C++的示例代码，大家可以看一下：

#include using namespace std;void bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {for (int j = 0; j  arr[j+1]) {int tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}}int main(){int arr[] = {2, 4, 3, 1};int n = sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, n);cout << "排序后的数组：\n";for (int i = 0; i < n; i++) {cout << arr[i] << " ";}cout << endl;return 0;}

解释一下： 

- 首先定义一个名为 `bubbleSort` 的函数，该函数接受一个整数数组和数组长度 n 作为输入，并将其按照从小到大的顺序进行排序。- 然后使用两重循环，第一重循环用来控制排序轮数，第二重循环用来控制每轮比较的次数。- 内部循环中，如果相邻两个元素的顺序不符合从小到大的顺序，就将它们交换位置。- 最后返回已排序数组。在 `main()` 函数中，定义了一个 `arr` 数组，包含了题目中给出的四个数字，然后调用 `bubbleSort` 函数，将排序后的数组打印出来。

二.插入排序（时间复杂度为O(n^2)或O(n)）

什么是插入排序？

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动

举个例子：把2,4,3,1用插入排序的方法进行从小到大的排序

第一次：有序表：2 ， 无序表为：4,3,1

首先把2当做有序表中的第一项，然后从后往前遍历无序表，把遍历的结果4与无序表中的2作比较，很明显是4大，故将2插入在4的前面，就是有序表的第一个位置，得到新的有序表：

2，4

第二次：有序表：2，4 ， 无序表为：3，1

从后往前遍历无序表，把遍历的结果3与无序表中的2,4作比较，发现2 < 3 < 4，故将3插入在2的后面，3的前面，最后得到新的有序表：

2,3,4

第三次：有序表：2，3，4 ， 无序表为：1

从后往前遍历无序表，把遍历的结果1与无序表中的2,3,4作比较，发现1 < 2 < 3 < 4，故将1插入在2的前面，3的前面，4的前面，也就是插入到最前面，最后得到新的有序表：

1，2,3,4

这样我们就完成了插入排序，怎么样，很简单吧！

以下是C++的实例代码，大家啊可以看一下（用vector做的）

#include #include using namespace std;vector insertion_sort(vector arr) {int n = arr.size();for (int i = 1; i = 0 && arr[j] > key) {arr[j+1] = arr[j];j--;}arr[j+1] = key;}return arr;}int main() {vector arr = {2, 4, 3, 1};vector sorted_arr = insertion_sort(arr);for (int num : sorted_arr) {cout << num << " ";}cout << endl;return 0;}

解释一下：

- 首先定义一个名为 `insertion_sort` 的函数，该函数接受一个整数数组作为输入，并返回已排序的数组。- 在函数中，使用变量 `n` 来记录输入数组的长度。- 对于每个待排序的元素（从下标1开始），将其插入到已排序序列的相应位置中。- 内部循环中，从已排序序列的尾部开始，向前遍历序列，将比待排序元素大的元素依次往后移。- 当找到待排序元素应该插入的位置后，将其插入到该位置中。- 最后返回已排序序列。在 `main()` 函数中，定义了一个 `arr` 数组，包含了题目中给出的四个数字，然后调用 `insertion_sort` 函数，将排序后的数组打印出来。

三.选择排序（时间复杂度为O(n^2)）

什么是选择排序？

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

还是这个例子：把2,4,3,1用选择排序的方法进行从小到大的排序

首先定义一个数组：

int arr[] = {2, 4, 3, 1};
  • 第一次：遍历整个数组，找出这个数组中后三位的最小值，把它与第一个数互换，这里最小值为1，第一个数也为2，于是就把它俩交换，最后数组变成了一下顺序

第一次：

1,4,3,2
  • 第二次：遍历整个数组，找出这个数组中后两位的最小值，把它与第二个数互换，这里最小值为2，第二个数也为4，所以就把这两个数交换，最后数组变成了一下顺序

第二次：

1,2,3,4
  • 第三次：遍历整个数组，找出这个数组中最后一位的最小值，把它与第三个数互换，但这里最小值为4，第三个数也为3，最小数比第三个数还要大，故不做交换，最后数组变成了一下顺序

第三次：

1,2,3,4

这样我们就完成了插入排序的学习，以下是C++的代码，大家可以看一下（用vector）：

#include #include using namespace std;vector selection_sort(vector arr) {int n = arr.size();for (int i = 0; i < n-1; i++) {int min_index = i;for (int j = i+1; j < n; j++) {if (arr[j] < arr[min_index]) {min_index = j;}}swap(arr[i], arr[min_index]);}return arr;}int main() {vector arr = {2, 4, 3, 1};vector sorted_arr = selection_sort(arr);for (int num : sorted_arr) {cout << num << " ";}cout << endl;return 0;}

解释一下：

- 首先定义一个名为 `selection_sort` 的函数，该函数接受一个整数数组作为输入，并返回已排序的数组。- 在函数中，使用变量 `n` 来记录输入数组的长度。- 外部循环中，用变量 `i` 遍历整个数组，表示选择已排序数组的末尾位置。- 内部循环中，找到未排序数组中最小的元素的下标 `min_index`，并将其保存下来。- 最后将未排序数组中最小元素的值与已排序数组的末尾位置进行交换。- 最后返回已排序数组。在 `main()` 函数中，定义了一个 `arr` 数组，包含了题目中给出的四个数字，然后调用 `selection_sort` 函数，将排序后的数组打印出来

四.快速排序（时间复杂度为O(nlogn)~ O(n^2)）

什么是快速排序？

快速排序（Quicksort），计算机科学词汇，适用领域Pascal，c++等语言，是对冒泡排序算法的一种改进

也就是说，快速排序是冒泡排序的改进，是基于冒泡排序的（这也就是我为什么先讲了冒泡排序）

先来看个动图吧

又是这个例子：把2,4,3,1用快速排序的方法进行从小到大的排序

差不多就是上图的这个意思（这个我就不写那么细了，因为平时根本用不到）

1. 选择第一个元素 2 作为基准元素。2. 从数组左侧开始查找大于等于基准元素的数，找到 3。3. 从数组右侧开始查找小于基准元素的数，找到 1。4. 交换找到的两个数，此时数组变为 1,2,3,4。5. 重新选择基准元素，选择第二个元素 1，重复以上步骤。6. 最终得到一个有序序列 1,2,3,4。

以下是C++的实例代码，大家可以看一下：

#include #include using namespace std;int partition(vector& arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(arr[i], arr[j]);}}swap(arr[i+1], arr[high]);return i+1;}void quick_sort(vector& arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);quick_sort(arr, low, pi-1);quick_sort(arr, pi+1, high);}}int main() {vector arr = {2, 4, 3, 1};int n = arr.size();quick_sort(arr, 0, n-1);for (int i = 0; i < n; i++) {cout << arr[i] << " ";}cout << endl;return 0;}

解释一下：

- 首先定义一个名为 `partition` 的函数，该函数接受一个整数向量 `arr`，以及 `low` 和 `high` 两个整数，返回排序后的 `arr`。- 在函数中，将序列中最后一个元素设为基准 `pivot`。- 定义变量 `i` 表示分割点的位置，初始化为 `low - 1`。- 对于序列中 `low` 到 `high-1` 的元素，比较其是否小于基准值 `pivot`，若小于，则将其交换至已处理区间的结尾。- 将基准值交换至 `i+1` 的位置。- 返回分割点的位置。- 定义一个名为 `quick_sort` 的函数，该函数接受一个整数向量 `arr`，以及 `low` 和 `high` 两个整数，表示待排序序列的开始和结束位置。- 在函数中，若序列的长度大于1，使用 `partition` 函数将数组分为两部分（左边的数都小于右边的数）。- 对左边的部分和右边的部分递归进行快速排序。- 在 `main()` 函数中，定义了一个 `arr` 数组，包含了题目中给出的四个数字，然后调用 `quick_sort` 函数将其从小到大排序，最后输出排序后的结果。使用快速排序对 2, 4, 3, 1 进行排序，最终输出结果为 1 2 3 4

五.归并排序（时间复杂度为O(n log n)）

什么是归并排序？

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

归并排序是一种分治思想的排序算法，它将待排序序列拆分为若干个子序列，对每个子序列进行排序，最后将子序列两两合并，得到一个有序序列。具体步骤如下：1. 分解：将待排序序列拆分为若干个子序列，每个子序列的长度为1。2. 合并：将相邻的两个子序列合并成一个有序序列，重复这个过程知道所有的子序列都合并为一个完整的有序序列。在归并排序中，最复杂的部分是将两个有序的子序列合并为一个有序的序列。在合并时，可以先定义一个临时数组用于存储合并后的序列，然后从两个子序列的开头开始比较它们的元素大小，将较小的元素先存入临时数组中。当其中一个序列已经全部放入临时数组时，将另一个序列中剩余的元素依次放入临时数组中即可

又又是这个例子：把2,4,3,1用归并排序的方法进行从小到大的排序

1. 初始状态为2,4,3,1。2. 将序列拆分为2,4和3,1两个子序列。3. 递归拆分2,4子序列为单个元素2和4。4. 将2,4子序列中的元素按大小合并为有序序列2,4。5. 递归拆分3,1子序列为单个元素3和1。6. 将3,1子序列中的元素按大小合并为有序序列1,3。7. 将2,4和1,3有序序列按大小合并为4个元素的有序序列1,2,3,4。最终得到的有序序列为1, 2, 3, 4。

以下是C++的代码，大家可以看一下：

#include #include using namespace std;void merge(vector& arr, int l, int m, int r) {int n1 = m - l + 1;int n2 = r - m;vector L(n1), R(n2);for (int i = 0; i < n1; i++) {L[i] = arr[l+i];}for (int j = 0; j < n2; j++) {R[j] = arr[m+j+1];}int i = 0, j = 0, k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k++] = L[i++];} else {arr[k++] = R[j++];}}while (i < n1) {arr[k++] = L[i++];}while (j < n2) {arr[k++] = R[j++];}}void merge_sort(vector& arr, int l, int r) {if (l < r) {int m = l + (r-l)/2;merge_sort(arr, l, m);merge_sort(arr, m+1, r);merge(arr, l, m, r);}}int main() {vector arr = {2, 4, 3, 1};int n = arr.size();merge_sort(arr, 0, n-1);for (int i = 0; i < n; i++) {cout << arr[i] << " ";}cout << endl;return 0;}

解释一下：

- 首先定义一个名为 `merge` 的函数，该函数接受一个整数向量 `arr`，以及 `l`、`m` 和 `r` 三个整数，表示要对 `arr` 的从 `l` 到 `m` 和从 `m+1` 到 `r` 这两个有序子序列进行归并，最终返回排序后的 `arr`。- 在函数中，将 `arr` 分别分为前一半 `L` 和后一半 `R`，将它们排序合并到 `arr` 中。- 定义变量 `i`、`j` 和 `k` 来分别对 `L`、`R` 和 `arr` 进行遍历和合并操作。- 最终返回排序后的 `arr`。- 定义一个名为 `merge_sort` 的函数，该函数接受一个整数向量 `arr`，以及 `l` 和 `r` 两个整数，表示待排序序列的开始和结束位置。- 在函数中，若序列的长度大于 1，使用 `merge_sort` 函数将数组分为两部分并递归排序，最终将这两部分进行合并。- 在 `main()` 函数中，定义了一个 `arr` 数组，包含了题目中给出的四个数字，然后调用 `merge_sort` 函数将其从小到大排序，最后输出排序后的结果。使用归并排序对 2, 4, 3, 1 进行排序，最终输出结果为 1 2 3 4。

六.堆排序（时间复杂度为O(nlogn)~ O(n^2)）

什么是堆排序？

堆排序（英语:Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

解释一下什么是堆

堆是一种叫做完全二叉树的数据结构，可以分为大根堆，小根堆，而堆排序就是基于这种结构而产生的一种程序算法

又又又是这个例子（看今天我能打出多少个又字（这个又字不算））：把2,4,3,1用堆排序的方法进行从小到大的排序（这个有点难）

1. 将待排序序列构建成一个二叉堆。以从小到大排序为例，可将序列构建成一个最大堆。最大堆的每个节点的值都大于等于其子节点的值。2. 待排序序列的首尾元素交换，然后将剩下的元素重新构建成一个二叉堆。3. 重复执行步骤2，直至排序完成。以2,4,3,1为例，下面是一步一步构建最大堆的过程：1. 将序列构建成一个完全二叉树：
 2/ \ 4 3/ 1
2. 从最后一个非叶子节点开始，依次将其与其子节点进行比较，确保最大堆的性质。在本例中，最后一个非叶子节点为节点1，即数字4。3. 将节点1与其左右子节点进行比较。因为节点1的值比其左右子节点都大，所以节点1的值不变。4. 将节点0与其左右子节点进行比较。因为节点0的值比其右子节点小，所以节点0和其右子节点进行交换。5. 交换节点0和2的值。6. 将节点0与其左右子节点进行比较。因为节点0的值比其子节点都大，所以节点0的值不变。7. 最大堆构建完成，得到序列4,2,3,1。最终进行堆排序，具体步骤如下：1. 构建最大堆。得到序列4,2,3,1。2. 将序列首尾元素互换，得到序列1,2,3,4。3. 以除去最后一个元素的序列重建最大堆，得到序列3,2,1。4. 将序列首尾元素互换，得到序列1,2,3。5. 以除去最后两个元素的序列重建最大堆，得到序列2,1。6. 将序列首尾元素互换，得到序列1,2。7. 完成排序，得到序列1,2,3,4。

听懂了吗，没听懂的也不用着急，这个的确有点难

以下是C++的代码，大家可以看一下：

#include using namespace std;void heapAdjust(int a[], int i, int n) {int child, tmp;for (tmp = a[i]; 2 * i + 1 < n; i = child) {child = 2 * i + 1;if (child + 1 < n && a[child]  tmp) { //比较节点和较大的子节点的值a[i] = a[child];} else {break;}}a[i] = tmp;}void heapSort(int a[], int n) {for (int i = n / 2 - 1; i >= 0; i--) {//初始堆的建立heapAdjust(a, i, n);}for (int i = n - 1; i >= 1; i--) {//排序过程swap(a[0], a[i]); //最后一个元素和堆顶元素交换位置heapAdjust(a, 0, i);//调整堆}}int main() {int a[] = {2, 4, 3, 1};int n = sizeof(a) / sizeof(int);heapSort(a, n);for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;return 0;}

解释一下： 

这段C++代码实现了堆排序算法，用于对输入的数组进行从小到大的排序。它包含两个函数：1. `heapAdjust`函数这个函数用于调整堆的结构，以确保它满足最大堆的性质。它的参数包括：- `a[]`表示待排序的数组。- `i`表示要调整的节点的下标。- `n`表示堆的长度。函数的核心思想是通过比较节点和其子节点之间的值的大小，找到其中的最大值，并将节点调整到合适的位置，以此达到调整堆的目的。2. `heapSort`函数这个函数用于对序列进行排序。它的参数包括：- `a[]`表示待排序的数组。- `n`表示数组的长度。在函数的实现过程中，首先将数组构建成一个初始堆，然后不断地将堆顶元素和最后一个元素互换位置，并调整堆的结构，最终完成排序。最后的`main`函数用于先定义一个待排序的数组，调用`heapSort`函数进行排序，并输出结果到标准输出流中。

七.希尔排序（时间复杂度为O(n^(2/3))）

什么是希尔排序？

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止

动图展示：

又又又又是这个例子：把2,4,3,1用希尔排序的方法进行从小到大的排序

咱们先看这个数组的长度，再把这个数组长度/2，也就是把4/2，也就是2，意味着这个数组将被分成两组：

第一组：2,3第二组：4,1

对这两组进行插入排序，结果如下，像1,2这样的小元素就被调到前面了，然后继续缩小增量：gap = 2 / 2 = 1,数组最后就被分成了一组：

1,2,3,4

以下是C++的代码，大家可以看一下：

#include using namespace std;void shellSort(int arr[], int n) {// 初始步长for (int gap = n / 2; gap > 0; gap /= 2) {// 从gap位置开始，对每个序列进行插入排序for (int i = gap; i = gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}}int main() {int arr[] = {2, 4, 3, 1};int n = sizeof(arr) / sizeof(int);shellSort(arr, n);for (int i = 0; i < n; i++) {cout << arr[i] << " ";}cout << endl;return 0;}

解释一下：

这段代码先定义了一个`shellSort`函数来实现希尔排序，其参数包括需要排序的数组和其长度。希尔排序是对插入排序的改进，它将原来的序列分为若干个序列进行排序，这些序列的相邻元素的步长逐渐缩小，直到步长为1。代码中指定的初始步长为序列长度的一半，然后逐渐缩小步长直至为1。希尔排序的实现需要嵌套两个循环，外层循环控制步长的缩减，内层循环则是对每个子序列进行插入排序。最后的`main`函数用于定义一个待排序的数组，调用`shellSort`函数进行排序，并输出结果到标准输出流中。

八.计数排序（时间复杂度为O(n*log(n))）

什么是计数排序？

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）

计数排序的思想

计数排序的核心是：利用数组的索引是有序的，通过将序列中的元素作为索引，其个数作为值放入数组，遍历数组来排序

计数排序的方法步骤

1、从无序数组中取出最大值max，新建一个长度为max+1的数组

2、遍历无序数组，取其中元素作为新建数组的索引，存在一个则新数组该索引所在的值自增

3、遍历新数组，当存在不为0的元素，取该元素的索引放入最终数组，并且该元素自减，直到为0，返回最终数组

动图：

又又又又又是这个例子：把2,4,3,1用计数排序的方法进行从小到大的排序

非常简单，让我们遍历这个无序的随机数列，每一个整数按照其值对号入座，对应数组下标的元素进行加1操作

第一次：第一个数为2，那么数组下标为2的元素加1：

1 0 0 02 4 3 1

第二次：第二个是为4，所以我们就把数组下标为4的元素加1：

1 1 0 02 4 3 1

大家现在应该就能发现，最后下标位置的值应该为（执行四次以后）：

1 1 1 12 4 3 1

最后我们直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次：

1 2 3 4

但是这样感觉这样不太明显，我感觉还是动图比较好，不会可以私我，我单独给你讲（先看动图）

以下是C++的代码，大家可以看一下：

#includeusing namespace std;void CountSort(int a[], int n, int maxVal) {int* count = new int[maxVal+1];for (int i = 0; i <= maxVal; i++) count[i] = 0;for (int i = 0; i < n; i++)count[a[i]]++;for (int i = 1; i = 0; i--) {temp[count[a[i]]-1] = a[i];count[a[i]]--;}for (int i = 0; i < n; i++) {a[i] = temp[i];}delete[] count;delete[] temp;}int main() {int a[] = {2,4,3,1};int n = 4;int maxVal = 4;CountSort(a, n, maxVal);for (int i = 0; i < n; i++) {cout << a[i] << " ";}return 0;}

解释一下： 

在这段代码中，函数 CountSort 接收一个数组 a，它的长度是 n，数组中最大的数值是 maxVal。首先创建一个长度为 (maxVal+1) 的计数数组 count，count[i] 表示值为 i 的元素在数组中出现的次数。然后扫描数组 a，对于每个 a[i]，将它的出现次数加 1。在第二个循环中，遍历计数数组 count，对于每个 i，计算小于等于 i 的元素数量并把结果保存在 count[i] 中。接下来，创建一个临时数组 temp，倒序遍历 a 数组，并将元素根据 count 数组中存储的信息放置到 temp 中。最后再将 temp 数组中的元素拷贝回 a 数组，完成排序。在 main 函数中调用 CountSort，排序数组 a，然后使用 cout 语句输出排序结果。

九.桶排序（时间复杂度为O(n)）

什么是桶排序？

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

基本思想

桶排序的想法近乎彻底的分治思想。桶排序假设数组均匀分布在一个范围内，并将这一范围划分为几个子范围（桶）。然后利用某种映射函数 f f f，将待排序的关键字 k k k映射到下标为 i i i的同种，那么该关键字 k k k就作为 B [ i ] B[i] B[i]中的元素。接着对每个桶的元素进行排序，并将其依次输出即可得到一个有序的序列。

映射函数一般采用:

也就是k = √n

动图：

又又又又又是这个例子：把2,4,3,1用桶排序的方法进行从小到大的排序（六个又，嘿嘿）

咱们先定义一个数组，定义大一点，防止数组越界(注意放在主函数main前，或者到后面把这个数组用memset函数初始化为0，个人建议选择第一种，因为打简单啊）：

int arr[1000];

第一次：第一个数为2，那我们就把下标为2元素的值加一

第二次：第一个数为4，那我们就把下标为4元素的值加一

第三次：第一个数为3，那我们就把下标为3元素的值加一

第四次：第一个数为1，那我们就把下标为1元素的值加一

最后我们遍历一下整个数组，只要元素的值不为0就输出（但是不一定哈，万一我把这些数存到别的数组里了呢，这样只要输出那个数组就行了），最后我们就可以得到以下结果（个人比较喜欢用这个排序，因为；它时间复杂度低啊，而且还容易理解）：

程序输出：1 2 3 4

以下是C++的代码，大家可以看一下：

#include#includeusing namespace std;void BucketSort(int a[], int n, int maxVal) {vector bucket[maxVal];for (int i = 0; i < n; i++) {bucket[a[i]-1].push_back(a[i]);}int k = 0;for (int i = 0; i < maxVal; i++) {int size = bucket[i].size();sort(bucket[i].begin(), bucket[i].end());for (int j = 0; j < size; j++) {a[k++] = bucket[i][j];}}}int main() {int a[] = {2,4,3,1};int n = 4;int maxVal = 4;BucketSort(a, n, maxVal);for (int i = 0; i < n; i++) {cout << a[i] << " ";}return 0;}

解释一下：

在这段代码中，函数 BucketSort 接收一个数组 a，它的长度是 n，最大的数值是 maxVal。首先创建一个 vector 数组 bucket，大小为 maxVal，每个桶表示不同的数值区间。扫描数组 a，对于每个 a[i]，将其放入相应的桶中。然后按照 bucket 数组的顺序，对每个桶内的数排序，最后将所有桶内的数按照顺序拷贝回原数组 a 中，完成排序。在 main 函数中调用 BucketSort，排序数组 a，然后使用 cout 语句输出排序结果。

十.基数排序（时间复杂度为O (nlog(r)m)，最后一个了，挺住）

什么是基数排序？

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法

动图

方法

都最后了，换个例子吧

把103,11,9,3,25这五个数按照基数排序的方法进行从小到大的输出

第一次以每个元素的个位放入对应的桶中

 11103,32590123 456789

将桶中的元素取出，放入元素组

数组为：11 103 3 25 9

第二次以每个元素的十位放入对应的桶中，没有十位的放入0号桶

103,3,9112501 23456789

将桶中的元素取出，放入元素组

数组为：103 3 9 11 25

第三次以每个元素的百位放入对应的桶中，没有百位的放入0号桶

3,9,11,251030123456789

将桶中的元素取出，放入元素组

数组为：3 9 11 25 103

结束输出数组

以下是C++的代码，大家可以看看：

#includeusing namespace std;int getMax(int a[], int n) {int maxVal = a[0];for (int i = 1; i  maxVal) {maxVal = a[i];}}return maxVal;}void CountSort(int a[], int n, int exp) {int* output = new int[n];int count[10] = {0};for (int i = 0; i < n; i++) {count[(a[i]/exp)%10]++;}for (int i = 1; i = 0; i--) {output[count[(a[i]/exp)%10]-1] = a[i];count[(a[i]/exp)%10]--;}for (int i = 0; i  0; exp *= 10) {CountSort(a, n, exp);}}int main() {int a[] = {103,11,9,3,25};int n = 5;RadixSort(a, n);for (int i = 0; i < n; i++) {cout << a[i] << " ";}return 0;}

解释一下：

在这段代码中，函数 getMax 接收一个数组 a 和数组长度 n，返回数组中最大的数值。函数 CountSort 接收一个数组 a，它的长度是 n，变量 exp 表示当前排序轮次，是一个 10 的幂次方。先创建一个长度为 10 的计数数组 count，用于统计数组中每个数值的出现次数。然后遍历 a 数组，将其按照当前轮次 exp 的数位进行排序，将排序结果保存在数组 output 中。最后将 output 数组中的值拷贝回 a 数组中，完成一轮排序。RadixSort 函数接收一个数组 a 和数组长度 n，用于进行多轮排序，从最低位开始，每次排序按照位数从小到大进行。在 main 函数中调用 RadixSort，排序数组 a，然后使用 cout 语句输出排序结果。

最后问大家一个小问题

脑筋急转弯：我一共打了多少个“又”字（别被误导，嘿嘿嘿）