逐步改进快速排序方法详解
一、快速排序介绍
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。
算法思想:1.先从数组中取出一个数组作为枢轴,一般情况下选取数组的第一个或者最后一个元素作为枢轴,当然可以选取其他的,在后面的优化措施里面,我会慢慢介绍。
2.双向遍历,从左边选取一个比枢轴大的数,从右边选择一个比枢轴小的数,然后交换这两个数;
3.重复步骤2,直到在枢轴的左边都比枢轴小,枢轴右边的数都比枢轴大。
算法的时间复杂度:O(nlogn)
二、内容
示例数组:arr = {1,4,2,5,6,7,9,3};
我们选取第一个数作为枢轴。
下面,我们来看看第一趟遍历过程:
我们从左循环了3次找到了比枢大的数5,从右循环找到了比枢轴小的数3,接下来,我们要交换这两个数:
至此,第一趟遍历结束,但是这并没有达到要求。我们来看看第二趟遍历的结果:
交换:
由于,上述已经满足了条件,因此不必进行再次交换。
直到最后一趟,我们枢轴归位:
代码实现:
int qsort(int *a,int left,int right){ if (right <= left) return -1; int pivot = a[right]; int i = left; int j = right - 1; //从前向后扫描,不需要判断是否会出现越界问题 while(true){ while(a[i++] < pivot); //从后向前扫描,要防止越界 while(a[j] > pivot && j >= left){ j--; } if (i < j) swap(a[i++],a[j--]); else{ break; } } swap(a[i],pivot); // 最后一趟是将a[i]与pivot交换 qsort(a,left,i -1); qsort(a,i+1,right); return 0; }
三、优化
我们都知道,快速排序的效率高低主要在于枢轴的选取,无论选取首个元素还是最后一个元素作为枢轴,我们都要对数组进一次遍历。因此,要想优化快排,还得从枢轴的选取下手。
1.随机选取法
引入原因:在待排序列是部分有序时,固定选取枢轴使快排效率底下,要缓解这种情况,就引入了随机选取枢轴
思路:使用随机数生成函数生成一个随机数rand,随机数的范围为[left, right],并用此随机数为下标对应的元素a[rand]作为中轴,并与最后一个元素a[right]交换,然后进行
与选取最后一个元素作为中轴的快排一样的算法即可。
优点:这是一种相对安全的策略。由于枢轴的位置是随机的,那么产生的分割也不会总是会出现劣质的分割。在整个数组数字全相等时,仍然是最坏情况,时间复杂度是O(n^2)。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。
代码实现:
int random(int left,int right){ return rand() % (right - left + 1) + left; } void Qsort(int *a,int left,int right){ if (left >= right) { return; } //随机选取一个元素作为枢轴,并与最后一个元素进行交换 int ic = random(left,right); swap(a[ic],a[right]); int midIndex = data[right]; int i = left; int j = right - 1; while(true){ //找大于枢轴的数据 while(a[i++] < midIndex); //找到小于枢轴的数据 while(a[j] > midIndex && j >= left){ j--; } //数据已经找到,准备交换 if (i < j) { swap(a[i++],a[j--]); } else{ break; } } swap(a[i],midIndex); //将枢轴放在正确的位置 Qsort(a,left,i -1); Qsort(a,i+1,right); }
2.三数取中(median-of-three)
引入的原因:虽然随机选取枢轴时,减少出现不好分割的几率,但是还是最坏情况下还是O(n^2),要缓解这种情况,就引入了三数取中选取枢轴
思路:假设数组被排序的范围为left和right,center=(left+right)/2,对a[left]、a[right]和a[center]进行适当排序,取中值为中轴,将最小者放a[left],最大者放在a[right],把中轴元与a[right-1]交换,并在分割阶段将i和j初始化为left+1和right-2。然后使用双向描述法,进行快排。
分割好处:
1.将三元素中最小者被分到a[left]、最大者分到a[right]是正确的,因为当快排一趟后,比中轴小的放到左边,而比中轴大的放到右边,这样就在分割的时候把它们分到了正确的位置,减少了一次比较和交换。
2.在前面所说的所有算法中,都有双向扫描时的越界问题,而使用这个分割策略则可以解决这个问题。因为i向右扫描时,必然会遇到不小于中轴的数a[right-1],而j在向左扫描时,必然会遇到不大于中轴的数a[left],这样,a[right-1]和a[left]提供了一个警戒标记,所以不需要检查下标越界的问题。
分析:最佳的划分是将待排序的序列分成等长的子序列,最佳的状态我们可以使用序列的中间的值,也就是第N/2个数。可是,这很难算出来,并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。事实上,随机性并没有多大的帮助,因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的不好情形,并且减少快排大约14%的比较次数
例子:
初始数组:6 1 8 9 4 3 5 2 7 0
选取三个中间数:6 1 8 9 4 3 5 2 7 0
对这三个数进行排序:0 1 8 9 4 3 5 2 7 6
最后中轴与a[right-1]交换:0 1 8 9 7 3 5 2 4 6
实例代码:
int Median(int *a,int left,int right){ int midIndex = (left + right)>>1; if (a[left] > a[midIndex]) { swap(a[left],a[midIndex]); } if (a[left] > a[right]) { swap(a[left],a[right]); } if (a[midIndex] > a[right]) { swap(a[midIndex],a[right]); } swap(a[midIndex],a[right-1]); return a[right-1]; //返回中轴 }
void qSort(int *a,int left,int right){ //如果需要排序的数据大于3个则使用快速排序 if (right - left >=3) { int midIndex = Median(a,left,right); int begin = left; int end = right - 1; while (true){ while(a[++begin] < midIndex); while(a[--end]<midIndex); if (begin < end) { swap(a[begin],a[end]); } else{ swap(a[begin],a[right -1]);//将枢轴移动到何时位置 break; } } qSort(a,left,begin -1); qSort(a,begin + 1,right); } else{ BubbleSort(a,left,right);//当数据小于3个,直接用冒泡排序 }//当要排序的数据很少时(小于3个),则不能进行三数取中值,此时直接使用简单的排序(例如冒泡)即可,而且从效率的角度来考虑这也是合理的,因为可以避免函数调用的开销。 }
四、进一步优化
上述三种快排,在处理重复数的时候,效率并没有很大提高,因此,我们可以想办法优化。
1.当待排序序列长度分割到一定大小后,使用插入排序。
原因:对于很小和部分有序的数组,快排不如插排好。当待排序序列的长度分割到一定大小后,继续分割的效率比插入排序要差,此时可以使用插排而不是快排
if (high - low + 1 < 10) { InsertSort(arr,low,high); return; }//else时,正常执行快排
2.在一次分割结束后,可以把与Key相等的元素聚在一起,继续下次分割时,不用再对与key相等元素分割(处理重复效率极高)
举例:
待排序序列 1 4 6 7 6 6 7 6 8 6
三数取中选取枢轴:下标为4的数6
转换后,待分割序列:6 4 6 7 1 6 7 6 8 6 枢轴key:6
本次划分后,未对与key元素相等处理的结果:1 4 6 6 7 6 7 6 8 6
下次的两个子序列为:1 4 6 和 7 6 7 6 8 6
本次划分后,对与key元素相等处理的结果:1 4 6 6 6 6 6 7 8 7
下次的两个子序列为:1 4 和 7 8 7
经过对比,我们可以看出,在一次划分后,把与key相等的元素聚在一起,能减少迭代次数,效率会提高不少
具体过程:在处理过程中,会有两个步骤
第一步,在划分过程中,把与key相等元素放入数组的两端
第二步,划分结束后,把与key相等的元素移到枢轴周围
举例:
待排序序列 1 4 6 7 6 6 7 6 8 6
三数取中选取枢轴:下标为4的数6
转换后,待分割序列:6 4 6 7 1 6 7 6 8 6 枢轴key:6
第一步,在划分过程中,把与key相等元素放入数组的两端
结果为:6 4 1 6(枢轴) 7 8 7 6 6 6
此时,与6相等的元素全放入在两端了
第二步,划分结束后,把与key相等的元素移到枢轴周围
结果为:1 4 66(枢轴) 6 6 6 7 8 7
此时,与6相等的元素全移到枢轴周围了
之后,在1 4 和 7 8 7两个子序列进行快排
代码示例:
void QSort(int arr[],int low,int high) //三数中值+聚集相等元素 { int first = low; int last = high; int left = low; int right = high; int leftLen = 0; int rightLen = 0; if (high - low + 1 < 10) { InsertSort(arr,low,high); return; } //一次分割 int key = SelectPivotMedianOfThree(arr,low,high);//使用三数取中法选择枢轴 while(low < high) { while(high > low && arr[high] >= key) { if (arr[high] == key)//处理相等元素 { swap(arr[right],arr[high]); right--; rightLen++; } high--; } arr[low] = arr[high]; while(high > low && arr[low] <= key) { if (arr[low] == key) { swap(arr[left],arr[low]); left++; leftLen++; } low++; } arr[high] = arr[low]; } arr[low] = key; //一次快排结束 //把与枢轴key相同的元素移到枢轴最终位置周围 int i = low - 1; int j = first; while(j < left && arr[i] != key) { swap(arr[i],arr[j]); i--; j++; } i = low + 1; j = last; while(j > right && arr[i] != key) { swap(arr[i],arr[j]); i++; j--; } QSort(arr,first,low - 1 - leftLen); QSort(arr,low + 1 + rightLen,last); }
原因:在数组中,如果有相等的元素,那么就可以减少不少冗余的划分。这点在重复数组中体现特别明显啊。
3.优化递归操作
快排函数在函数尾部有两次递归操作,我们可以对其使用尾递归优化
优点:如果待排序的序列划分极端不平衡,递归的深度将趋近于n,而栈的大小是很有限的,每次递归调用都会耗费一定的栈空间,函数的参数越多,每次递归耗费的空间也越多。优化后,可以缩减堆栈深度,由原来的O(n)缩减为O(logn),将会提高性能。
void QSort(int arr[],int low,int high) { int pivotPos = -1; if (high - low + 1 < 10) { InsertSort(arr,low,high); return; } while(low < high) { pivotPos = Partition(arr,low,high); QSort(arr,low,pivot-1); low = pivot + 1; } }
参考文献
http://blog.sina.com.cn/s/blog_5a3744350100jnec.html
http://www.blogjava.net/killme2008/archive/2010/09/08/331404.html
http://www.cnblogs.com/cj723/archive/2011/04/27/2029993.html
http://blog.****.net/zuiaituantuan/article/details/5978009
http://blog.****.net/ljianhui/article/details/16797431
推荐阅读
-
PHP 气泡、选择、插入和快速排序算法详解
-
[排序算法] VII.快速排序补充:三指针 + 随机数方法
-
纯干货分享 | 研发效能提升——敏捷需求篇-而敏捷需求是提升效能的方式中不可或缺的模块之一。 云智慧的敏捷教练——Iris Xu近期在公司做了一场分享,主题为「敏捷需求挖掘和组织方法,交付更高业务价值的产品」。Iris具有丰富的团队敏捷转型实施经验,完成了企业多个团队从传统模式到敏捷转型的落地和实施,积淀了很多的经验。 这次分享主要包含以下2个部分: 第一部分是用户影响地图 第二部分是事件驱动的业务分析Event driven business analysis(以下简称EDBA) 用户影响地图,是一种从业务目标到产品需求映射的需求挖掘和组织的方法。 在软件开发过程中可能会遇到一些问题,比如大家使用不同的业务语言、技术语言,造成角色间的沟通阻碍,还会导致一些问题,比如需求误解、需求传递错误等;这会直接导致产品的功能需求和要实现的业务目标不是映射关系。 但在交付期间,研发人员必须要将这些需求实现交付,他们实则并不清楚这些功能需求产生的原因是什么、要解决客户的哪些痛点。研发人员往往只是拿到了解决方案,需要把它实现,但没有和业务侧一起去思考解决方案是否正确,能否真正的帮助客户解决问题。而用户影响地图通常是能够连接业务目标和产品功能的一种手段。 我们在每次迭代里加入的假设,也就是功能需求。首先把它先实现,再逐步去验证我们每一个小目标是否已经实现,再看下一个目标要是什么。那影响地图就是在这个过程中帮我们不断地去梳理目标和功能之间的关系。 我们在软件开发中可能存在的一些问题 针对这些问题,我们如何避免?先简单介绍做敏捷转型的常规思路: 先做团队级的敏捷,首先把产品、开发、测试人员,还有一些更后端的人员比如交互运维的同学放在一起,组成一个特训团队做交付。这个团队要包含交付过程中所涉及的所有角色。 接着业务敏捷要打通整个业务环节和研发侧的一个交付。上图中可以看到在敏捷中需求是分层管理的,第一层是业务需求,在这个层级是以用户目标和业务目标作为输入进行规划,同时需要去考虑客户的诉求。业务人员通过获取到的业务需求,进一步的和团队一起将其分解为产品需求。所以业务需求其实是我们真正去发布和运营的单元,它可以被独立发布到我们的生产环境上。我们的产品需求其实就是产品的具体功能,它是我们集成和测试的对象,也就是我们最终去部署到系统上的一个基本单元。产品需求再到了我们的开发团队,映射到迭代计划会上要把它分解为相应的技术任务,包括我们平时所说的比如一些前端的开发、后端的开发、测试都是相应的技术任务。所以业务敏捷要达到的目标是需要去持续顺畅高质量的交付业务价值。 将这几个点串起来,形成金字塔结构。最上层我们会把业务目标放在整个金字塔的塔尖。这个业务目标是通过用户的目标以及北极星指标确立的。确认业务目标后再去梳理相应的业务流程,最后生产。另外产品需求包含了操作流程和业务规则,具需求交付时间、工程时间以及我们的一些质量标准的要求。 谈到用户影响的地图,在敏捷江湖上其实有一个传说,大家都有一个说法叫做敏捷需求的“任督二脉”。用户影响地图其实就是任脉,在黑客马拉松上用过的用户故事地图其实叫督脉。所以说用户影响地图是在用户故事地图之前,先帮我们去梳理出我们要做哪些东西。当我们真正识别出我们要实现的业务活动之后,用户故事地图才去梳理我们整个的业务工作流,以及每个工作流节点下所要包含的具体功能和用户故事。所以说用户影响地图需要解决的问题,我们包括以下这些: 首先是范围蔓延,我们在整张地图上,功能和对应的业务目标是要去有一个映射的。这就避免了一些在我们比如有很多干系人参与的会议上,那大家都有不同想法些立场,会提出很多需求(正确以及错误的需求)。这个时候我们会依据目标去看这些需求是否真的是会影响我们的目标。 这里提到的错误需求,比如是利益相关的人提出的、客户认为产品应该有的、某个产品经理需求分析师认为可以有的....但是这些功能在用户影响地图中匹配不到对应目标的话,就需要降低优先级或弃掉。另外,通常我们去制定解决方案的时候,会考虑较完美的实现,导致解决方案括很多的功能。这个时候关键目标至关重要,会帮助我们梳理筛选、确定优先级。 看一下用户影响到地图概貌 总共分为一个三层的结构: 第一层why,你的业务目标哪个是最重要的,为什么?涉及到的角色有哪些? 第二层how ,怎样产生影响?影响用户角色什么样的行为? (不需要去列出所有的影响,基于业务目标) 第三层what,最关键的是在梳理需求时不需一次把所有细节想全,这通常团队中经常遇到的问题。 我们用这个例子来看一下 这是一个客服中心的影响地图,业务目标是 3个月内不增加客服人数的前提下能支持1.5倍的用户数。此业务目标设定是符合 smart 原则的,specific非常的具体,miserable 是可以衡量的,action reoriented是面向活动的, real list 也是很实际的。 量化的目标会指引我们接下来的行动,梳理一个业务目标,尽量去量化,比如 :我们通过打造一条什么样的流水线,能够提高整个部署的效率,时间是原来的 1/2 。这样才是一个能量化的有意义的目标。 回到这幅图, how 层级识别出来的内容,客服角色:想要对它施加的影响,把客户引导到论坛上,帮助客户更容易的跟踪问题,更快速的去定位问题。初级用户:方论坛上找到问题。高级用户:在论坛上回答问题。通过我们这些用户角色,进行活动,完成在不增加客户客服人数的前提下支持更多的用户数量。 最后一个层级,才是我们日常接触比较多的真正的功能的特性和需求,比如引导到客户到论坛上,其实这个产品就需要有一个常见问题的论坛的链接。这个层次需要我们团队进一步地在交付,在每个迭代之前做进一步的梳理,细化成相应的用户故事。 这个是云智慧团队中,自己做的影响地图的范例,可以看下整个的层级结构。序号表示优先级。 那我们用户影响地图可以总结为:
-
斐波那契数列的时间复杂性详解与改进方法
-
快速排序技巧:掌握高效的序列排列方法
-
逐步改进快速排序方法详解
-
三种快速排序方法及其效率提升技巧
-
加速排序新技巧:双路快速排序方法详解
-
几种改进快速排序的方法
-
三大改进策略优化快速排序算法