莆田网站制作报价,网站设计的摘要,网站设计技术入股,word素材库免费欢迎来到我的博客#xff01;在今天的文章中#xff0c;我将采用一种独特且直观的方式来探讨我们的主题#xff1a;我会使用一幅图像来贯穿整篇文章的讲解。这幅精心设计的图表不仅是我们讨论的核心#xff0c;也是一个视觉辅助工具#xff0c;帮助你更深入地理解和掌握本… 欢迎来到我的博客在今天的文章中我将采用一种独特且直观的方式来探讨我们的主题我会使用一幅图像来贯穿整篇文章的讲解。这幅精心设计的图表不仅是我们讨论的核心也是一个视觉辅助工具帮助你更深入地理解和掌握本文的内容。
通过这种方式我们可以一步步深入本文的主题每个阶段都将图像作为参考。这样不仅可以增加信息的吸收和理解还能让学习过程更加生动和有趣。无论你是刚入门的新手还是寻求更深层次理解的老手这幅图都将是你理解本文内容的有力工具。
所以让我们开始这一独特的旅程一边阅读文章一边参考这幅将贯穿全文的图表深入探索我们今天的话题 想象一下你走进了一个充满了成千上万本书的巨大图书馆。这些书籍横七竖八地堆放着没有任何顺序。你需要找到一本特定的书但在这混乱中这看似是一个不可能完成的任务。这时一位图书管理员出现了。这位管理员不仅知道每本书的具体位置而且还能以令人难以置信的速度将这些书籍分类和组织起来让你轻松地找到所需的书籍。这正是快速排序算法在数据世界中的角色一个高效、精准的“信息管理员”能迅速将数据整理成有序的结构。 快速排序这个由英国计算机科学家Tony Hoare在1960年发明的算法至今仍是计算机科学中最受欢迎和广泛使用的排序算法之一。它之所以名为“快速”是因为它比其他传统排序算法如冒泡排序或插入排序要快得多尤其是在处理大量数据时。快速排序的基本思想是选择一个元素作为“基准”然后将数组分为两部分一边是小于基准的元素另一边是大于基准的元素接着递归地在这两部分进行同样的操作。 在现代计算的世界里快速排序不仅是一个算法的范例它也是处理大规模数据不可或缺的工具。从数据库的查询优化到大数据分析再到我们日常使用的搜索引擎快速排序的影响无处不在。它的效率和优雅使它成为了计算机科学中的一个经典一个在不断变化和发展的数字时代依然屹立不倒的算法巨人。 快速排序有三种方法。他们分别是“hoare版本” “挖坑法” 和 “前后指针版本”本文只介绍第一种剩下两种请挪步下一篇文章
1.hoare版本
一张图片带你秒懂过程 快速排序的基本原理
快速排序是一种高效的排序算法使用分而治之的策略来排序数据。以下是它的基本步骤 选择基准值Pivot 从数组中选择一个元素作为基准值。这个选择可以是随机的通常选择第一个或最后一个元素。 分区Partitioning 重新排列数组使得所有小于基准值的元素都排在基准之前而所有大于基准值的元素都排在基准之后。这个步骤结束后基准元素就处于其最终位置。 递归排序子数组 对基准左侧和右侧的子数组分别递归地执行快速排序。 终止条件 当子数组的大小减至1或0时递归结束因为每个元素都已经被排序。 // 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{if(right - left 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div1, right)QuickSort(array, div1, right);
}
上述为快速排序递归实现的主框架。
分区Partitioning
我们首先选择基准值将其定义为key 一般为最左或最右此时对其进行遍历L向右找比key大的值R向左找比key小的值找到了就相互交换 直到第一次相遇将key与相遇点进行交换 此时可能会有人疑问为什么相遇就一定要交换如果我们相遇后这个值比key大的情况下是否违背我们要排序的初衷呢 这里先给出答案相遇位置一定比key小。 原因 如果左边先走就无法保证一定比key小 接下来我们实现初步代码如何让他先进行左右交换并让key挪动到相遇位置
void QuickSort(int* a, int begin, int end)
{int keyi begin;int right end;int left begin ;while (left right){//左边找大while(left right a[left] a[keyi])//加入的原因是如果到相遇点时left还是小于kei他不会在相遇点停下并且再次交换就颠倒顺序了{left;}//右边找小while (left right a[right] a[keyi]){--right;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);keyi left;} 此时我们已经完成初步交换 那我们是不是可以得出如果接下来让左边变得有序右边也有序。整体就有序了 递归排序子数组
接下来我们对左右子数组进行递归处理就可以得出一个有序数组
接下来我们先对左子树进行递归 进行处理后3就是key就是相遇处接着再对左子数组进行处理递归处理直到只剩一个数组时返回 接着再对右子树进行处理以此类推这里不多做赘述
终止条件
这里涉及到递归子分治问题所以我们进行修改代码将第一步的key也就是图中的6保留keyi-1就是左边的数组个数keyi1就是右边的数组个数我们进行递归返回条件就是只有一个节点时返回。
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi begin;int right end;int left begin1 ;while (left right){//左边找大while(left right a[left] a[keyi])//加入的原因是如果到相遇点时left还是小于kei他不会在相遇点停下并且再次交换就颠倒顺序了{left;}//右边找小while (left right a[right] a[keyi]){--right;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);keyi left;//左半 [begin , keyi-1] keyi [keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}
快速排序的优化
对以上代码进行测试我们会发现在处理有序数组时快速排序反而是最慢的排序
为什么有序的情况下快排会很吃亏呢 因为我们采取了固定选Key
理想状态下快排时间复杂度是O(N*logN)
所以我们采取三数取中法 可以避开所有最坏的情况越接近二分就越快
三数取中法是快速排序算法中一种改进的基准pivot选择方法。它的目的是减少快速排序在最坏情况下的时间复杂度这通常发生在选择的基准值是最小或最大元素时。通过选择一个更接近中间值的基准可以提高分区的均匀性从而使算法更加高效。
在传统的快速排序中基准通常被选择为数组的第一个元素、最后一个元素或随机一个元素这样在面对某些特定的数据集时比如已经排序或接近排序的数组可能会导致算法效率低下。
三数取中法是通过考虑数组的第一个元素、中间元素和最后一个元素然后选择这三个元素的中位数作为基准。这种方法在实践中通常能给出一个较好的基准从而使得分区更加平衡。 void QuickSort(int* a, int begin, int end)
{if (begin end)return;int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int keyi begin;int right end;int left begin ;while (left right){//右边找小while (left right a[right] a[keyi]){--right;}//左边找大while(left right a[left] a[keyi])//加入的原因是如果到相遇点时left还是小于kei他不会在相遇点停下并且再次交换就颠倒顺序了{left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);keyi left;//左半 [begin , keyi-1] keyi [keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
} begin 和 end 这两个变量通常表示正在处理的数组或子数组的开始和结束索引。在数组的第一次排序时begin 通常是 0数组的第一个元素的索引而 end 是数组的最后一个元素的索引。 计算中点 (begin end) / 2 这个表达式的目的是找到 begin 和 end 之间的中间索引。这是通过将 begin 和 end 的值相加然后除以 2 来实现的。由于这里使用的是整数除法所以即使 begin end 是奇数结果也会被自动向下取整到最接近的整数。 数组索引 在 C/C 中数组的索引是从 0 开始的。因此计算出的 midi 一定是一个有效的数组索引只要 begin 和 end 是有效的。这意味着 a[midi] 是数组中的一个实际元素。
总结来说int midi (begin end) / 2; 确保 midi 是位于 begin 和 end 之间的一个有效索引而 a[midi] 则是数组在这个索引位置的元素。这是一种常见的找到数组中间元素索引的方法。 结论Hoare版本快速排序的效率与优势
Hoare版本的快速排序算法是计算机科学中的一个经典例子它展示了高效算法设计的重要性。通过其独特的分区策略该算法能够快速、高效地处理各种大小的数据集。Hoare版本的快速排序在最佳情况下的时间复杂度为 O(n log n)并且即使在平均情况下也能维持这一高效表现。虽然它在最坏情况下的时间复杂度为 O(n^2)但通过智能选择枢轴点如使用三数取中法或随机选取可以大幅减少这一风险。
此外Hoare版本相较于其他变体如Lomuto分区方法通常需要更少的数据交换操作这使得它在处理大数据集时更为高效。然而它的实现相比一些其他版本更为复杂可能需要更细致的理解和调试。
总的来说Hoare版本的快速排序因其高效性和对大数据集友好的特性在算法领域和实际应用中仍然占有一席之地。它不仅是排序算法的一个优秀代表也是计算机算法设计和分析的一个经典案例。
