C语言实现-排序1

🎯引言

欢迎来到HanLop博客的C语言数据结构初阶系列。在本篇文章中，我们将探讨一种基础而又极为重要的算法——排序（Sorting）。排序算法在计算机科学中占据着举足轻重的地位，它们被广泛应用于各种场景，如数据检索、数据库管理、图像处理等。通过排序，我们可以将数据按照一定的顺序进行组织和管理，从而提高程序的效率和可读性。在本文中，我们将介绍几种经典的排序算法，包括冒泡排序、直接选择排序、堆排序、直接插入排序、希尔排序、快速排序和归并排序，并通过代码示例，展示如何在C语言中实现这些算法。无论您是初学者还是有经验的程序员，这篇文章都将帮助您理解排序算法的基本原理及其在实际编程中的应用。

👓排序

1.排序的概念以及运用

1.1概念

排序是指将一组无序的数据按照特定的规则重新排列，使其形成有序序列的过程。排序的目标是通过一定的比较和交换规则，将数据按升序或降序排列，便于后续的查找、插入、删除等操作。

1.2运用

排序算法的应用场景非常广泛，即使在日常生活中也能找到许多例子。以下是一些普通人也能轻松理解的例子：

1. 书籍整理： 当你将家中的书籍按字母顺序排列时，你实际上是在对书籍进行排序。这使得你可以更快速地找到某本书，因为你知道每本书在书架上的大致位置。
2. 考试成绩排名： 在学校中，老师通常会将学生的考试成绩从高到低排列，生成一个成绩单。这是一个典型的排序应用，通过这个排序，可以轻松确定每个学生的排名。

1.3常见的排序算法

本次博客只讲解插入和选择排序

2.排序算法的实现

2.1插入排序

2.1.1直接插入排序

直接插入排序是一种简单的排序算法，适用于小规模的数据集。它的基本思想是通过逐步将元素插入到已排序的部分，逐渐形成有序的序列。以下是对你提供的直接插入排序函数的详细解析：

//代码实现
void InsertSort(int* arr, int n)
{int i = 0;// 外层循环：逐步将每个元素插入到已排序部分for (i = 0; i < n - 1; i++){int end = i;            // end 指向已排序部分的最后一个元素int num = arr[end + 1]; // 记录当前要插入的元素// 内层循环：将当前元素插入到已排序部分的适当位置while (end >= 0){// 如果已排序部分的元素大于当前元素，将其向后移动if (arr[end] > num){arr[end + 1] = arr[end];end--;}else{break; // 一旦找到比当前元素小的位置，跳出循环}}// 将当前元素插入到合适的位置arr[end + 1] = num;}
}

解析：

1. 函数定义：
   • void InsertSort(int* arr, int n)：该函数接受一个整数数组 arr 以及数组的长度 n，并对数组进行直接插入排序。
2. 外层循环 (for (i = 0; i < n - 1; i++))：
   • 这个循环从第一个元素开始，逐步将每个元素插入到已排序部分。注意，i从0开始，遍历到 n-2（即第 n-1 个元素），因为在 i 为 n-1 时，整个数组就已经排序完成。
3. 已排序部分的最后一个元素 (int end = i)：
   • end 指向当前已排序部分的最后一个元素位置。它表示我们需要将当前 arr[i+1] 插入到从 arr[0] 到 arr[i] 的已排序部分。
4. 待插入的元素 (int num = arr[end + 1])：
   • num 存储当前需要插入到已排序部分的元素值，即 arr[i+1]。
5. 内层循环 (while (end >= 0))：
   • 这个循环用于找到 num 在已排序部分中的正确位置。每次比较 num 与已排序部分中的元素 arr[end]，如果 arr[end] 比 num 大，那么我们需要将 arr[end] 向后移动，以便为 num 腾出空间。
   • 条件判断 (if (arr[end] > num))：
     • 如果 arr[end] 比 num 大，说明 num 还没有找到合适的位置，arr[end] 向后移动 (arr[end + 1] = arr[end])，并继续向前比较 (end--)。
   • 循环终止条件 (else { break; })：
     • 一旦找到 arr[end] <= num 的情况，说明 num 应该插入到 arr[end] 后面的位置，循环终止。
6. 插入元素 (arr[end + 1] = num)：
   • 最后，将 num 插入到正确的位置 arr[end + 1]。到此，已排序部分的长度增加1，即包含从 arr[0] 到 arr[i+1] 的元素。

时间复杂度分析

直接插入排序的时间复杂度主要取决于数组中元素的初始排列情况。我们可以从以下几种情况进行分析：

