快速排序和递归

首先介绍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)

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