前言
排序算法是计算机科学领域的基石之一，它不仅在算法的理论研究中占据重要地位，更是实际开发当中解决数据组织，检索，处理等问题的关键工具。现如今数据日益增长，理解并掌握这些排序算法的原理、特点及其适用场景，对于提升程序效率、优化用户体验至关重要。
八大排序算是排序算法当中知名度较高的了，它们不仅涵盖了简单直观的排序方法，以便初学者学习理解；也包含了高效复杂的排序策略，广泛应用于实际开发。
本篇文章，作者主要介绍并实现八大排序算法的其中四种：冒泡排序、选择排序、插入排序、希尔排序。
正文开始
写一串测试数据
首先，我们写一个乱序的数组，便于后续排序测试：
int main() { int arr[] = { 5,9,4,0,2,7,8,0,0,1,4,4,1,3,5,6,3,2,9,7 }; int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数 for (int i = 0; i < sz; i++)//打印数组 { printf("%d ", arr[i]); } return 0; }
交换两元素的函数
在这里，我们将交换两个元素的步骤封装成一个函数，便于后续多次调用。
void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; }
一、冒泡排序
冒泡排序是一种简单的排序算法，易于初学者理解和学习。它的核心思想就是重复遍历数组，比较相邻两个元素，如果它们的顺序错误，则交换之。直到数组中没有顺序错误的情况，则排序已经完成。
它的具体步骤描述如下：
1.遍历数组，比较所有的相邻元素，如果前者大于后者（默认升序），则交换它们。
2.当遍历到数组最后一对相邻元素后，数组中最后一个元素会是最大的数。此时一趟冒泡排序完成。
3.重新遍历数组比较相邻元素（最后一个元素除外，因为已经是最大的了）。一趟结束后，数组中第二大的元素将位于倒数第二个位置。
4.重复进行上述步骤（已经就位的元素除外），直到所有元素均不需要再交换。
动图表示：
接下来，我们尝试实现冒泡排序：
void BubbleSort(int* arr, int n) { //外层循环控制排序的趟数 for (int i = 0; i < n - 1; i++)//每一趟排序使一个元素就位，n个元素的数组需要n-1趟排序（最后一趟会使前两个元素就位） { //内层循环控制需要比较的相邻元素 for (int j = 0; j < n - 1 - i; j++)//每一趟结束后，需要比较的元素便减少一个，所以要减去i { if (arr[j] > arr[j + 1])//若前者大于后者，说明顺序错误，需要交换 { Swap(&arr[j], &arr[j + 1]);//交换两元素 } } } }
不难发现，如果没有到达排序的趟数，但是数组已经有序，程序就会继续进行不必要的元素比较，运行效率降低。基于这一点，我们可以做出如下改进：
void BubbleSort(int* arr, int n) { //外层循环控制排序的趟数 for (int i = 0; i < n - 1; i++)//每一趟排序使一个元素就位，n个元素的数组需要n-1趟排序（最后一趟会使前两个元素就位） { int flag = 1;//假设数组已经有序 //内层循环控制需要比较的相邻元素 for (int j = 0; j < n - 1 - i; j++)//每一趟结束后，需要比较的元素便减少一个，所以要减去i { if (arr[j] > arr[j + 1])//若前者大于后者，说明顺序错误，需要交换 { Swap(&arr[j], &arr[j + 1]);//交换两元素 flag = 0;//发生了交换，说明数组并非有序 } } if (flag == 1)//如果数组已经有序，则不需要排序，直接退出循环 { break; } } }
接下来，我们对测试数组进行排序：
int main() { int arr[] = { 5,9,4,0,2,7,8,0,0,1,4,4,1,3,5,6,3,2,9,7 }; int sz = sizeof(arr) / sizeof(arr[0]); BubbleSort(arr, sz);//冒泡排序 for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; }
运行结果：
可以看到，排序成功了。
冒泡排序的特性总结
空间复杂度：O(1)
时间复杂度：O(N^2)
稳定性（相同值的元素排序前后的相对次序是否保持不变）：稳定
无论数组是否有序，都有大量元素被重复地进行比较和交换，运行效率不高
二、选择排序
选择排序是一种比较接近人类思想的排序算法，它的核心思想非常简单：从数组中寻找最小（最大）元素，将其放于数组第一个位置（最后一个位置）处，然后再从剩余的元素中寻找最小（最大）值，放到数组第二个位置（倒数第二个位置）处......
具体步骤如下：
1.首先遍历数组，寻找到数组中最小的元素，将其与数组的首元素进行交换。
2.开始遍历数组的剩下部分，寻找最小值，与该部分的首元素进行交换。
3.重复第二步，直到“该部分”只有一个元素为止，说明数组已经排序好。
动图表示：
接下来，我们尝试代码实现选择排序：
void SelectSort(int* arr, int n) { //外层循环控制遍历次数以及遍历的起始位置 for (int i = 0; i < n; i++) { int mini = i;//假设最小值位于遍历部分的首元素处 //内层循环，寻找最小值 for (int j = mini + 1; j < n; j++) { if (arr[j] < arr[mini])//将更小的元素标记为mini { mini = j; } } Swap(&arr[i], &arr[mini]);//将最小值与遍历部分的首元素交换 } }
运行测试：
选择排序特性总结
空间复杂度：O(1)
时间复杂度：O(N^2)
稳定性：不稳定
使用寻找最值进行交换的方式，虽然在效率上相比冒泡排序有所提升，但是依然不是很实用。
三、插入排序
插入排序是一种适用于对少量数据进行排序的算法，它的效率要略高于冒泡排序和选择排序。就像玩扑克牌一样，它的核心思想是：将一个个数据不断插入到已经有序的数组的合适位置，从而使整个数组有序。
具体步骤如下：
1.将数组首元素视为有序。
2.将有序数组的下一个元素取出，然后开始对该元素之前的部分进行遍历，找到合适位置并插入。
3.将这部分有序数组看成整体，重复第二步，直到将最后一个元素调整完成。
动图表示：
代码实现如下：
void InsertSort(int* arr, int n) { //外层循环确定遍历次数 for (int i = 0; i < n - 1; i++) { int end = i;//记录有序数组的末尾位置 int tmp = arr[end + 1];//保存需要插入的元素tmp //内层循环控制对有序数组的遍历 while (end >= 0)//当end小于0时，一次遍历结束 { if (arr[end] > tmp) { arr[end + 1] = arr[end];//该值后移一位，留空缺 end--;//继续向前走 } else//当tmp值比有序数组中某元素小或相等时，说明tmp应该插入在该元素之后，终止遍历 { break; } } arr[end + 1] = tmp;//插入到该元素之后的位置 } }
代入测试：
插入排序性能总结
空间复杂度：O(1)
时间复杂度：O(N^2)
稳定性：稳定
虽然在时间复杂度上没有什么变化，但是相比冒泡排序和选择排序，性能有所提升。由于它是按照顺序进行扫描并且插入的，所以相同值元素的相对位置不会改变，是一种稳定的排序算法，是排序少量数据的首选。不过面对的数据量庞大时，依然不够看。
四、希尔排序
希尔排序又称为缩小增量排序，是一种效率很高的排序算法，算是插入排序的升级版。它的核心思想也比较简单：首先对数组进行预排序，使其接近有序，然后进行插入排序。
这里介绍一下排序的思路：
首先选定一个增量gap(这里我们使gap=数组元素n/3)，将数组中相差gap个位置的元素视为一个子序列，然后分别对这些子序列进行插入排序。当所有子序列排序结束之后，使gap的值逐渐减小（再除以3），然后再将相差gap个位置的元素构成的子序列进行插入排序......直到gap为1时，构成的序列就是数组本身，对其进行一次插入排序即可。
当然，这里的增量gap并不是只有n/3这一种取法。他还有很多种取法，例如n/2、n/4等。但要注意：变化的gap值应尽量满足没有除1以外的公因子，并且最后一次gap的值是1。
接下来，我们尝试实现希尔排序：
void ShellSort(int* arr, int n) { int gap = n;//定义增量gap //循环控制预排序的次数，以及进行最后一次插入排序 while (gap > 1) { gap = gap / 3 + 1;//首先调整gap值 //进行插入排序 //注意细节处理，是对相隔gap的元素进行排序 for (int i = 0; i < n - gap; i++)//一次循环结束后，i++就走向了下一个子序列的起始位置 { int end = i;//记录有序部分的末尾位置 int tmp = arr[end + gap];//end+gap位置的元素视为子序列中的下一个元素 while (end >= 0) { if (arr[end] > tmp) { arr[end + gap] = arr[end]; end -= gap;//一次向前走gap个位置 } else { break; } } arr[end + gap] = tmp; } } }
从代码角度看，它相比插入排序又多了一层循环，效率怎么会高于插入排序呢？实际上，有了预排序之后，最后一次插入排序所节省的时间要远远大于预排序消耗的时间。
代入数据测试：
希尔排序性能总结
空间复杂度：O(1)
时间复杂度：O(N^1.3)(计算过程相对复杂)
稳定性：不稳定
相比冒泡排序，选择排序和插入排序，希尔排序的时间复杂度较低，运行效率更高，更适用于大规模数据的排序。但是它的性能不稳定，易受数据和增量选择的影响。
程序全部代码
程序全部代码如下：
//交换函数 void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } //冒泡排序 void BubbleSort(int* arr, int n) { //外层循环控制排序的趟数 for (int i = 0; i < n - 1; i++)//每一趟排序使一个元素就位，n个元素的数组需要n-1趟排序（最后一趟会使前两个元素就位） { int flag = 1;//假设数组已经有序 //内层循环控制需要比较的相邻元素 for (int j = 0; j < n - 1 - i; j++)//每一趟结束后，需要比较的元素便减少一个，所以要减去i { if (arr[j] > arr[j + 1])//若前者大于后者，说明顺序错误，需要交换 { Swap(&arr[j], &arr[j + 1]);//交换两元素 flag = 0;//发生了交换，说明数组并非有序 } } if (flag == 1)//如果数组已经有序，则不需要排序，直接退出循环 { break; } } } //选择排序 void SelectSort(int* arr, int n) { //外层循环控制遍历次数以及遍历的起始位置 for (int i = 0; i < n; i++) { int mini = i;//假设最小值位于遍历部分的首元素处 //内层循环，寻找最小值 for (int j = mini + 1; j < n; j++) { if (arr[j] < arr[mini])//将更小的元素标记为mini { mini = j; } } Swap(&arr[i], &arr[mini]);//将最小值与遍历部分的首元素交换 } } //插入排序 void InsertSort(int* arr, int n) { //外层循环确定遍历次数 for (int i = 0; i < n - 1; i++) { int end = i;//记录有序数组的末尾位置 int tmp = arr[end + 1];//保存需要插入的元素tmp //内层循环控制对有序数组的遍历 while (end >= 0)//当end小于0时，一次遍历结束 { if (arr[end] > tmp) { arr[end + 1] = arr[end];//该值后移一位，留空缺 end--;//继续向前走 } else//当tmp值比有序数组中某元素小或相等时，说明tmp应该插入在该元素之后，终止遍历 { break; } } arr[end + 1] = tmp;//插入到该元素之后的位置 } } //希尔排序 void ShellSort(int* arr, int n) { int gap = n;//定义增量gap //循环控制预排序的次数，以及进行最后一次插入排序 while (gap > 1) { gap = gap / 3 + 1;//首先调整gap值 //进行插入排序 //注意细节处理，是对相隔gap的元素进行排序 for (int i = 0; i < n - gap; i++)//一次循环结束后，i++就走向了下一个子序列的起始位置 { int end = i;//记录有序部分的末尾位置 int tmp = arr[end + gap];//end+gap位置的元素视为子序列中的下一个元素 while (end >= 0) { if (arr[end] > tmp) { arr[end + gap] = arr[end]; end -= gap;//一次向前走gap个位置 } else { break; } } arr[end + gap] = tmp; } } } int main() { int arr[] = { 5,9,4,0,2,7,8,0,0,1,4,4,1,3,5,6,3,2,9,7 }; int sz = sizeof(arr) / sizeof(arr[0]); //BubbleSort(arr, sz); //SelectSort(arr, sz); //InsertSort(arr, sz); ShellSort(arr, sz); for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; }
总结
今天，我们学习了八大排序的其中四种：冒泡排序，选择排序，插入排序和希尔排序。在理解这些排序思想和实现它们的过程当中，我们感受到了算法之美，也加强了分析问题、解决问题的能力。之后博主会和大家分享剩下的几种排序算法。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤
