递归实现
$arr = [2,3,4,9,1,20,12,12,1,2];
function quickSort($arr){
if(count($arr)<=1){
return $arr;
}
$left_array= $right_array = [];
$rand = (rand(0,count($arr)-1));//随机索引
$pos = $arr[$rand ];//需要做比较的值
unset($arr[$rand]);//将该值从原数组去掉
foreach($arr as $k => $v){
if($v<$pos){
$left_array[] = $v;
}else{
$right_array[] = $v;
}
}
$left_array = quickSort($left_array);
$right_array = quickSort($right_array);
//合并
return array_merge($left_array, array($pos), $right_array);
}
echo '<pre/>';
print_r(quickSort($arr));
时间复杂度是nlogn.
上面的例子有个问题 $left_array 和 $right_array都需要开启额外的空间来存储排序后的数据,所以这种方式的快排并不是原地排序.
问题来了,那什么是原地排序呢?
原地排序就是除了数据本身存储的空间外,并不需要其他空间.
像上面的例子,就是不需要$left_array和$right_array来存储排序后的数据.
这样子,编程的复杂度就提高了,那要怎么操作呢?
这里我用java代码来说明快排的原地排序,并花时间画了几幅图来帮助理解.
上面的图中有7个骷髅,最高的210cm,最矮的140cm,现在我们要把它们从矮到高进行排序.思路如下:
- 将最后一个骷髅作为基准骷髅,从第一个骷髅开始和它比较高矮,矮的放左边,高的放右边.
- 这样第一轮排序后,已经保证了左边的都比右边矮,但是左边区间里并不是有序的,需要重复刚才的操作.右边同理.
- 这样处理n次后,才能保证排序完成.
那怎么用原地排序的方式来操作呢?
关键就是利用额外的标识变量.这里我用标识变量i当做已经比较高矮后的骷髅下标的下一个骷髅,这里可能有点绕,就是说{}区域内的骷髅是A[0]A[i-1]的元素,当i=0的时候,不存在A[0]A[-1]的区间,所以就是空的.
i=1的时候,A[0]~A[0]即第一个元素是已经排序好后的骷髅.
i=2的时候,A[0]~A[1]即前面两个元素是已经排序好后的骷髅.
标识j当做未比较的骷髅下标.
刚开始,没比较之前,左边{}区域放的就是比基准骷髅矮的骷髅.在这里,基准骷髅是175cm,所以{}标识的区域应该放的都是<=175cm的骷髅.
第一次拿j=0的骷髅和pivot比较,发现210>175,比pivot高,不需要将它移动到{}里,那么i不变,j++.
第二次拿j=1的骷髅和pivot比较,发现150<=175,比pivot矮,要将它移动到{}里,怎么移呢,将150和210交换位置.这时候,{}里已经有1个元素了,i++,j++.
第三次拿j=2的骷髅和pivot比较,发现170<=175,比pivot矮,要将它移动到{}里,将170和210交换位置,这时候{}里已经有2个元素,i++,j++.
第四次比较
第五次比较
第六次比较
最后
这样子,就保证了{}里的都是比175矮的骷髅,高的都在右边.
接下来就是要对{}的数据和右边的数据再次执行相同的逻辑就可以实现全局排序了.
看看代码怎么写
package cn.test;
import java.util.Arrays;
/**
* @author Administrator
*/
public class QuickSort {
public static void main(String[] args) {
int[] data = {210, 150, 170, 175, 140, 190, 175};
quickSort(data, 0, data.length - 1);
System.out.println(Arrays.toString(data));
}
private static void quickSort(int[] data, int p, int r) {
if (p >= r) {
return;
}
//找到基准元素
int q = partition(data, p, r);
quickSort(data, p, q - 1);
quickSort(data, q + 1, r);
}
private static int partition(int[] data, int p, int r) {
int i = p;
int j = p;
int pivot = data[r];
while (j < r) {
if (data[j] <= pivot) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
i++;
}
j++;
}
int tmp = data[i];
data[r] = tmp;
data[i] = pivot;
return i;
}
}
需要注意,快排并不是稳定排序, 每次排序后,值相同的元素不能确保先后顺序.
