天津网站建设美丽,大型网站开发语言,南昌企业免费建站,建网站 多少钱钱#x1f38a;【数据结构与算法】专题正在持续更新中#xff0c;各种数据结构的创建原理与运用✨#xff0c;经典算法的解析✨都在这儿#xff0c;欢迎大家前往订阅本专题#xff0c;获取更多详细信息哦#x1f38f;#x1f38f;#x1f38f; #x1fa94;本系列专栏 -… 【数据结构与算法】专题正在持续更新中各种数据结构的创建原理与运用✨经典算法的解析✨都在这儿欢迎大家前往订阅本专题获取更多详细信息哦 本系列专栏 - 数据结构与算法_勾栏听曲_0 欢迎大家 点赞 评论 收藏⭐️ 个人主页 - 勾栏听曲_0的博客 希望本文能对你有所帮助如有不足请指正共同进步吧 莫将画竹论难易刚道繁难简更难。君看萧萧只数叶满堂春风不胜寒。 定义 快速排序是另一种基于分治技术的重要排序算法。与我们上一篇所讲的合并排序不一样。合并排序是按照元素在数组中的位置对它们进行划分快速排序按照元素的值对它们进行划分。划分是对给定数组中的元素的重新排列使得一个数组A[i]有s下标A[s]左边的元素都小于等于A[s]而所有A[s]右边的元素都大于等于A[s]。 A[0]...A[s-1],A[s],A[s1]...A[i-1] 显然在对数组建立了一个划分以后A[s]已经位于它在有序数组中的最终位置接下来我们可以继续对A[s]前和A[s]后的子数组分别进行排序(例如使用同样的方法)。注意它与合并排序的不同之处在于:在合并排序算法中将问题划分成两个子问题是很快的算法的主要工作在于合并子问题的解;而在快速排序中算法的主要工作在于划分阶段而不需要再去合并子问题的解了。 伪代码 伪代码实现 Quicksort(A[ l..r ]) //用Quicksort对子数组排序 //输入数组A[0..n-1]中的子数组A[ l..r ]由左右下标 l 和 r 定义 //输出非降序排列的子数组A[ l..r ] if l r s -Partition (A[1..r])//s是分裂位置 Quicksort( A[ l.. (s - 1)]) Quicksort(A[(s 1)..r ]) 算法解析 对于快速排序有数组A[0..n-1]子数组A[e..r]我们要选择一个中轴接下来会根据该元素的值来划分子数组。选择中轴有许多不同的策略当我们分析该算法的效率时我们会回到这个话题。现在我们只使用最简单的策略——选择子数组的第一个元素即pA[0]。 然后 我们将分别从子数组的两端进行扫描并且将扫描到的元素与中轴相比较。从左到右的扫描(下面用指针i表示)从第二个元素开始。因为我们希望小于中轴的元素位于子数组的左半部分扫描会忽略小于中轴的元素直到遇到第一个大于等于中轴的元素才会停止。从右到左的扫描(下面用指针j表示)从最后一个元素开始。因为我们希望大于中轴的元素位于子数组的右半部分扫描会忽略大于中轴的元素直到遇到第一个小于等于中轴的元素才会停止。(为什么当遇到与中轴元素相等的元素时值得停止扫描?因为当遇到有很多相同元素的数组时这个方法可以将数组分得更加平均从而使算法运行得更快。如果我们遇到相等元素时继续扫描对于一个具有n个相同元素的数组来说划分后得到的两个子数组的长度可能分别是n~1和0从而在扫描了整个数组后只将问题的规模减1。) 两次扫描全部停止以后取决于扫描的指针是否相交会发生3种不同的情况。1、如果扫描指针i和 j不相交也就是说ij我们简单地交换A[i]和A[j]再分别对i加1对j减1然后继续开始扫描2、如果扫描指针相交也就是说i j把中轴和A[j]交换以后我们得到了该数组的一个划分3、最后如果扫描指针停下来时指向的是同一个元素也就是说i j被指向元素的值一定等于p。(为什么?)因此我们建立了该数组的一个划分分裂点的位置s i j。 我们可以把第三种情况和指针相交的情况(i j )结合起来只要i≥j就交换中轴和A[j]的位置。 下面我们来看看快速排序的视频案例 分治法_快速排序 时间效率分析 在开始讨论快速排序的效率以前我们应该要注意;如果扫描指针交叉了建立划分之前所执行的键值比较次数是n1;如果它们相等则是n。如果所有的分裂点位于相应子数组的中点这就是最优的情况。在最优情况下键值比较的次数Cbes(n)满足下面的递推式: 当n1时 根据主定理对于n2*的情况求得 。 在最差的情况下所有的分裂点都趋于极端:两个子数组有一个为空而另一个子数组仅仅比被划分的数组少一个元素。具体来说这种令人遗憾的情况会发生在升序的数组上也就是说输入的数组已经被排过序了!的确如果 A[0..n –1]是严格递增的数组并且我们将A[0]作为中轴从左到右的扫描会停在A[1]上而从右到左的扫描会一直处理到A[0]为止导致分裂点出现在0这个位置。 所以在进行了n1次比较之后建立了划分并且将A[0]和它本身进行了交换以后快速排序算法还会对严格递增的数组A[1..n-1]进行排序。对规模减小了的严格递增数组的排序会一直继续到最后一个子数组A[n-2..n-1]。这种情况下键值比较的总次数应该等于: 源码 #include stdio.h// 交换两个元素的值
void swap(int *a, int *b) {int temp *a;*a *b;*b temp;
}// 分区函数
int partition(int arr[], int low, int high) {// 选取最后一个元素作为基准值int pivot arr[high];// i指向小于基准值的最后一个元素int i (low - 1);// 遍历数组将小于基准值的元素放到左边大于基准值的元素放到右边for (int j low; j high - 1; j) {if (arr[j] pivot) {i;swap(arr[i], arr[j]);}}// 将基准值放到中间swap(arr[i 1], arr[high]);return (i 1);
}// 快速排序函数
void quickSort(int arr[], int low, int high) {if (low high) {// 将数组分为两部分左边的元素都小于右边的元素int pi partition(arr, low, high);// 递归排序左边的部分quickSort(arr, low, pi - 1);// 递归排序右边的部分quickSort(arr, pi 1, high);}
}int main() {int arr[] {10, 7, 8, 9, 1, 5};int n sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf(Sorted array: );for (int i 0; i n; i) {printf(%d , arr[i]);}return 0;
}如有小伙伴需要理解分治法思想或者合并排序可阅读这篇文章哦 分治法实现合并排序(归并排序)理解分治算法思想实现分治算法的完美例子合并排序含码源与解析https://blog.csdn.net/weixin_53050357/article/details/129718346?spm1001.2014.3001.5501
