常用的排序算法(一) - 快速排序(PHP实现)
假设当前需要从小到大进行排序,快速排序的核心思路是,从当前数组中,找到一个元素作为基准比较值(key),分别从两个方向进行比较。从后往前找,比key小元素放在数组前面,然后从前往后找,比key大的元素放在数组后面。最终两个方向交汇到中间,让key交换到数组的中间位置。
举例说明:
首先,常见的取key方式是,取当前排序数组范围的最左边第一位。(取最右边末尾也可以,但是操作顺序需要调成对称相反的模式)
假设当前需要排序的数组如下:
[ 34,5,5,555,5,4,14,5,88,89,54 ]
那么,可以先取34作为一个基准的比较值(key),也就是 key=34
因为我们的key是从前边取的,所以先要从后边(右边)开始往前找数字。
(如果是key从末尾取54,那么就需要先从前边开始往后找数字)
令left
为第一位为0,令right
为最末位数组长度ñ。
那么,key是从前边取,就我们先从需要right
开始,从后往前走。
如果a[right]>=key(即34)
,说明是正常的,因为大数字就应该放后面。
因此,right
继续往前走,也就是right--
。
直到出现a[right]<key
,这就说明有一个小数字出现在了后面,至于它是不是真的属于后面?这个还暂时不知道,所以先停停来,这时候的right
就标记了这个位置。
继续,不要忘记,快速排序的核心思路是,从当前数组中,找到一个元素作为基准比较值(key),分别从两个方向进行比较。从后往前找,比key小元素放在数组前面。然后从前往后找,比key大的元素放在数组后面。最终两个方向交汇到中间,让key交换到数组的中间位置。
从后往前找小数,已经找到了一个位置了,那么就换一个方向,从前往后找大数。
从因此left
开始,从前往后走。
如果a[left]<=key(即34)
,说明是正常的,因为小数字就应该放前面。
因此,left
继续往后走,也就是left++
。
(这里可以看出,left
状语从句:right
的操作的英文对称的)
直到出现a[left]>key
,这就说明有一个大数字出现在了前面,至于它是不是真的属于前面?这个就需要判断left
和right
的关系。
如果 left < right
,数组说明的中间位置还夹数在left和right
之间,因此left
标记的位置属于前面,right
标记的位置属于后面。
此时,一个大数字出现在了前面,一个小数字出现在了后面,因此我们直接将其互换,将ar[left]
和ar[right]
互换。
互换完之后,当前位标记left
和right
继续两边往中间走。同理,先从right
继续从后往前走,直到遇见一个小数字(比key小)。然后换方向从left
继续从前往后走,直到遇见一个大数字(比key大)
如果不满足left < right
,而是left = right
,说明以及抵达了数值的中心,这时候我们需要做的是把钥匙换到这个中间的地方,这就完成了一轮的快速排序。
完成了这一轮的快速排序之后,就会发现,这个数组可以拆分成左半部分和右半部分。
左半部分是从第一位
到left-1
(此时离在中心标记位),里面的数字都比中心的key
小。
右半部分是从left+1
到最末位
,里面的数字都比中心的key
大。
因此,我们就可以继续递归地对左半部分和右半部分使用快速排序即可。
直到最终,,开始的left >= 开始right
说明已经是拆成1个数字了,就没必要再比下去了。
排序的结果就完成了。
整个流程如图所示:
PHP代码运行如图:
PHP版本的实现代码如下
<?php<?php/**
* Created by PhpStorm.
* User: L
* Date: 2018-9-27
* Time: 16:45
*/$ar = [34, 5, 5, 555, 5, 4, 14, 5, 88, 89, 54];print_r(json_encode($ar));quick($ar);print_r(json_encode($ar));/** 快速排序 找基准数 左右分组交换至左小右大
* @param array $ar
* @param int $left
* @param null $right
*/function quick(array & $ar, $left = 0, $right = null){
//default left = 0 ,right = len-1
if ($right === null) {
$right = sizeof($ar) - 1;
}
if ($left >= $right) {//not need to sort
return;
}
//mark the default value
$first_index = $left;
$last_index = $right;
$key = $ar[$left];//default key as first element
while ($left != $right) {//find 2 swap element to sort into 2 parts
while ($ar[$right] >= $key && $left < $right) { // [l--r] is [small--big]
$right--;
}//until a[r] < key
while ($ar[$left] <= $key && $left < $right) {
$left++;
}//until a[l] > key
if ($left < $right) { //swap
echo "<br/> swap ar[$left] = $ar[$left] <-->ar[$right] = $ar[$right] <br/>";
$t = $ar[$left];
$ar[$left] = $ar[$right];
$ar[$right] = $t;
}
}//finish 2 sorted parts
//left == right == mid
if ($first_index != $left) {//first_index == mid_index not need to swap, just len = 1
echo "put key ar[$first_index] = $key <--> ar[$left] =$ar[$left] <br/>";
//put mid to first(location of key)
$ar[$first_index] = $ar[$left];
//put key into mid
$ar [$left] = $key;
}
print_r(json_encode($ar));
//continue cut and sort
//left == right == mid
echo " <br/> cut into: $first_index ---- | $left |---- $last_index <br/>";
quick($ar, $first_index, $left - 1);
quick($ar, $left + 1, $last_index);}
作者:Petrick
链接:http://www.imooc.com/article/247285
来源:慕课网
推荐阅读: