首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

排序算法拾掇之快速排序

2012-07-30 
排序算法整理之快速排序它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有

排序算法整理之快速排序

它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

 排序算法拾掇之快速排序

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。

 

步骤为:

1.        从数列中挑出一个元素,称为 "基准"(pivot),

2.        重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割结束之后,该基准就处于数列的中间位置。这个称为分割(partition)操作。

3.        递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

 

如图:

排序算法拾掇之快速排序

left指针,right指针,base参照数。

第一步:首先我们从数组的left位置取出该数(20)作为基准(base)参照物。

第二步:从数组的right位置向前找,一直找到比(base)小的数,

如果找到,将此数赋给left位置(也就是将10赋给20),

此时数组为:10,40,50,10,60,

left和right指针分别为前后的10。

第三步:从数组的left位置向后找,一直找到比(base)大的数,

如果找到,将此数赋给right的位置(也就是40赋给10),

此时数组为:10,40,50,40,60,

left和right指针分别为前后的40。

第四步:重复“第二,第三“步骤,直到left和right指针重合,

最后将(base)插入到40的位置,

此时数组值为: 10,20,50,40,60,至此完成一次排序。

第五步:此时20已经潜入到数组的内部,20的左侧一组数都比20小,20的右侧作为一组数都比20大,

以20为切入点对左右两边数按照"第一,第二,第三,第四"步骤进行,最终快排大功告成。

实现代码:


 

运行结果:

排序前:[2, 5, 1, 8, 9, 3]

排序后:[1, 2, 3, 5, 8, 9]

热点排行