1. 最佳情况（已排序数组）：
   • 如果数组已经是有序的，那么在每次插入时，内层循环 while (end >= 0) 不会执行（因为 arr[end] <= num），只需进行一次比较。因此，每次插入操作的时间复杂度是O(1)，整个数组的排序时间复杂度为O(n)。
2. 最坏情况（逆序数组）：
   • 如果数组是逆序排列的，那么在每次插入时，内层循环需要比较并移动所有已排序的元素。例如，当插入第 i+1 个元素时，需要进行 i+1 次比较和 i+1 次移动。因此，最坏情况下的时间复杂度为O(n^2)。
3. 平均情况：
   • 在随机排列的数组中，插入第 i+1 个元素时，内层循环需要大约 i/2 次比较和移动。因此，平均情况下的时间复杂度为O(n^2)。

时间复杂度总结：

• 最佳情况：O(n)
• 最坏情况：O(n^2)
• 平均情况：O(n^2)

空间复杂度分析

直接插入排序是一种原地排序算法，它只需要常数级别的额外空间来存储临时变量 num。无论数组的大小如何，所需的额外空间都不变，因此空间复杂度为O(1)。

空间复杂度总结：

• 空间复杂度：O(1)

结论

直接插入排序的时间复杂度在最坏和平均情况下都是O(n^2)，但在最佳情况下是O(n)。空间复杂度为O(1)，意味着它不需要额外的存储空间。这使得直接插入排序适用于小规模的数据集或近乎有序的数组，但在大规模或完全无序的数据集上表现较差。

2.1.2希尔排序

希尔排序是一种基于插入排序的排序算法，它通过逐步减少间隔（gap）来比较和交换不相邻的元素，最终实现整个数组的有序。希尔排序也被称为缩小增量排序（Diminishing Increment Sort），是插入排序的更高效改进版本。以下是对你提供的希尔排序函数的详细解析：

//代码实现
void ShellSort(int* arr, int n)
{int gap = n;// 外层循环：逐步减少间隔 gapwhile (gap > 1){// 缩小间隔，通常选择 gap = gap / 3 + 1gap = gap / 3 + 1;// 内层循环：对每个间隔 gap 进行插入排序 实现多组并排的效果for (size_t i = 0; i < n - gap; i++){int end = i;int num = arr[end + gap]; // 待插入的元素// 类似于插入排序，按当前间隔 gap 对元素进行排序while (end >= 0){if (arr[end] > num){arr[end + gap] = arr[end]; // 向后移动元素end -= gap; // 按间隔跳跃比较}else{break; // 找到正确位置后跳出循环}}// 插入元素到正确位置arr[end + gap] = num;}}
}

解析：

1. 函数定义：
   • void ShellSort(int* arr, int n)：该函数接受一个整数数组 arr 和数组长度 n，并使用希尔排序算法对数组进行排序。
2. 初始化间隔 (int gap = n)：
   • gap 初始值为数组长度 n。间隔决定了当前比较和交换的元素之间的距离。
3. 外层循环 (while (gap > 1))：
   • 外层循环用于逐步缩小间隔 gap，直到 gap 小于等于1时结束。gap 的缩减采用 gap = gap / 3 + 1，这是一种常见的选择，可以保证每次缩减间隔时依然覆盖较大的范围。
4. 内层循环 (for (size_t i = 0; i < n - gap; i++))：
   • 内层循环用于对每个间隔 gap 进行插入排序。i 表示当前已排序的元素位置，i + gap 是待插入元素的索引。
5. 待插入的元素 (int num = arr[end + gap])：
   • num 存储当前间隔 gap 后待插入的元素值，即 arr[i + gap]。
6. 插入排序的过程 (while (end >= 0))：
   • 这一部分与直接插入排序类似，只是每次比较和移动的元素间隔为 gap，而不是相邻的元素。
   • 条件判断 (if (arr[end] > num))：
     • 如果 arr[end] 大于 num，则将 arr[end] 向后移动到 arr[end + gap]，并且 end 减少 gap 继续比较。
   • 循环终止条件 (else { break; })：
     • 一旦找到比 num 小的元素位置，说明 num 应该插入到 arr[end + gap]，跳出循环。
7. 插入元素 (arr[end + gap] = num)：
   • 将 num 插入到正确的位置 arr[end + gap]。
8. 最后一次排序 (gap = 1)：
   • 当 gap 减小到1时，希尔排序退化为直接插入排序，对所有相邻元素进行一次最终的排序。此时，整个数组就已经基本有序了，插入排序的效率较高。

由于希尔排序的时间复杂度涉及一些非常复杂的数学知识,我们这里就不继续深入探讨,几个结论,希尔排序的时间复杂度大约是O(n^1.5)

2.2选择排序

2.2.1直接选择排序

