【本关目标】

1. 排序的概念
2. 常见排序的算法思想和实现
3. 排序算法的复杂度以及稳定性分析

目录

【本关目标】

1.排序的概念

2.常见排序的算法思想和实现（代码默认都是从小到大排序）

2.1插入排序

1）直接插入排序

 2）希尔排序

2.2选择排序

1）直接选择排序

2）堆排序

2.3交换排序

1）冒泡排序

2）快速排序

3.以上几种函数的性能对比：

4.源代码（VS2022下编写）

1.排序的概念

• 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
• 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
• 内部排序：数据元素全部放在内存中的排序。
• 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

 常见的排序算法：

各种排序算法的接口：

//直接插入排序
void InsertSort(int* a, int n);//希尔排序
void ShellSort(int* a, int n);//排序的性能测试对比
void functionText()
{//设定随机数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);for (int i = 0; i < N; ++i){a1[i] = rand() + i;//因为rand()得到的数据只有3万左右，剩下的就都是重复的了//所以这里用rand() + i使得其重复数尽量的减小a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];}// clock()是计算运行到此时cpu执行的时间，单位毫秒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();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);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);
}

2.常见排序的算法思想和实现（代码默认都是从小到大排序）

2.1插入排序

1）直接插入排序

基本思想：

直接插入排序是一种简单的排序算法
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

性能总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

代码实现：

void InsertSort(int* a, int n)
{//两层循环    第一层是用来确顶当前该比较哪个位置的数，用tmp来记录//		     第二层是用来进行从end到0方向的下标位置比较，//                  用tmp与之前的所有位置的数进行比较for (int i = 0; i < n - 1; ++i){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp > a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}

 2）希尔排序

基本思想： 

希尔排序法又称缩小增量法。

先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

 希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定
   希尔排序的时间复杂度和堆排序的复杂度差不多，但在数据越大的情况下希尔排序更好
4. 稳定性：不稳定

代码实现：

void ShellSort(int* a, int n)
{// 三层循环，第一层：对gap的递减，达成预排序//			 第二层和第三层的方法就和直接插入排序一样了// // gap > 1 预排序// gap == 1 直接插入排序int gap = n;while (gap > 1){gap = gap / 2;for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}//精简代码版：
void shellSort(int* arr, int n) 
{int gap, i, j, tmp;for (gap = n / 2; gap > 0; gap /= 2) {for (i = gap; i < n; i++) {tmp = arr[i];for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = tmp;}}
}

2.2选择排序

1）直接选择排序

基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

也可以一次循环直接将最小和最大都选出来（如下面代码中那样）

步骤：

• 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
• 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个
  （第一个）元素交换
• 在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

直接选择排序在任何情况都是O(N^2)  包括有序或接近有序，

所以它的排序效率还没有直接插入排序的效率高

代码实现：

void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);// 这里是防止maxi和begin相等时，由于换位而导致maxi的交换发生错误if (maxi == begin){	maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

2）堆排序

基本思想：

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

具体可看博主之前的文章：

数据结构_第十关：二叉树的顺序结构——堆_小羊在摸鱼的博客-CSDN博客

堆排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

代码如下：

//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//像下调整(建大堆)（数组、数组大小、父节点下标）
void AdjustDown(int* a, int n, int parent)
{//默认认为左孩子大int child = parent * 2 + 1;//超过数组大小while (child < n){//确认child指向大的孩子if (child + 1 < n && a[child + 1] > a[child]) //第一处：a[child + 1] > a[child]{++child;}//孩子大于父亲，交换,继续调整//这里换为 > 是大堆的创建if (a[child] > a[parent])  //第二处：a[child] > a[parent]{swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}//将第一处和第二处的>换为<则是建小堆
}
//堆排序
void HeapSort(int* a, int size)
{// 向下调整建堆 -- O(N)// 升序：建大堆for (int i = (size - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, size, i);}int end = size - 1;//(end表示数组需要与array[0]交换的下标位置)while (end > 0){Swap(&a[0], &a[end]);//交换array[0]和array[end]的位置AdjustDown(a, end, 0);//向下调整end--;}
}

2.3交换排序

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，

交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

1）冒泡排序

基本思想

用当前的和前一个进行比较，将值大的往后移动，值小的往前移动。

冒泡排序也时最简单，最常学习的排序，缺点就是排序效率比较差

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2) 
3. 空间复杂度：O(1)
4. 稳定性：稳定

代码如下：

void BubbleSort(int* a, int n)
{for (int j = 0;j < n;j++){for (int i = 1;i < n - j;i++){if (a[i-1] > a[i]){int tmp = a[i - 1];a[i - 1] = a[i];a[i] = tmp;}}}
}

2）快速排序

由于内容较多，放到了下一章分开来学习

数据结构_第十三关（2）：快速排序_小羊在摸鱼的博客-CSDN博客

