排序算法整理之快速排序
它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序使用分治法(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]