数据结构初阶最终讲：排序

这一讲是数据结构初阶的最后一讲了，当然也是很有难度的一讲，是对于排序算法的总篇章，当然，会有其它更好的排序算法，但是对于初阶的数据结构来说，先学习这些就足够了

1.排序的概念及其运用

1.1什么是排序

排序，顾名思义，就是对一串数据，按照某个特定的顺序，将这一串数据进行有序排列的方法

1.2排序的运用

排序在我们日常生活中的使用十分广泛

当我们在网上购物，筛选自己心仪的产品时，就使用到了排序：

当我们在考试完后看自己的成绩排名时，也会用到排序：

1.3常见排序算法

下面是一些常见的排序算法，这一讲会将这些排序算法逐一实现

2.冒泡排序

冒泡排序对于教学来说很有意义，至少是我所学过的第一个排序算法，但是使用起来非常麻烦，它的时间复杂度为O(n^2)，是一个非常大的复杂度值了

//冒泡排序
void BubbleSort(int* arr, int n)
{//冒泡排序十分经典，而且使用很少，所以不再讲解，这里只会作为一个对比for (int i = 0; i < n-1; i++){int def = 0;for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);def = 1;}}//当没有一个数据交换时，表示已经排序完了，直接退出即可if (def == 0){break;}}
}

3.直接插入排序

上面是害怕大图会看不清，所以分成了三个小图，下面放大图：

我们会惊奇地发现，这个算法竟然和我们打扑克牌时整牌的操作一样！（至少和我是一样的）：

下面我们来使用代码实现这个思路：

