平面设计类网站什么颜色好,海外网站速度慢,长沙推广销售,山东东营市属于几线城市大家好#xff0c;这里是小编的博客频道 小编的博客#xff1a;就爱学编程 很高兴在CSDN这个大家庭与大家相识#xff0c;希望能在这里与大家共同进步#xff0c;共同收获更好的自己#xff01;#xff01;#xff01; 本文目录 引言正文一、冒泡排序#xff1a;数据海… 大家好这里是小编的博客频道 小编的博客就爱学编程 很高兴在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 rootint left 2 * i 1; // left 2*i 1int right 2 * i 2; // right 2*i 2// See if left child of root exists and is greater than rootif (left n arr[left] arr[largest])largest left;// See if right child of root exists and is greater than rootif (right n arr[right] arr[largest])largest right;// Change root, if neededif (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 heapfor (int i n - 1; i 0; i--) {// Move current root to endswap(arr[0], arr[i]);// call max heapify on the reduced heapheapify(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。重复上述过程对i1, 2, ..., n-1均执行上述操作直至整个数组有序。 3、示例
假设有一个数组[5, 2, 9, 1, 5, 6]我们对其进行插入排序 1. 初始状态[5, 2, 9, 1, 5, 6]2. i1A[1]2小于A[0]5将5右移2插入到首位[2, 5, 9, 1, 5, 6]3. i2A[2]9大于A[1]5无需移动保持原样[2, 5, 9, 1, 5, 6]4. i3A[3]1小于A[2]9和A[1]5以及A[0]2依次将9、5和2右移1插入到首位[1,2, 5, 9, 5, 6]5. i4A[4]5小于A[3]9但大于A[2]5和A[1]2以及A[0]1将9右移5插入到第三位[1, 2, 5, 5, 9, 6]6. i5A[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.hint 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借用数据结构其中栈是最为常用的。对于快速排序使用栈是最好模拟的方式。 代码实现
1ST.h
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h#define MAXCAPACITY 4typedef 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
#includeST.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
#includeST.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);//进行单趟排序并返回keyiint 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[mid1...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;
}快乐的时光总是短暂咱们下篇博文再见啦如果本篇文章对你有帮助的话不要忘了给小编点点赞和收藏支持一下在此非常感谢
