首先介绍D&C递归

快速排序的思想是:分而治之(divide and conquer,D&C)一种递归式问题解决思路

这里先介绍D&C的工作原理

  1)找出简单的基线条件

  2)确定如何缩小问题的规模,使其符合基线条件。

看一个例子。

给定一个数组 {2 4 6},把这些数组相加返回一个结果,使用循环很容易完成。

但是如果使用递归函数来完成呢。

第一步:找出基线条件。最简单的数组是什么样呢?如果数组不包含任何元素或只包含一个元素,计算总和将非常容易。

    因此这就是基线条件。

第二部:每次递归都必须离空数组更进一步,缩小问题的规模。

    sum(2,4,6)=2+sum{4,6} 给函数sum传递的数组更短。换言之 这缩小了问题的规模。

函数sum的工作原理类似这样

  接受一个数组

    如果列表为空就返回0

    否则,计算表中除第一个数字意外其他数字的总和,将其与第一个数组相加,再返回结果。

sum(2,4,6)=2+sum{4,6}。sum{4,6}=4+sum(6), sum{6}=6+sum{0}. sum{0}是基线条件,返回0

    public static int calSum(int[] arr,int n){
        if(n>0){
            return arr[n-1]+calSum(arr,n-1);
        }else{
            return 0;
        }
    }

快速排序

使用快速排序对数组:{3,5,9,6,1}进行排序

基线条件为数组为空或只包含一个元素,在这种情况下,只需要原样返回数组——根本就不用排序。

使用D&C将数组进行分解,直到满足基线条件

下面介绍快速排序的工作原理:

1)首先从数组中选择一个元素,这个元素被称为基准值(pivot)

2)将数组分成两个子数组:小于基准值的元素和大于基准值的元素。

3)对两个子数组进行快速排序。

    static void sort(int[] arr,int left ,int right){
         int start = left;
         int end = right;
         int key = arr[left];//基准值
         while(end>start){
             /**从后往前比较*/
            while(end>start&&arr[end]>=key){//如果不小于基准值 则比较下一个(指针减一)
                end--;
            }
            if(arr[end]<key){//比基准值小的则和基准值交换位置
                int temp = arr[end];
                arr[end] = arr[start];
                arr[start] = temp;
            }
            /**从前往后比较*/
            while(end>start&&arr[start]<=key){
                start++;
            }
            if(arr[start]>key){
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }
            //第一次循环后:左边的值都比关键值小,右边的值都比关键值大
            //递归
            if(start>left) sort(arr,left,start-1);//左边序列。第一个索引位置到关键值索引-1
            if(end<right) sort(arr,end+1,right);//右边序列。从关键值索引+1到最后一个
        }
    }

快速排序的平均情况和最糟情况

快速排序的性能高度依赖于你选择的基准值。

假设你总将第一个元素用作基准值,且要处理的数组是有序的,由于快速排序算法不检查输入数组是否有序,因此它依然尝试对其进行排序。

比如数组{1,2,3,4,5,6,7,8}进行快速排序,

如果选择1作为基准值

  结果是数组没有被分成两半,其中一个子数组始终为空,这导致调用栈非常长(栈长为O(n))。整个算法所需要的时间O(n)*O(n)=O(n2)

如果总是将中间的元素作为基准值,

  数组被一份为二,调用栈会短很多(栈长为O(log n))。整个算法所需要的时间为O(n)*O(logn)=O(nlogn)

总结:快速排序的时候 基准值尽可能的选取中间(大小)值

03-01 05:36