//直接插入排序
void InsertSort(int* arr, int n)
{for (int i = 0; i < n-1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}

4.堆排序

之前我们已经实现过堆排序了，所以这里也不再详细说明堆排序，直接将代码拿过来：

链接: 堆排序链接

//交换函数
void Swap(HeapDataType* x, HeapDataType* y)
{HeapDataType tmp = *x;*x = *y;*y = tmp;
}//堆的向上排序
void ADJustUp(HeapDataType* arr, int child)
{int father = (child - 1) / 2;while (child > 0){//建大堆：>//建小堆：<if (arr[child] < arr[father]){Swap(&arr[child], &arr[father]);child = father;father = (child - 1) / 2;}else{break;}}
}//堆的向下排序
void ADJustDown(HeapDataType* arr, int father, int n)
{int child = father * 2 + 1;while (child < n){//大堆：寻找左右孩子中最大的那个孩子//小堆：寻找左右孩子中最小的那个孩子if (child + 1 < n && arr[child] < arr[child + 1]){child += 1;}//如果目标数据小/大的话，将最大的那个孩子与目标数据进行交换if (arr[father] < arr[child]){Swap(&arr[father], &arr[child]);father = child;child = father * 2 + 1;}else{break;}}
}//堆排序
void HeapSort(int* arr, int sz)
{//首先需要一个数据一个数据地拿出来，创建一个堆for (int i = 0; i < sz; i++){ADJustUp(arr, i);}//向下调整算法建堆int n = (sz - 1 - 1) / 2;for (int i = n; i >= 0; i--){ADJustDown(arr, i, sz);}//先交换数据int end = sz;while(end > 1){Swap(&arr[0], &arr[end - 1]);end--;//然后对堆中第一个数据进行向下排序ADJustDown(arr, 0, end);}
}

5.测试代码：排序性能对比

已经有了三种排序代码，哪一种排序的效率是最高的才是我们最想要看到的，所以我们需要一个测试排序性能的代码：

// 测试排序的性能对⽐
void TestOP()
{//-------------------1.----------------------//1,这里代表着生成十万个数据，方便后序进行排序//a1、a2、a3分别指代不同的排序方法srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);/*int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);*/int* a4 = (int*)malloc(sizeof(int) * N);/*int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);*/int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();/*a2[i] = a1[i];a3[i] = a1[i];*/a4[i] = a1[i];/*a5[i] = a1[i];a6[i] = a1[i];*/a7[i] = a1[i];}//-------------------1.----------------------//-------------------2.----------------------//2.clock是一个C语言中的函数，可以返回从程序开始运行到系现在所用的时间//用begin2 - begin1就可以得出算法运行的时间了int begin1 = clock();InsertSort(a1, N);int end1 = clock();/*int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();*/int begin4 = clock();HeapSort(a4, N);int end4 = clock();/*int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();*/int begin7 = clock();BubbleSort(a7, N);int end7 = clock();//-------------------2.----------------------//-------------------3.----------------------//3.最后将得出的时间进行打印并且销毁空间即可printf("InsertSort:%d\n", end1 - begin1);/*printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);*/printf("HeapSort:%d\n", end4 - begin4);/*printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);*/printf("BubbleSort:%d\n", end7 - begin7);free(a1);/*free(a2);free(a3);*/free(a4);/*free(a5);free(a6);*/free(a7);//-------------------3.----------------------
}

拥有了检测排序性能的函数之后，我们就可以直观地看出不同排序算法之间的效率差异了：

时间单位为毫秒，可以看出，冒泡排序竟然用了15秒！真是夸张，所以冒泡排序还是不足以应对生活中的排序的

5.1直接插入排序时间复杂度分析

//直接插入排序
void InsertSort(int* arr, int n)
{for (int i = 0; i < n-1; i++){//当外层循环一次时，内层循环最坏要交换i+1次，也就是下面的那样：//i        0  1  2  3  4  5  ...  n-1//循环次数 1  2  3  4  5  6  ...  n//循环次数是等差数列，求和并分析可以得出它的时间复杂度为O(n^2)//但是这个最坏情况是很难达到的，而冒泡排序两层循环，而且一一对比，为什么效率低很容易理解int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}

直接插入排序的时间消耗已经很不错了，但是还有一个人不满足，他想要优化插入排序，让插入排序更块，它就是希尔排序，我们来看：

6.希尔排序

然后是大图：

代码实现：

//希尔排序
void ShellSort(int* arr, int n)
{int gap = n;while(gap > 1){//当gap为3时，gap/3=1，所以刚循环一次就跳出循环，显然是不合理的，所以这里要+1gap = gap / 3 + 1;//注意：这里要考虑for循环中i的结束条件为什么是i<n-gap而不是i<n//当i = n-gap时，end+gap = n，此时已经发生了越界，所以i应该小于n-gapfor (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

此时我们再来看一下运行时间：

竟然是11秒，比堆排序花费的时间还少了，是不是很振奋！！！

6.1希尔排序时间复杂度分析

对于希尔排序的时间复杂度的求解到目前仍然是一个相对困难的事，但是它的时间复杂度大约是n的1.3次方，这是由大量数据平均得来的：

现在我们进行简单的推导：

7.选择排序

7.1初步思路

初步实现思路就是选择最小的数据，将最小的数据往前移

代码实现：

//选择排序
void SelectSort(int* arr, int n)
{//这里的i就能够充当begin的作用，所以不用创建变量beginfor (int i = 0; i < n; i++){int mini = i;//先寻找最小的数据的下标for (int j = i+1; j < n; j++){if (arr[j] < arr[mini]){mini = j;}}//找到最小的元素之后，交换Swap(&arr[mini], &arr[i]);}
}

7.2选择排序优化

7.2.1初步实现

上一个实现思路的时间复杂度为o(n^2)，非常的不好，所以我们要进行优化：再创建一个指针，保存最大的数据，将小数据和大数据一起排列：

代码实现：

//选择排序--优化后--初步实现
void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin;int maxi = begin;//寻找最大和最小的数据for (int i = begin+1; i < n; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}//然后将大小数据插入到合适的位置Swap(&arr[begin++], &arr[mini]);Swap(&arr[end--], &arr[maxi]);}
}

然而，当我们对数据进行排序时，我们会发现：出错了！！！为什么呢？我们来探讨一下：

7.2.2出错点1

查找时应该在begin–end范围内查找，而不是begin–n范围

//选择排序--优化后
void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin;int maxi = begin;//寻找最大和最小的数据//更改点1：查找范围出错，i<n ---> i<endfor (int i = begin+1; i < end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}//然后将大小数据插入到合适的位置Swap(&arr[begin++], &arr[mini]);Swap(&arr[end--], &arr[maxi]);}
}

7.2.3出错点2

代码实现：

//选择排序--优化后
void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin;int maxi = begin;//寻找最大和最小的数据//更改点1：查找范围出错，i<n ---> i<endfor (int i = begin+1; i < end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}//出错点2：考虑maxi==begin的情况if (maxi == begin){maxi = mini;}//然后将大小数据插入到合适的位置Swap(&arr[begin++], &arr[mini]);Swap(&arr[end--], &arr[maxi]);}
}

7.2.4出错点3

这个出错点和第一个出错点的位置一样，i的范围应该包括end，i<end是错的，只能是i<=end

代码更正：

//选择排序--优化后
void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin;int maxi = begin;//寻找最大和最小的数据//更改点1：查找范围出错，i<n ---> i<end//出错点3：i应该<=endfor (int i = begin+1; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}//出错点2：考虑maxi==begin的情况if (maxi == begin){maxi = mini;}//然后将大小数据插入到合适的位置Swap(&arr[begin++], &arr[mini]);Swap(&arr[end--], &arr[maxi]);}
}

7.2.5选择排序优化最终代码

//选择排序--优化后
void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin;int maxi = begin;//寻找最大和最小的数据//更改点1：查找范围出错，i<n ---> i<end//出错点3：i应该<=endfor (int i = begin+1; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}//出错点2：考虑maxi==begin的情况if (maxi == begin){maxi = mini;}//然后将大小数据插入到合适的位置Swap(&arr[begin++], &arr[mini]);Swap(&arr[end--], &arr[maxi]);}
}

7.3选择排序时间复杂度分析

选择排序外循环每次循环一次，内循环都要走一遍，所以它的时间复杂度为O(n^2)，时间复杂度太差，所以一般不用这个排序，只是让我们了解这个排序，并且直到这个排序算法并不理想，接着我们看一下排十万个数据的时间吧：

可以看出，当冒泡排序时间才为4秒时，选择排序就排了3秒，所以说不好用，下面我们就要讲一个排序的"神"算法–快速排序，也就是我们熟知的快排

8.快速排序–Hoare版本

看起来十分难懂啊，我们不用管这些，让我画图进行理解：

8.1.1代码的初步实现

//快速排序
//寻找基值的函数，返回基值的下标
int _QuickSort(int* arr, int left, int right)
{int key = 0;while (left <= right){//找出比基值大的数据while(arr[left] < arr[key]){//当找到的数据比基值小时，往后找，直到找到比基值大的数据left++;}//找出比基值小的数据while (arr[right] > arr[key]){//当找到的数据比基值大时，往前找，直到找到比基值小的数据right--;}//然后将大小数据进行交换Swap(&arr[left], &arr[right]);}//最后将基值赋值到right，right就成为了基值下标Swap(&arr[key], &arr[right]);return right;
}//与其他排序方法不同，这里应该传入数组、排序区域的左区间、排序区域的右区间
void QuickSort(int* arr, int left, int right)
{//递归结束条件//当left和right重合时，表示此时只有一个结点，退出递归if (left >= right){return;}//寻找基值int key = _QuickSort(arr, left, right);//递归寻找基值QuickSort(arr, left, key-1);QuickSort(arr, key + 1, right);
}

8.1.2错误点1

第五行代码我们竟然就已经出错了，做题一定要仔细！

//快速排序
//寻找基值的函数，返回基值的下标
int _QuickSort(int* arr, int left, int right)
{//错误点1：key应该等于left，指向的是排序数组中的第一个数据，而不是整个数组中的第一个数据int key = left;

8.1.3错误点2

仍然是第五行，而且还是特别明显的错误：

//快速排序
//寻找基值的函数，返回基值的下标
int _QuickSort(int* arr, int left, int right)
{//错误点1：key应该等于left，指向的是排序数组中的第一个数据，而不是整个数组中的第一个数据int key = left;//错误点2：left指向的位置应该是key位置之后的数据，而不是指向key这个位置++left;

8.1.4错误点3

这是一个注意点，因为错误率很高：

//快速排序
//寻找基值的函数，返回基值的下标
int _QuickSort(int* arr, int left, int right)
{//错误点1：key应该等于left，指向的是排序数组中的第一个数据，而不是整个数组中的第一个数据int key = left;//错误点2：left指向的位置应该是key位置之后的数据，而不是指向key这个位置++left;//注意点3：当left=right时，仍然要进入循环while (left <= right)

8.1.5错误点4

while (left <= right)
{//错误点4：假设待排序数组中的所有数据都比基值数据大，left会一直向后++，会发生越界情况，所以这边的判断需要加上一个条件//找出比基值大的数据while (left<=right && arr[left] < arr[key]){//当找到的数据比基值小时，往后找，直到找到比基值大的数据left++;}//错误点4：和上边的错误点4一样//找出比基值小的数据while(left<=right && arr[right] > arr[key]){//当找到的数据比基值大时，往前找，直到找到比基值小的数据right--;}

8.1.6错误点5

这也是一个注意点

//错误点4：假设待排序数组中的所有数据都比基值数据大，left会一直向后++，会发生越界情况，所以这边的判断需要加上一个条件
//找出比基值大的数据
//注意点5：假设所有数据都为6，如果这里的判断条件为arr[left] <= arr[key]的话，left会一直向后++，right一直向前--，
//        导致基值不变，造成死循环，所以这边的判断条件不能为=
while(left<=right && arr[left] < arr[key])
{//当找到的数据比基值小时，往后找，直到找到比基值大的数据left++;
}
//错误点4：和上边的错误点4一样
//找出比基值小的数据
//注意点5：和上边注意点5相同
while(left<=right && arr[right] > arr[key])
{//当找到的数据比基值大时，往前找，直到找到比基值小的数据right--;
}

8.1.7错误点6

在交换时要加上前置条件，否则会出现下面的情况：

//错误点6：交换时要加上前置条件
if(left<=right)
{//然后将大小数据进行交换Swap(&arr[left], &arr[right]);
}

8.1.8错误点7

//错误点6：交换时要加上前置条件
if(left<=right)
{//然后将大小数据进行交换//错误点7：交换完之后要注意改变left和right，在思路图中想到了，但是没有实现在代码上Swap(&arr[left++], &arr[right--]);
}

8.2Hoare版本快排最终代码

//快速排序
//寻找基值的函数，返回基值的下标
int _QuickSort(int* arr, int left, int right)
{//错误点1：key应该等于left，指向的是排序数组中的第一个数据，而不是整个数组中的第一个数据int key = left;//错误点2：left指向的位置应该是key位置之后的数据，而不是指向key这个位置++left;//注意点3：当left=right时，仍然要进入循环while (left <= right){//错误点4：假设待排序数组中的所有数据都比基值数据大，left会一直向后++，会发生越界情况，所以这边的判断需要加上一个条件//找出比基值大的数据//注意点5：假设所有数据都为6，如果这里的判断条件为arr[left] <= arr[key]的话，left会一直向后++，right一直向前--，//        导致基值不变，造成死循环，所以这边的判断条件不能为=while (left<=right && arr[left] < arr[key]){//当找到的数据比基值小时，往后找，直到找到比基值大的数据left++;}//错误点4：和上边的错误点4一样//找出比基值小的数据//注意点5：和上边注意点2相同while (left<=right && arr[right] > arr[key]){//当找到的数据比基值大时，往前找，直到找到比基值小的数据right--;}//错误点6：交换时要加上前置条件if(left<=right){//然后将大小数据进行交换//错误点7：交换完之后要注意改变left和right，在思路图中想到了，但是没有实现在代码上Swap(&arr[left++], &arr[right--]);}}//最后将基值赋值到right，right就成为了基值下标Swap(&arr[key], &arr[right]);return right;
}//与其他排序方法不同，这里应该传入数组、排序区域的左区间、排序区域的右区间
void QuickSort(int* arr, int left, int right)
{//递归结束条件//当left和right重合时，表示此时只有一个结点，退出递归if (left >= right){return;}//寻找基值int key = _QuickSort(arr, left, right);//递归寻找基值QuickSort(arr, left, key-1);QuickSort(arr, key + 1, right);
}

8.3快速排序空间复杂度分析

函数递归每调用一次就会创建一次函数栈帧，每次return循环结束之后就会销毁函数栈帧，而快排在调用时的作用如图：

每一次递归就会将原数组分为两半，所以求空间复杂度，就是求这个二叉树的深度，也就是log2N，所以快速排序的空间复杂度为log2N

8.4快速排序时间复杂度分析

8.4.1最优情况（平均情况）

对于一个具有n个数据的数组来说，每一层需要交换的数据为n个，而深度为longN，所以总的排序工作量为NlogN，时间复杂度也就是O(NlogN)

8.4.2最坏情况

如果每次分区都极度不均衡，也就是每次基值都是数组中最大的数据或最小的数据，此时快速排序的时间复杂度就退化为O(n^2)

8.5观察快速排序的排序时间

快速排序在排序中是最快的，所以我们一定会很期待快排的发挥：

可以看出，在十万个数据中，快排只需要4ms，这次我们增大数据量，将数据增加到100万：

对于100万个数据，快速排序只用了39ms，相当快速，这时希尔排序只是个意外【笑哭】

9.快速排序–挖坑法

挖坑法为查找基值提供了一个新的思路，我们来看：

代码实现：

int _QuickSort(int* arr, int left, int right)
{//先在第一个值的位置挖坑int hole = left;//将第一个坑中的值保存下来int key = arr[left];while (left < right){//先让right向前走//错误点1：此时要加上=，当数组中的数据全为6时，如果不加等号的话right的值不会改变，程序会死循环while (left < right && arr[right] >= key){right--;}//填坑挖新坑arr[hole] = arr[right];hole = right;//再让left向后走//错误点1：看上边错误点1while (left < right && arr[left] <= key){left++;}arr[hole] = arr[left];hole = left;}arr[hole] = key;return hole;
}//与其他排序方法不同，这里应该传入数组、排序区域的左区间、排序区域的右区间
void QuickSort(int* arr, int left, int right)
{//递归结束条件//当left和right重合时，表示此时只有一个结点，退出递归if (left >= right){return;}//寻找基值int key = _QuickSort(arr, left, right);//递归寻找基值QuickSort(arr, left, key-1);QuickSort(arr, key + 1, right);
}

10.快速排序–lomuto前后指针

代码实现：

//Lomuto法
int _QuickSort(int* arr, int left, int right)
{int key = left;int prev = left;int pcur = left +1;while (pcur < right){if (arr[pcur] < arr[key] && ++prev!=pcur){Swap(&arr[pcur], &arr[prev]);}pcur++;}Swap(&arr[key], &arr[prev]);return prev;
}//与其他排序方法不同，这里应该传入数组、排序区域的左区间、排序区域的右区间
void QuickSort(int* arr, int left, int right)
{//递归结束条件//当left和right重合时，表示此时只有一个结点，退出递归if (left >= right){return;}//寻找基值int key = _QuickSort(arr, left, right);//递归寻找基值QuickSort(arr, left, key-1);QuickSort(arr, key + 1, right);
}

11.快速排序–非递归版本

上面我们实现的快速排序都是在递归的基础上实现的，下面我们接触一个新的非递归实现快排的方法：

代码实现：

//快速排序--非递归版本
void QuickSortNoneD(int* arr, int left, int right)
{Stack s;Init(&s);//先将右值和左值入栈StackPush(&s, right);StackPush(&s, left);//当栈为空时，结束循环while (s.top != 0){//先从栈中取左值和右值left = StackPrint(&s);StackPop(&s);right = StackPrint(&s);StackPop(&s);//然后在左值--右值这一块空间中寻找基值--lomuto指针法int keyi = left;int prev = left;int pcur = left +1;while (pcur <= right){if (arr[pcur] < arr[keyi] && ++prev != pcur){Swap(&arr[pcur], &arr[prev]);}pcur++;}Swap(&arr[keyi], &arr[prev]);//此时基值为prev//然后再次入栈，先让右数组入栈，再让左数组入栈//1.当只有一个数据时不用入栈//2.当数组的指向越界时不用入栈//左数组：[left, prev-1]//右数组：[prev+1, right]if (prev + 1 < right){StackPush(&s, right);StackPush(&s, prev + 1);}if (left < prev - 1){StackPush(&s, prev - 1);StackPush(&s, left);}}Destory(&s);
}

此时再使用100万个数据进行检测：

快速排序依旧很强势！！！

12.归并排序

其实就是先递归，然后排序

代码实现：

//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{//递归结束条件：left>=rightif (left >= right){return;}int mid = (left + right) / 2;_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right, tmp);//递归完成，开始向上排序int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;//对数组进行排序，谁小谁插入到新的数组中//错位点1：这里的i应该指向left，不能指向0int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}//退出循环只有两种可能：//1.begin1的数组为空//错误点2：这里应该为while，不能是ifwhile (begin2 <= end2){tmp[index++] = arr[begin2++];}//2.begin2的数组为空while (begin1 <= end1){tmp[index++] = arr[begin1++];}//最后要将tmp中的数据赋值到arr数组中//错误点3：这里j应该初始化为left，不能为0for (int i = left; i <= right; i++){arr[i] = tmp[i];}
}void MergeSort(int* arr, int n)
{//开辟新的数组空间来存储排序好的数据int* tmp = (int*)malloc(sizeof(int) * n);//递归进行排序_MergeSort(arr, 0, n - 1, tmp);free(tmp);
}

对100万数据进行排序的结果：

毋庸置疑是一个非常好用的排序方法！！！

12.1归并排序时间复杂度分析

对于归并排序，假设有N个数据，那么递归的深度为logN，而每一层递归都是要将这一层的数据进行排序，所以它的时间复杂度为NlogN

12.2归并排序空间复杂度分析

归并排序使用过程中开辟了一个数组的空间，所以它的空间复杂度为O(N)

13.非比较排序–计数排序

之前所使用的所有排序算法都是通过数据之间的比较，从而将大数和小数区分出来的，现在我们要掌握一种不需要比较就能够进行排序的算法

代码实现：

//非比较排序
void CountSort(int* arr, int n)
{//先确定数组中的最大值和最小值int max = arr[0];int min = arr[0];for (int i = 0; i < n; i++){if (arr[i] > max){max = arr[i];}if (arr[i] < min){min = arr[i];}}//然后通过最大值和最小值来开辟空间int capacity = max - min + 1;int* tmp = (int*)malloc(capacity * sizeof(int));//将开辟的空间初始化为0memset(tmp, 0, capacity * sizeof(int));//将原数组中每个数据出现的次数存储到开辟数组中for (int i = 0; i < n; i++){tmp[arr[i] - min]++;}//通过开辟数组记录的数据实现排序int index = 0;for (int i = 0; i < capacity; i++){while (tmp[i]--){arr[index++] = i + min;}}
}

然后我们让这个排序算法来排100万个数据：

仅仅用了1ms！！！但是这个算法有致命的缺点：
1.无法对小数进行排序
2.对于整数的排序在特殊情况下空间浪费多

13.1非比较函数时间复杂度分析

//非比较排序--时间复杂度分析--O(N)
void CountSort(int* arr, int n)
{int max = arr[0];int min = arr[0];//O(N)for (int i = 0; i < n; i++){if (arr[i] > max){max = arr[i];}if (arr[i] < min){min = arr[i];}}int capacity = max - min + 1;int* tmp = (int*)malloc(capacity * sizeof(int));memset(tmp, 0, capacity * sizeof(int));//O(N)for (int i = 0; i < n; i++){tmp[arr[i] - min]++;}//此处虽然是两层循环，但是作用是遍历开辟数组，对arr数组进行赋值//所以此处的时间复杂度还是O(N)int index = 0;for (int i = 0; i < capacity; i++){while (tmp[i]--){arr[index++] = i + min;}}
}

14.排序算法复杂度以及稳定性分析

总结：

分析：

到这里，所有排序已经讲完，之后将要学习C++的内容，也是成功地脱离新手村了，希望自己能够坚持下来！！！