快速排序
如图显示该分区,它具有以下属性:S1=theArray[first....poivotIndex-1]分区的所有项都小于枢轴项p,而S2=theArray[pivotIndex+1 .....last]的所有项大于等于p。这个属性并未说明数组已经完成排序,但指出一个重要的事实:在正确排序数组后,虽然位置first到pivotIndex-1的元素的相对位置可能变化,但依然在first到pivotIndex-1范围内。同样,在正确排序数组后,虽然位置pivotIndex+1
到last的相对位置可能变化,但依然在pivotIndex+1 到last范围内。最终的有序数组中,枢轴项的位置保持不变。
分区列出作为递归解决方案组分的数组项之间的关系。围绕枢轴项p排列数组,将产生两个更小的排序问题:排序数组的左侧部分(S1),排序数组的右侧部分(S2)。枢轴项和数组项之间的关系指示:一旦解决了左侧和右侧的数组排序问题,就解决了原始排序问题。在递归调用前,分解数组,可以在正确的位置放置枢轴项,并确保:在排序更小的数组段后,他们的元素将与数组其余部分简历适当的关系。另外,快速排序最后将终止:左侧和右侧的排序问题是更小的数组排序问题,实际上,因为枢轴项不属于S1和S2,所以与原始排序问题相比,左侧与右侧的排序问题跟接近基例;基例是包含一个元素的数组。
这个问题的难点之所在围绕枢轴项划分数组部分。因此,设计一个划分函数是很必要的。
划分函数的参数为数组段theArray[first....last]。该函数必须将数组段的元素分为两个区域:小于枢轴项的元素集合S1,大于等于枢轴项的元素集合S2。如下图所示。应使用哪个枢轴项?若数组元素的随机排列,则可随机地选择枢轴项。
例如,可将theArray[first]选作枢轴项。在开发分区时,不管选择哪个枢轴项,将枢轴项放在theArray[first]的位置会更方便。准备放到S1和S2区域的元素全部都在数组的另一区域,称为未知区域。数组索引first、lastS1、firstUnknow 和 last 按上述划分数组。枢轴项和未知区域(theArray[firstUnknow...last])元素的关系同样未知!
在整个分区过程中,下面的描述一定为真:
区域S1的元素都小于枢轴项,而区域S2的元素都大于等于枢轴项。
上述语句是划分算法的不变式。为是不变式在划分算法开始时为真,必须将数组索引初始化为以下形式,使未知区域涵盖除枢轴项之外的要分区的所有数组段。
lastS1=first
firstUnknown=first+1;
划分算法的每个步骤分析未知区域的一项,确定它属于S1还是属于S2,并将其放入适当的位置。这样,未知区域的大小每次减1,当未知区域的大小为0时,即firstunknow>last时算法终止。
分享到:
相关推荐
python编写 快速排序 Quick Sort
基于python的排序算法-快速排序Quick Sort
python 一行代码实现的快速排序 quick sort
php /** * 快速排序 quick sort * **/ function sort_quick($arrData) { if(empty($arrData) || !is_array($arrData)) return false; $flag = $arrData[0]; $len = count($arrData) – 1; if($len == 0) return $...
快速排序(Quick Sort)
经典排序算法 - 快速排序Quick sort 经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - ...
数据结构,排序算法,快速排序算法的C语言实现, quick sort C qsort.c an c implementation of quick sort
快速排序(Quick Sort)源码及运行示例
快速排序(Quick Sort)作者原版论文,快速排序的作者C.A.R Hoare 发表的原著论文。
@沧海。Tags:快速排序。
c++快排(快速排序)的源代码。代码简洁明了。让您知道理解快排。 用一个函数解决快排问题。 请您赶快来下载吧!
C#,双向链表(Doubly Linked List)快速排序(Quick Sort)算法与源代码。双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始...
鉴于初学C语言或C++时对快速排序算法的了解不够深入,在此上传快速排序的C语言实现代码,该实现代码具有模块化特点,并且在代码中写了注释,并在调试过程中易出错的关键地方做了标注;此外,在代码实现中添加了良好...
在B站讲快速排序的笔记,需要的同学可以免费下载
快速排序 Quick Sort 的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。
各种数据结构、算法及实用的C#源代码.C#,单向链表(Simply Linked List)快速排序(Quick Sort)算法与源代码.单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部...
快速排序(quick sort)C++源代码
c#实现快速排序quick_sort函数