鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c++ > >

“chaos”的算法--之快速排序

来源:互联网 作者:佚名 时间:2013-08-15 08:55
【声明:版权所有,欢迎转载。联系信箱:yiluohuanghun@gmail.com】今天下午在公司不是太忙,又总结了一个排序类算法,算是偷了点懒,主要还是快排。快速排序实

【 声明:版权所有,欢迎转载。  联系信箱:yiluohuanghun@gmail.com】

   今天下午在公司不是太忙,服务器空间,又总结了一个排序类算法,算是偷了点懒,主要还是快排。快速排序实际上是最常用的一种排序算法了,就像名字一样、速度快,效率高。快排是基于冒泡排序而来的。整体来说,在最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准左边的子区间为空(或右边的子区间为空),而划分所得的另一个非空的子区间中记录数目,仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n*n)在最好情况下,每次划分所取的基准都是当前无序区的"中值"记录,划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数:O(nlgn)尽管快速排序的最坏时间为O(n2),但就平均性能而言,它是基于关键字比较的内部排序算法中速度最快者,快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。


快排思想:

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。


(1) 分治法的基本思想

    分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。


(2)快速排序的基本思想

    设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:

①分解:

    在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],美国服务器,并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。

 注意:

    划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos]):

    R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys

                 其中low≤pivotpos≤high。

②求解:

    通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。

③组合:

    因为当"求解"步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,"组合"步骤无须做什么,可看作是空操作。

(该段摘自)

   或许这样说还不是太直观,那就用白话再说一遍吧。快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置。递归快速排序,将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置,排序完成。所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

举例说明一下吧,这个可能不是太好理解。假设要排序的序列为

2 2 4 9 3 6 7 1 5 首先用2当作基准,使用i j两个指针分别从两边进行扫描,把比2小的元素和比2大的元素分开。首先比较2和5,5比2大,j左移

2 2 4 9 3 6 7 1 5 比较2和1,1小于2,所以把1放在2的位置

2 1 4 9 3 6 7 1 5 比较2和4,4大于2,因此将4移动到后面

2 1 4 9 3 6 7 4 5 比较2和7,2和6,2和3,2和9,全部大于2,满足条件,因此不变

经过第一轮的快速排序,元素变为下面的样子

[1] 2 [4 9 3 6 7 5]之后,在把2左边的元素进行快排,由于只有一个元素,香港虚拟主机,因此快排结束。右边

进行快排,递归进行,最终生成最后的结果。

#include <stdio.h> #include <stdlib.h> void quickSort(int array[], int start, int end) { if(start < end) { int key = array[start]; int low = start; int high = end; while(low < high) { while((low < high) && key < array [high]) high--; array[low] = array[high]; while((low < high) && key > array [low]) low++; array[high] = array[low]; } array[low] = key; quickSort(array, start, low - 1); quickSort(array, low + 1, end); } } int main(int argc, char *argv[]) { int index = 0; int array[] = {2, 4, 9, 3, 6, 7, 1, 5}; quickSort(array, 0, 7); for(; index < 8; index++) { printf("%d\t", array[index]); } system("pause"); return 0; }



本文出自 “驿落黄昏” 博客,请务必保留此出处

网友评论
<