PHP排序算法之快速排序排序算法之快速排序(Quick Sort)及其优化算法详解及其优化算法详解
本文实例讲述了PHP排序算法之快速排序(Quick Sort)及其优化算法。分享给大家供大家参考,具体如下:
基本思想:基本思想:
快速排序(Quicksort)是对冒泡排序的一种改进。他的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一
部分的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行快速排序,整个排序过程可以递归进行,以达
到整个序列有序的目的。
基本算法步骤:基本算法步骤:
举个栗子:
假如现在待排序记录是:
6 2 7 3 8 9
第一步、创建变量 $low 指向记录中的第一个记录,$high 指向最后一个记录,$pivot 作为枢轴赋值为待排序记录的第一个元
素(不一定是第一个),这里:
$low = 0;
$high = 5;
$pivot = 6;
第二步、我们要把所有比 $pivot 小的数移动到 $pivot 的左面,所以我们可以开始寻找比6小的数,从 $high 开始,从右往左
找,不断递减变量 $high 的值,我们找到第一个下标 3 的数据比 6 小,于是把数据 3 移到下标 0 的位置($low 指向的位
置),把下标 0 的数据 6 移到下标 3,完成第一次比较:
3 2 7 6 8 9
//这时候,$high 减小为 3
$low = 0;
$high = 3;
$pivot = 6;
第三步、我们开始第二次比较,这次要变成找比 $pivot 大的了,而且要从前往后找了。递加变量 $low,发现下标 2 的数据是
第一个比 $pivot 大的,于是用下标 2 ($low 指向的位置)的数据 7 和 指向的下标 3 ($high 指向的位置)的数据的 6 做交
换,数据状态变成下表:
3 2 6 7 8 9
//这时候,$high 减小为 3
$low = 2;
$high = 3;
$pivot = 6;
完成第二步和第三步我们称为完成一个循环。
第四步(也就是开启下一个循环)、模仿第二步的过程执行。
第五步、模仿第三步的过程执行。
执行完第二个循环之后,数据状态如下:
3 2 6 7 8 9
//这时候,$high 减小为 3
$low = 2;
$high = 2;
$pivot = 6;
到了这一步,我们发现 $low 和 $high“碰头”了:他们都指向了下标 2。于是,第一遍比较结束。得到结果如下,凡是
$pivot(=6) 左边的数都比它小,凡是 $pivot 右边的数都比它大。
然后,对 、$pivot 两边的数据 {3,2} 和 {7,8,9},再分组分别进行上述的过程,直到不能再分组为止。
注意:第一遍快速排序不会直接得到最终结果,只会把比k大和比k小的数分到k的两边。为了得到最后结果,需要再次对下标
2两边的数组分别执行此步骤,然后再分解数组,直到数组不能再分解为止(只有一个数据),才能得到正确结果。