直接选择排序（Selection Sort）是一种简单直观的排序算法，它通过多次扫描未排序的部分，每次从中找到最大值或最小值，将其放到已排序部分的末尾或开头，逐步构建有序数组。以下是你提供的直接选择排序函数的详细解析：

void SelectSort(int* arr, int n)
{int left = 0;int right = n - 1;int maxi = left, mini = left;while (left < right){// 找到当前未排序部分的最大值和最小值for (int i = left + 1; i <= right; i++){if (arr[i] < arr[mini]){mini = i; // 更新最小值的位置}if (arr[i] > arr[maxi]){maxi = i; // 更新最大值的位置}}// 将最小值交换到未排序部分的开头// 如果最大值在最小值的位置，先更新最大值的位置if (maxi == left){maxi = right;}Swap(&arr[mini], &arr[left]);Swap(&arr[maxi], &arr[right]);// 缩小范围left++;right--;}
}

解析：

1. 函数定义：
   • void SelectSort(int* arr, int n)：该函数接受一个整数数组 arr 和数组长度 n，使用直接选择排序算法对数组进行排序。
2. 初始化左右边界 (int left = 0, right = n - 1)：
   • left 和 right 分别表示当前未排序部分的左边界和右边界。排序的目标是逐步将最小值移到左边界，将最大值移到右边界。
3. 初始化最大值和最小值的位置 (int maxi = left, mini = left)：
   • maxi 和 mini 分别用于记录未排序部分中当前最大值和最小值的位置。初始时它们都指向未排序部分的左边界 left。
4. 主循环 (while (left < right))：
   • 主循环不断缩小未排序部分的范围，直到 left 和 right 相遇为止。每次迭代，确定当前范围内的最大值和最小值，然后将它们放在正确的位置。
5. 内层循环 (for (int i = left + 1; i <= right; i++))：
   • 内层循环扫描当前未排序部分的每个元素，找出最小值和最大值的位置。mini 和 maxi 在循环过程中不断更新。
6. 处理最大值在左边界的特殊情况 (if (maxi == left))：
   • 如果最大值位于左边界 left，在交换最小值到左边界之前，需要提前更新 maxi 的位置为右边界 right。这是因为接下来会将最小值交换到左边界，可能会覆盖当前的 maxi。
7. 交换最小值和最大值：
   • Swap(&arr[mini], &arr[left])：将最小值交换到左边界 left。
   • Swap(&arr[maxi], &arr[right])：将最大值交换到右边界 right。
8. 缩小范围 (left++, right--)：
   • 每次成功交换后，将左边界 left 向右移一位，右边界 right 向左移一位，缩小未排序部分的范围，进入下一轮排序。

直接选择排序的时间复杂度分析

1. 最坏情况下的时间复杂度：
   • 比较次数：对于每一轮扫描，直接选择排序需要在未排序部分中找到最大值和最小值。对于第 i 轮，未排序部分包含 n - 2i 个元素，因此需要进行 n - 2i - 1 次比较。整个排序过程中的比较次数可以表示为：$$比较次数=(n-1)+(n-3)+\cdots +1=\frac{(n-1)+1}{2}\times \frac{n}{2}\approx \frac{n^2}{4}$$
   • 所以，最坏情况下的时间复杂度为 O(n^2)。
2. 平均情况下的时间复杂度：
   • 平均情况下的比较次数与最坏情况类似，仍然是 O(n^2)，因为直接选择排序的操作步骤与数据的初始排列无关，总是执行相同的比较和交换操作。
3. 最佳情况下的时间复杂度：
   • 即使数组已经有序，直接选择排序仍然需要扫描数组以确定最大值和最小值，因此最佳情况下的时间复杂度仍为 O(n^2)。

时间复杂度总结：

• 最坏情况：O(n^2)
• 平均情况：O(n^2)
• 最佳情况：O(n^2)

直接选择排序的空间复杂度分析

直接选择排序是原地排序算法，不需要额外的存储空间来存储临时数据，除了几个用于交换和迭代控制的辅助变量。因此，空间复杂度是 O(1)。

空间复杂度总结：

• 空间复杂度：O(1)

2.2.2堆排序

堆排序在我之前的博客有讲到,大家自行跳转到该博客去了解堆排序堆

🥇结语

通过本篇文章的学习，您应该已经掌握了插入排序和选择排序算法的基本原理及其在C语言中的实现方法。在下一章,我们将会讲解的是快速排序以及归并排序还有计数排序。排序是许多复杂算法的基础，理解这些基本算法不仅能够帮助您优化代码性能，还能为您在数据结构和算法的学习之路上奠定坚实的基础。我们鼓励您在实践中不断运用和优化这些算法，从而加深理解。在未来的文章中，我们将探讨更多高级的数据结构和算法，敬请期待！