快速排序

递归实现

$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,现在我们要把它们从矮到高进行排序.思路如下:

1. 将最后一个骷髅作为基准骷髅,从第一个骷髅开始和它比较高矮,矮的放左边,高的放右边.
2. 这样第一轮排序后,已经保证了左边的都比右边矮,但是左边区间里并不是有序的,需要重复刚才的操作.右边同理.
3. 这样处理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;
    }
}

需要注意,快排并不是稳定排序, 每次排序后,值相同的元素不能确保先后顺序.