3.以上几种函数的性能对比：

以下对比都是在Debug版本下的对比，如果是在Release 版本下，其所需时间会更短

数据量为1万时，各排序所需时间： 

 数据量为10万时，各排序所需时间： 

 数据量为100万时，各排序所需时间（去掉两个最慢的，选择和冒泡）： 

数据量为1000万时，各排序所需时间（去掉两个最慢的，选择和冒泡）： 

 结论：

• 可以看到，冒泡排序是最拉的排序算法，虽然其思想很简单
• 最排序和希尔排序的效率差不多

4.源代码（VS2022下编写）

#include<stdlib.h>
#include<time.h>//直接插入排序
void InsertSort(int* a, int n);//希尔排序
void ShellSort(int* a, int n);
void shellSort(int* arr, int n);//选择排序
void SelectSort(int* a, int n);//堆排序
void HeapSort(int* a, int n);//冒泡排序
void BubbleSort(int* a, int n);//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//像下调整（数组、数组大小、父节点下标）
void AdjustDown(int* a, int n, int parent)
{//默认认为左孩子大int child = parent * 2 + 1;//超过数组大小while (child < n){//确认child指向大的孩子if (child + 1 < n && a[child + 1] > a[child]) //第一处：a[child + 1] > a[child]{++child;}//孩子大于父亲，交换,继续调整//这里换为 > 是大堆的创建if (a[child] > a[parent])  //第二处：a[child] > a[parent]{Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}//将第一处和第二处的>换为<则是建小堆
}//直接插入排序
void InsertSort(int* a, int n)
{//两层循环，第一层是用来确顶当前该比较哪个位置的数，用tmp来记录//			第二层是用来进行从end到0方向的下标位置比较，用tmp与之前的所有位置的数进行比较for (int i = 0; i < n - 1; ++i){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}//希尔排序
void ShellSort(int* a, int n)
{// 三层循环，第一层：对gap的递减，达成预排序//			 第二层和第三层的方法就和直接插入排序一样了// // gap > 1 预排序// gap == 1 直接插入排序int gap = n;while (gap > 1){gap = gap / 2;  // +1是为了保证最后一次gap一定为1// 如果是gap /= 2，则最后一次肯定是1，除2就不用+1了for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}
//代码简化版
void shellSort(int* arr, int n) 
{//步长从大到小逐渐缩小，直到步长为1，也就是最后一次对整个数组进行插入排序。//在最开始的时候，步长通常为数组长度的一半，可以尽快达到比较均匀的排序效果，之后每次都把步长折半// int gap, i, j, tmp;for (gap = n / 2; gap > 0; gap /= 2) {for (i = gap; i < n; i++) {tmp = arr[i];for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = tmp;}}
}//选择排序
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);if (maxi == begin)maxi = mini;Swap(&a[end], &a[maxi]);++begin;--end;}
}//堆排序
void HeapSort(int* a, int size)
{//排升序，建大堆for (int i = (size - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, size, i);}int end = size - 1;//(end表示数组需要与array[0]交换的下标位置)while (end > 0){Swap(&a[0], &a[end]);//交换array[0]和array[end]的位置AdjustDown(a, end, 0);//向下调整end--;}
}//冒泡排序
void BubbleSort(int* a, int n)
{for (int j = 0;j < n;j++){for (int i = 1;i < n - j;i++){if (a[i-1] > a[i]){int tmp = a[i - 1];a[i - 1] = a[i];a[i] = tmp;}}}
}void printArray(int* a, int n)
{for (int i = 0;i < n;i++){printf("%d ", a[i]);}printf("\\n");
}
void TestInsertSort()
{int a[] = { 9, 1, 2, 5, 7, 4, 8, 6};InsertSort(a, sizeof(a) / sizeof(int));printArray(a, sizeof(a) / sizeof(int));shellSort(a, sizeof(a) / sizeof(int));printArray(a, sizeof(a) / sizeof(int));HeapSort(a, sizeof(a) / sizeof(int));printArray(a, sizeof(a) / sizeof(int));BubbleSort(a, sizeof(a) / sizeof(int));printArray(a, sizeof(a) / sizeof(int));
}
void functionText()
{srand(time(0));const int N = 1000000;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() + i;a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a7[i];}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 begin7 = clock();BubbleSort(a7, N);int end7 = clock();//int begin5 = clock();//QuickSort(a5, 0, N - 1);//int end5 = clock();// //int begin6 = clock();//MergeSort(a6, N);//int end6 = clock();printf("数据量为%d，以下时间单位为毫秒（ms）\\n",N);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("BubbleSort:	%d\\n", end7 - begin7);//printf("QuickSort:%d\\n", end5 - begin5);//printf("MergeSort:%d\\n", end6 - begin6);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}int main()
{TestInsertSort();//性能测试：functionText();return 0;
}