比较之舞，优雅演绎排序算法的智美篇章
大家好，这里是小编的博客频道
小编的博客：就爱学编程
很高兴在
CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！
本文目录
- 引言
- 正文
- 一、冒泡排序：数据海洋中的升腾之光
- 1、定义与原理
- 2、算法步骤
- 3、性能分析
- 4、优化方案
- 5、适用场景
- 二、选择排序：万千数据中的最优寻觅之旅
- 1、什么是选择排序
- 2、选择排序的工作原理
- 3、选择排序的具体步骤
- 4、C语言实现选择排序
- 5、选择排序的优缺点
- （1）优点
- （2）缺点
- 6、选择排序的应用场景
- 三、堆排序：肩担比较算法里的秩序之责
- 1、概述
- 2、基本思想
- 3、实现步骤
- （1）. 构建初始堆
- （2）. 调整堆并排序
- 4、代码示例
- 5、优缺点分析
- （1）优点
- （2）缺点
- 6、总结
- 四、插入排序：简单却强大的数据整理工具
- 1、概述
- 2、算法步骤
- 3、示例
- 4、时间复杂度分析
- 五、希尔之光：跨越间隔的优雅排序之旅
- 1、引言
- 2、希尔排序的原理
- 3、希尔排序的实现步骤
- 4、希尔排序的优缺点
- （1）优点
- （2）缺点
- 六、快速排序：速度与效率的完美平衡
- 1. 基本快速排序
- 霍尔法（Hoare法）
- 挖坑法
- 快慢指针法
- 2、随机化快速排序
- 3、三向切分快速排序
- 4.、插入排序优化
- 5、非递归优化
- 总结
- 七、分而治之，合而有序：深度探索归并排序
- 1、归并排序的原理
- 2、归并排序的递归实现
- 3、归并排序的非递归实现
- 快乐的时光总是短暂，咱们下篇博文再见啦！！！如果本篇文章对你有帮助的话不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！
引言
在浩瀚的数字世界中，比较算法如同一座桥梁，连接着无序与有序，混沌与规律。它们以智慧为笔，以数据为墨，绘制出一幅幅令人叹为观止的排序画卷。
当我们置身于庞大的数据集前，面对杂乱无章的信息海洋，是比较算法赋予了我们一双慧眼，让我们能够迅速洞察数据的内在秩序。通过巧妙的比较与交换，它们将散乱的数据点编织成一条条有序的序列，如同夜空中璀璨的星辰，按照一定的轨迹排列，展现出无尽的魅力。
在本篇博客中，小编将和大家一起踏上探索比较算法的奇妙旅程。从基础的冒泡排序、选择排序到进阶的插入排序、堆排序再到高效的快速排序、归并排序，每一种算法都蕴含着独特的智慧和美感。小编将深入剖析它们的原理，探讨它们的性能特点，感受它们在数据处理中的强大力量。
让我们一起走进比较算法的世界，领略它们的智美风采，共同开启一段充满挑战与收获的旅程吧！
那接下来就让我们开始遨游在知识的海洋！
正文
一、冒泡排序：数据海洋中的升腾之光
1、定义与原理
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换的元素为止，也就是说该数列已经排序完成。这个算法的名字由来是因为越小（或越大）的元素会经过交换慢慢“浮”到数列的顶端。
- 具体来说，冒泡排序从序列中的第一个元素开始，依次对相邻的两个元素进行比较和交换操作。如果前一个元素大于后一个元素，则交换它们的位置；如果前一个元素小于或等于后一个元素，则不进行交换。这一比较和交换的过程一直持续到最后一个还未排好序的元素为止。每一趟操作完成后，序列中最大的未排序元素就被放置到了所有未排序的元素中最后的位置上，而其它较小的元素则被移动到了序列的前面。
2、算法步骤
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
3、性能分析
-
时间复杂度：
- 最好情况：
O(n)（当输入数据已经有序时，只需进行一趟扫描即可确定整个序列已排序，从而立即退出函数）。 - 平均和最坏情况：
O(n^2)。因为冒泡排序需要进行大量的比较和交换操作，且随着数据规模的增大，所需的操作次数呈平方倍增长。
- 最好情况：
-
空间复杂度：
O(1)。冒泡排序只需要一个额外的变量用于交换元素，不需要额外的存储空间来存储中间结果。 -
稳定性：冒泡排序是一种稳定的排序算法。在排序过程中，只有当两个相邻元素的大小关系不满足要求时才进行交换操作。如果两个相等的元素不相邻，即使通过前面的两两交换把它们变成相邻的也不会进行交换操作，因此相等元素的相对位置在排序前后不会改变。
4、优化方案
虽然冒泡排序的时间复杂度较高，但在某些情况下可以通过一些优化方案来提高其效率。例如：
- 设置一个标志位来检测是否进行了交换操作。如果在某一趟排序中没有进行任何交换操作，则说明整个序列已经有序，可以提前结束排序过程。
- 记录每一趟排序中最后一次交换操作的位置。下一趟排序时只需要对该位置及其之前的元素进行比较和交换操作即可减少不必要的比较次数。
经典实现：
void Swap(int* p1, int* p2) {
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//冒泡排序
void BubbleSort(int* a, int n) {
for (int i = 0; i < n; i++) {
int change = 0;
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
change = 1;
Swap(&a[j], &a[j + 1]);
}
}
if (change == 0) break;
}
}
5、适用场景
- 冒泡排序适用于小规模数据的排序任务。由于它的时间复杂度较高且缺乏适应性（即使在部分已经有序的情况下仍然需要进行完整的比较和交换操作），因此在处理大规模数据集时效率较低且无法满足实时性要求。然而对于小规模的数据集来说，冒泡排序的实现简单易懂且易于调试和维护，因此在实际应用中仍有一定的使用价值。
综上所述：
- 冒泡排序作为一种经典的排序算法具有稳定、简单易懂等特点但也存在时间复杂度高、缺乏适应性等缺点。
二、选择排序：万千数据中的最优寻觅之旅
1、什么是选择排序
选择排序（Selection Sort）是一种简单直观的排序算法，其基本思想是反复从未排序的数列中选择最小的元素，将其加入到已排序的数列中，最终得到一个有序的数列。这种排序方法既可以从小到大排序，也可以从大到小排序。
2、选择排序的工作原理
选择排序的工作过程如下：
- 1. 将待排序的数组划分为已排序和未排序两部分。初始时，已排序部分为空，未排序部分为整个数组。
- 2. 在每一轮排序中，从未排序部分找出最小（或最大）的元素。
- 3. 将这个最小（或最大）元素与未排序部分的起始位置元素交换，从而将其放入已排序部分的末尾。
- 4. 重复上述步骤，直到所有元素均排序完毕。
例如，对于数组 [88, 5, 15, 56, 32, 18, 69]，按照从小到大的顺序进行排序的过程如下：
- 第一轮，在未排序部分
[88, 5, 15, 56, 32, 18, 69]中找到最小的元素5，将其与未排序部分的起始位置元素88交换，得到[5, 88, 15, 56, 32, 18, 69]。 - 第二轮，在未排序部分
[88, 15, 56, 32, 18, 69]中找到最小的元素15，与起始位置元素88交换，得到[5, 15, 88, 56, 32, 18, 69]。 - 依此类推，经过多轮比较和交换，最终使整个数组有序。
3、选择排序的具体步骤
假设要对数组 arr[] 进行排序，数组的长度为 n，具体步骤如下：
-
- 从数组的第一个元素开始，即
i = 0。
- 从数组的第一个元素开始，即
-
- 对于每个
i，从i + 1到n - 1中找到最小的元素，并记录其索引min_index。
- 对于每个
-
- 如果
min_index不等于i，则交换arr[i]和arr[min_index]。
- 如果
-
- 增加
i，重复步骤 2 和 3，直到i = n - 2。
- 增加
4、C语言实现选择排序
以下是一个用C语言实现选择排序的代码示例：
// 交换两个元素的值
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 选择排序函数
void selectionSort(int arr[], int n) {
int i, j, min_index;
for (i = 0; i < n - 1; i++) {
min_index = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
if (min_index != i) {
swap(&arr[i], &arr[min_index]);
}
}
}
5、选择排序的优缺点
（1）优点
- 算法简单：选择排序的原理易懂，实现起来也相对简单。无论是初学者还是经验丰富的程序员，都能快速理解并掌握这种排序方法。
- 数据移动次数少：在每次迭代中，只需要移动最小（或最大）的元素到正确的位置，这在一定程度上减少了数据的移动次数。
- 空间复杂度低：选择排序法只需要一个额外的变量来保存最小值或最大值的下标，不需要额外的内存空间，是一种原地排序算法。
（2）缺点
- 时间复杂度高：选择排序的时间复杂度为 O(n^2)，其中 n 为待排序数据的数量。在处理大规模数据时性能不佳。
- 不稳定：选择排序是一种不稳定的排序算法。这意味着如果两个元素的值相同，它们在排序后的顺序可能会发生变化。
6、选择排序的应用场景
- 小规模数据：由于选择排序的算法复杂度为 O(n^2)，它对于小规模数据的排序是非常高效的。
- 部分有序数据：如果待排序的数据集合中已经部分有序，即只有少数元素需要进行排序，选择排序是一种合适的选择。
- 内存受限环境：选择排序是一种原地排序算法，它只需要一个额外的变量来进行元素交换，这使得它在内存受限的嵌入式系统或其他资源有限的环境中得到广泛应用。
总的来说：
- 选择排序虽然效率相对较低，但其实现简单直观，非常适合作为学习排序算法的起点。同时，在处理部分有序或规模较小的数据时表现良好，因此在实际应用中也有其独特的价值。
三、堆排序：肩担比较算法里的秩序之责
1、概述
- 堆排序是一种基于二叉堆数据结构所设计的排序算法，属于选择排序的一种。它通过构建最大堆或最小堆，然后不断删除堆顶元素并调整堆结构来实现排序。堆排序的时间复杂度为O(n log n)，空间复杂度为O(1)，具有稳定性和适用性广的优点。
2、基本思想
- 堆是一个近似完全二叉树的结构，同时满足堆积的性质：即子节点的键值总是小于（或者大于）它的父节点。在堆的数据结构中，堆中的最大值（或最小值）总是位于根节点。
堆排序的基本思想是：
- 1. 将待排序的序列构造成一个大顶堆（或小顶堆），此时整个序列的最大值（或最小值）就是堆顶的根节点。
- 2. 将堆顶元素与末尾元素交换，然后将剩余的堆重新构造成一个堆，得到新的最大值（或最小值）。
- 3. 重复上述过程，直到堆的大小减至1，此时序列已经完全排序。
3、实现步骤
（1）. 构建初始堆
- 首先需要根据给定的待排序数组构建一个初始堆。构建堆的过程通常是从最后一个非叶子节点开始，向上遍历每个节点，对每个节点进行下沉操作，以确保每个节点都满足堆的性质。
（2）. 调整堆并排序
- 将堆顶元素（最大值或最小值）与末尾元素交换，然后移除末尾元素（或将其视为已排序部分），此时堆的大小减一。接着对剩余部分重新进行下沉操作，以恢复堆的性质。这个过程重复进行，直到堆的大小减至1，排序完成。
4、代码示例
以下是用C语言实现的堆排序代码：
// Function to swap two elements
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// Function to heapify a subtree rooted with node i which is an index in arr[]
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left = 2*i + 1
int right = 2 * i + 2; // right = 2*i + 2
// See if left child of root exists and is greater than root
if (left < n && arr[left] > arr[largest])
largest = left;
// See if right child of root exists and is greater than root
if (right < n && arr[right] > arr[largest])
largest = right;
// Change root, if needed
if (largest != i) {
swap(&arr[i], &arr[largest]);
// Heapify the root.
heapify(arr, n, largest);
}
}
// Main function to do heap sort
void heapSort(int arr[], int n) {
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
swap(&arr[0], &arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
5、优缺点分析
（1）优点
1.时间复杂度稳定 ：无论输入数组的状态如何，堆排序的时间复杂度总是O(n log n)。
2. 空间复杂度低 ：堆排序是原地排序算法，只需要常数个额外的空间，空间复杂度为O(1)。
（2）缺点
- 不稳定排序 ：堆排序是不稳定排序，相同元素的相对顺序可能会被改变。
- 常数系数较大 ：尽管堆排序的时间复杂度和快速排序相同，但堆排序的常数系数较大，实际运行速度往往比不上快速排序。
6、总结
- 堆排序是一种高效且稳定的排序算法，特别适用于处理大型数据集和外部排序场景。虽然它在某些方面可能不如其他排序算法出色，但在许多实际应用中仍然是一种非常有用的工具。
四、插入排序：简单却强大的数据整理工具
1、概述
- 插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上通常使用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，找到合适位置并插入时，不需要移动其它元素。
2、算法步骤
- 初始状态：假设待排序数组为
A[0...n-1]，其中前i-1个元素已经排好序（即A[0...i-1]是有序的），第i个元素到最后一个元素A[i...n-1]是无序的。 - 取无序区首元素：取出无序区的第一个元素
A[i]，将其视为“当前元素”。 - 在有序区寻找插入位置：将当前元素与有序区的元素进行比较，如果当前元素比有序区的某个元素小，则将该有序区的元素向后移动一位，直到找到当前元素的正确插入位置。
- 插入当前元素：将当前元素插入到找到的位置上，此时有序区长度增加1，无序区长度减少1。
- 重复上述过程：对
i=1, 2, ..., n-1均执行上述操作，直至整个数组有序。
3、示例
假设有一个数组[5, 2, 9, 1, 5, 6]，我们对其进行插入排序：
- 1. 初始状态：
[5, 2, 9, 1, 5, 6]- 2.
i=1，A[1]=2，小于A[0]=5，将5右移，2插入到首位：[2, 5, 9, 1, 5, 6]- 3.
i=2，A[2]=9，大于A[1]=5，无需移动，保持原样：[2, 5, 9, 1, 5, 6]- 4.
i=3，A[3]=1，小于A[2]=9和A[1]=5以及A[0]=2，依次将9、5和2右移，1插入到首位：[1,2, 5, 9, 5, 6]- 5.
i=4，A[4]=5，小于A[3]=9但大于A[2]=5和A[1]=2以及A[0]=1，将9右移，5插入到第三位：[1, 2, 5, 5, 9, 6]- 6.
i=5，A[5]=6，小于A[4]=9但大于前面的所有元素，将9右移，6插入到最后一位：[1, 2, 5, 5, 6, 9]- 最终得到有序数组
[1, 2, 5, 5, 6, 9]。
代码为：
//插入排序-------O(N ^ 2)
void InsertSort(int* a, int n) {
for (int i = 1; i < n; i++) {
int end = i - 1; //对应有序数字最后一个元素的下标
int temp = a[end + 1]; //end的后一个，也就是要插入的元素
while (end >= 0) {
if (temp < a[end])
{
a[end + 1] = a[end];
--end;
}
else {
break;
}
}
a[end + 1] = temp;
}
}
4、时间复杂度分析
- 最坏情况：当输入数组是逆序的时，需要进行
n(n-1)/2次比较和交换操作，因此时间复杂度为O(n^2)。 - 最好情况：当输入数组已经是有序的时，只需要进行
n-1次比较而无需交换操作，因此时间复杂度为O(n)。 - 平均情况：时间复杂度仍然为O(n^2)，因为即使输入数组部分有序，也可能需要多次比较和交换操作来维护有序性。
- 尽管插入排序在最坏情况下的时间复杂度较高，但由于其实现简单且在小规模数据集上表现良好，因此在某些情况下仍具有实用价值。
五、希尔之光：跨越间隔的优雅排序之旅
1、引言
- 在计算机科学中，排序算法是数据处理领域的基础和核心。在众多排序算法中，
希尔排序（Shell Sort）以其独特的分治策略和高效的性能脱颖而出，成为众多开发者青睐的选择。本文将详细介绍希尔排序的原理、实现步骤以及它的优缺点，带你领略这一算法的优雅与魅力。
2、希尔排序的原理
- 希尔排序是由计算机科学家Donald Shell于1959年提出的一种基于插入排序的改进算法。它通过将待排序数组分割成若干个子序列，分别对每个子序列进行插入排序，从而逐步减少数据的无序程度，最终实现对整个数组的排序。
- 希尔排序的关键在于选择合适的“
间隔（gap）”序列。初始时，选择一个较大的间隔值，将数组分割成多个子序列；然后，对每个子序列进行插入排序；接着，逐渐减小间隔值，重复上述过程，直到间隔值为1时，对整个数组进行一次最终的插入排序。这样，通过多次局部有序化，可以大大加快整体排序的速度。
3、希尔排序的实现步骤
- 初始化间隔值：选择一个合适的初始间隔值，通常可以选择数组长度的一半或更小的值作为起始间隔。
- 分组排序：根据当前间隔值，将数组分割成多个子序列，对每个子序列进行插入排序。
- 更新间隔值：按照一定的规则（如减半）更新间隔值，继续对新的子序列进行插入排序。
- 重复步骤2和3：直到间隔值为1时，对整个数组进行一次最终的插入排序。
以下是一个简单的希尔排序C语言实现示例：
//希尔排序-------O(N ^ 1.3)
void ShellSort(int* a, int n) {
int gap = n;
while (gap > 1) {
gap /= 2;
/*for (int i = 0; i < gap; i++) {
for (int j = i; j < n - gap; j += gap) {
int end = j;
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;
}
}*/
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;
}
PrintArray(a, n);
printf("\n");
}
}
4、希尔排序的优缺点
（1）优点
- 效率高：相比于简单的插入排序，希尔排序通过多次局部有序化，减少了数据移动的次数，提高了排序效率。
- 稳定性好：虽然希尔排序不是稳定的排序算法（即相同元素的相对顺序可能会改变），但在实际应用中，其稳定性问题通常可以忽略不计。
- 适用范围广：希尔排序适用于各种类型的数据，包括整数、浮点数和字符串等。
（2）缺点
- 间隔值选择困难：希尔排序的性能很大程度上取决于间隔值的选择。不同的间隔值序列可能导致截然不同的排序效果。因此，如何选择合适的间隔值序列是一个难题。
- 最坏情况性能不佳：在某些情况下，希尔排序的最坏时间复杂度可能达到O(n^2)，尽管在实际应用中这种情况较为罕见。
四、总结与展望
- 希尔排序作为一种经典的排序算法，以其独特的
分治策略和高效的性能在数据处理领域发挥着重要作用。然而，随着计算机科学的发展和新算法的涌现，希尔排序也面临着来自其他更高效排序算法的挑战。未来，我们可以期待更多关于希尔排序的优化和改进，以应对更加复杂和多样化的数据处理需求。同时，我们也可以借鉴希尔排序的思想和方法，探索和发展更多新的排序算法和技术。
六、快速排序：速度与效率的完美平衡
快速排序是一种非常高效的排序算法，其基本思想是通过一个划分操作将待排序的数组分为两个子数组，左边子数组的元素都比右边子数组的元素小，然后递归地对这两个子数组进行排序。下面是快速排序的多种版本及其实现原理和优化方法的详细介绍。
1. 基本快速排序
原理
- 选择基准：从数组中选择一个元素作为基准（pivot）。
- 分区操作：将数组分为两部分，左边部分的所有元素都小于基准，右边部分的所有元素都大于基准。
- 递归排序：对左右两个子数组递归地进行快速排序。
三种版本：
霍尔法（Hoare法）
霍尔法是以快速排序的创始人霍尔命名的，也是快速排序最初的实现版本。其基本思想是用两个指针分别指向待排序数组的开头和结尾，然后让这两个指针相向而行，根据与key值的大小关系进行移动和交换，直到两者相遇。具体步骤如下：
任取一个待排序数组中的数作为key值（可以取头值、尾值或中间值等）。
如果取头值作为key值，则让右指针先移动；如果取尾值作为key值，则让左指针先移动。“移动”的过程是：
right指针直到找到小于key的值才停下来，left指针直到找到大于key的值才停下来。
将left和right所对应的值进行交换。
重复上述过程，直到left和right相遇。此时，将key值和right所指向的值进行交换，right最后指向的位置就是key值应该所在的位置。
以right为界，将数组一分为二，递归地对左右两部分进行排序。
代码实现：
//快速排序-----霍尔
void QuickSort1(int* a, int left, int right) {
if (left >= right) return;
int end = right, begin = left, keyi = left;
while (left < right) {
//右指针找小
while (left < right && a[right] >= a[keyi]) {
--right;
}
//左指针找大
while (left < right && a[left] <= a[keyi]) {
++left;
}
Swap(&a[right], &a[left]);
}
//最后对调将目标值放到合适的位置
Swap(&a[keyi], &a[left]);
keyi = left;
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi + 1, end);
}
霍尔法的优势在于其高效性，但理解起来可能相对复杂一些。
挖坑法
挖坑法是快速排序的一种实现方式，其思路与霍尔法类似，但更容易理解。具体步骤如下：
选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑。
定义left和right两个指针，分别从数组的左右两端开始相向而行。
right指针向左移动，直到找到比key小的数；然后将该数填入坑中，并将hole更新为当前right的位置。
left指针向右移动，直到找到比key大的数；然后将该数填入当前的hole中，并再次更新hole为当前left的位置。
重复上述步骤，直到left和right相遇。此时，将key值填入最后的hole中。
以hole为界，将数组一分为二，递归地对左右两部分进行排序。
代码实现：
//快速排序-----挖坑
void QuickSort2(int* a, int left, int right) {
if (left >= right) return;
int end = right, begin = left;
int midi = GetMidNumi(a, left, right);
Swap(&a[left], &a[midi]);
int key = a[left], hole = left;
while (left < right) {
//右指针找小
while (left < right && a[right] >= key) {
--right;
}
a[hole] = a[right];
hole = right;
//左指针找大
while (left < right && a[left] <= key) {
++left;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
QuickSort2(a, begin, hole - 1);
QuickSort2(a, hole + 1, end);
}
挖坑法的优势在于其直观易懂，便于理解和实现。
快慢指针法
这种方法使用两个指针从数组的两端向中间移动，直到它们相遇或交错。
代码实现：
//快速排序-----快慢指针
void QuickSort3(int* a, int left, int right) {
if (left >= right) return;
int keyi = left;
int prev = left, cur = left + 1;
int midi = GetMidNumi(a, left, right);
Swap(&a[left], &a[midi]);
while (cur <= right){
if (a[cur] < a[keyi]) {
Swap(&a[cur], &a[++prev]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
QuickSort3(a, left, keyi - 1);
QuickSort3(a, keyi + 1, right);
}
2、随机化快速排序
原理
- 随机选择基准：在每次划分之前，随机选择一个元素作为基准，以减少最坏情况的发生概率。
- 分区操作：与基本快速排序相同。
- 递归排序：对左右两个子数组递归地进行快速排序。
代码示例
#include <stdlib.h>
int randomPartition(int arr[], int low, int high) {
int random = low + rand() % (high - low + 1);
swap(&arr[random], &arr[high]);
return partition(arr, low, high);
}
void randomizedQuickSort(int arr[], int low, int high) {
if (low < high) {
int pi = randomPartition(arr, low, high);
randomizedQuickSort(arr, low, pi - 1);
randomizedQuickSort(arr, pi + 1, high);
}
}
3、三向切分快速排序
原理
- 选择基准：选择一个元素作为基准。
- 三向分区：将数组分为三部分：
- 左边部分的所有元素都小于基准。
- 中间部分的所有元素都等于基准。
- 右边部分的所有元素都大于基准。
- 递归排序：只对左右两个子数组递归地进行快速排序，中间部分已经有序。
代码示例
void threeWayQuickSort(int arr[], int low, int high) {
if (high <= low) return;
int lt = low, gt = high;
int pivot = arr[low];
int i = low + 1;
while (i <= gt) {
if (arr[i] < pivot) {
swap(&arr[lt++], &arr[i++]);
} else if (arr[i] > pivot) {
swap(&arr[i], &arr[gt--]);
} else {
i++;
}
}
threeWayQuickSort(arr, low, lt - 1);
threeWayQuickSort(arr, gt + 1, high);
}
4.、插入排序优化
原理
- 选择基准：选择一个元素作为基准。
- 分区操作：将数组分为两部分。
- 递归排序：当子数组的大小小于某个阈值时，使用插入排序而不是快速排序，以减少递归调用的开销。
代码示例
void hybridQuickSort(int arr[], int low, int high, int threshold) {
while (low < high) {
if (high - low < threshold) {
insertionSort(arr, low, high);
break;
} else {
int pi = partition(arr, low, high);
hybridQuickSort(arr, low, pi - 1, threshold);
low = pi + 1;
}
}
}
void insertionSort(int arr[], int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
5、非递归优化
因为递归算法都存在一个无法避免的问题——递归深度太大会导致栈溢出的问题，所以我们应该掌握非递归实现各种递归算法的技能。
- 递归算法改非递归一般有两种思路：（1）直接改循环；（2）借用数据结构其中栈是最为常用的。
- 对于快速排序，使用栈是最好模拟的方式。
代码实现：
（1）ST.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#define MAXCAPACITY 4
typedef int Datastyle;
typedef struct stack {
Datastyle* a; //指向有效数据的指针
int top;
//给top初始化一般要么给-1，要么给0，如果给1及以上就会造成空间的浪费，给-2及以下也会造成空间的浪费（除非进行特殊的处理，分情况给top加值）
//如果top初始化给的是-1，则top代表的是栈顶元素所在位置的下标；如果top初始化给的是0，则top代表的是栈顶元素所在位置的下一个位置的下标
//这是因为（以插入为例）每一次入栈后，top必定加1-----而top初始化给-1元素入栈就是top先++再赋值；而top初始化给0元素入栈就是top先赋值再++
//但无论哪种入栈方式，最终的结果都是top++。至于为什么两种不同的给top赋初值对应不同的入栈方式也是取决于数组的下标从0开始的特点
//本次我们就展示top初始化为0的栈的写法
int capacity;
}ST;
//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestory(ST* ps);
//插入数据（从栈顶）----（入栈，压栈）
void STPush(ST* ps, Datastyle x);
//删除数据（从栈顶）----（出栈）
void STPop(ST* ps);
//访问栈顶元素
Datastyle STTop(ST* ps);
//得出栈的元素个数
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
ST.c
#include"ST.h"
//初始化栈
void STInit(ST* ps) {
assert(ps);
Datastyle* temp = (Datastyle*)malloc(MAXCAPACITY * sizeof(Datastyle));
if (temp == NULL) {
perror("malloc fail");
exit(-1);
}
ps->a = temp;
ps->capacity = MAXCAPACITY;
ps->top = 0;
}
//销毁栈
void STDestory(ST* ps){
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
//插入数据（从栈顶）----（入栈，压栈）
void STPush(ST* ps, Datastyle x) {
assert(ps);
//判断是否满了
if (ps->top == ps->capacity) {
Datastyle* temp = (Datastyle*)realloc(ps->a, 2 * ps->capacity * sizeof(Datastyle)); //扩容为当前容量的两倍比较合理
if (temp == NULL) {
perror("realloc fail");
return;
}
ps->capacity *= 2;
ps->a = temp;
}
ps->a[ps->top++] = x;
}
//判空
bool STEmpty(ST* ps) {
return (ps->top == 0);
}
//删除数据（从栈顶）----（出栈）
void STPop(ST* ps) {
assert(ps && !STEmpty(ps));
--ps->top;
}
//访问栈顶元素
Datastyle STTop(ST* ps) {
return ps->a[ps->top - 1];
}
//得出栈的元素个数
int STSize(ST* ps) {
assert(ps);
return ps->top;
}
Sort.c
#include"ST.h"
//快速排序-----非递归实现------入栈元素：每次递归会发生改变的参数
void QuickSortNonR(int* a, int left, int right) {
//Chaucer创建栈
ST st;
//初始化栈
STInit(&st);
//先入栈
STPush(&st, right);
STPush(&st, left);
while (!STEmpty(&st)){
//因为栈先入后出的特点，所以我们先入右再入左
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
//进行单趟排序并返回keyi
int keyi = SingalQuickSort(a, begin, end);
//[begin,keyi - 1] keyi [keyi + 1, end]
//因为栈先入后出的特点，所以我们先入右再入左，不过当区间内仅剩一个元素或没有元素的时候，我们也不应该入栈
if (keyi + 1 < end) {
STPush(&st, end);
STPush(&st, keyi + 1);
}
if (begin < keyi - 1) {
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
//销毁栈
STDestory(&st);
}
总结
- 快速排序的多种版本和优化方法可以显著提高其在不同场景下的性能。选择合适的版本和优化方法，可以根据具体的数据特性和应用场景，进一步提升排序算法的效率和稳定性。希望这些介绍能帮助你更好地理解和应用快速排序算法。
七、分而治之，合而有序：深度探索归并排序
1、归并排序的原理
归并排序的基本思想是将一个待排序的数组分成两个小数组，分别对这两个小数组进行排序，然后将这两个已排序的小数组合并成一个最终的已排序数组。其关键步骤包括分解和合并两个阶段：
- 分解阶段：将待排序的数组分割成两个子数组，直到每个子数组的长度小于或等于1（此时认为是有序的）。
- 合并阶段：将两个有序的子数组合并成一个更大的有序数组，直到最终合并为整个数组的排序结果。
- 归并排序的时间复杂度为O(n log n)，其中n是待排序数组的元素个数。这是因为每次分解都将数组规模减半，而合并操作则需要遍历整个数组。由于分解和合并都是线性时间复杂度的操作，因此总的时间复杂度为O(n log n)。
- 此外，归并排序是一种稳定的排序算法，即相同元素的相对顺序在排序前后保持不变。
2、归并排序的递归实现
- 递归实现是归并排序的一种常见方式。其基本思路是不断地将数组分解成更小的子数组，直到每个子数组只有一个元素或为空，然后再将这些子数组合并起来形成有序的数组。
以下是归并排序递归实现的C语言代码示例：
#include <stdio.h>
#include <stdlib.h>
// 合并两个有序数组arr[left...mid]和arr[mid+1...right]到temp[]中
void merge(int arr[], int left, int mid, int right, int temp[]) {
int i = left; // 左子数组的起始索引
int j = mid + 1;// 右子数组的起始索引
int k = 0; // 临时数组的索引
// 将较小的元素放入临时数组中
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 将剩余的元素放入临时数组中
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 将临时数组中的元素复制回原数组中
for (int p = 0; p < k; p++) {
arr[left + p] = temp[p];
}
}
// 使用递归对数组arr[left...right]进行归并排序
void mergeSort(int arr[], int left, int right, int temp[]) {
if (left < right) {
int mid = left + (right - left) / 2;
// 对左半部分进行排序
mergeSort(arr, left, mid, temp);
// 对右半部分进行排序
mergeSort(arr, mid + 1, right, temp);
// 合并左右两部分
merge(arr, left, mid, right, temp);
}
}
// 归并排序的主函数
void MergeSortWrapper(int arr[], int n) {
int *temp = (int *)malloc(n * sizeof(int));
if (temp == NULL) {
fprintf(stderr, "Memory allocation failed
");
exit(EXIT_FAILURE);
}
mergeSort(arr, 0, n - 1, temp);
free(temp);
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Given array is
");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("
");
MergeSortWrapper(arr, n);
printf("Sorted array is
");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("
");
return 0;
}
- 在这个例子中，
merge函数负责将两个有序的子数组合并成一个有序的数组，而mergeSort函数则使用递归来对数组进行分解和排序。最后，MergeSortWrapper函数为mergeSort分配了一个临时数组，并在排序完成后释放了它。
3、归并排序的非递归实现
- 虽然递归实现简洁明了，但在某些情况下可能会导致栈溢出或效率问题。因此，非递归实现也是一种重要的选择。
非递归实现通常采用迭代的方式来进行归并操作。以下是非递归实现的C语言代码示例：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 非递归归并排序函数
void mergeSortNonRecursive(int arr[], int n) {
int *temp = (int *)malloc(n * sizeof(int));
if (temp == NULL) {
fprintf(stderr, "Memory allocation failed
");
exit(EXIT_FAILURE);
}
int gap = 1; // 每次归并操作的子数组大小
while (gap < n) {
// 进行一轮归并操作
for (int i = 0; i < n; i += 2 * gap) {
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
// 处理边界情况
if (end1 >= n) {
end1 = n - 1;
}
if (begin2 >= n) {
break; // 没有第二个子数组需要归并了
}
if (end2 >= n) {
end2 = n - 1;
}
// 合并两个子数组
int j = begin1;
int k = 0;
while (begin1 <= end1 && begin2 <= end2) {
if (arr[begin1] <= arr[begin2]) {
temp[k++] = arr[begin1++];
} else {
temp[k++] = arr[begin2++];
}
}
while (begin1 <= end1) {
temp[k++] = arr[begin1++];
}
while (begin2 <= end2) {
temp[k++] = arr[begin2++];
}
// 将合并后的数组复制回原数组
memcpy(arr + i, temp + begin1 - i, (end2 - i + 1) * sizeof(int));
}
// 增加gap的值以便下一轮归并操作
gap *= 2;
}
free(temp);
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Given array is
");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("
");
mergeSortNonRecursive(arr, n);
printf("Sorted array is
");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("
");
return 0;
}