快速排序算法_快速排序算法

快速排序的思想是分治法：

    分治法可以通俗的理解为：一代国君，把土地划分几大区域分发给诸侯管理，诸侯又把土地划分为几大小区域给各个地方首领管理，这就是分。而治，也就是合，就是国君只需要管理诸侯，诸侯管理地方首领，汇总到国君那就行了

  分治法的精髓：

分：将问题分解为规模更小的子问题；

治：将这些规模更小的子问题逐个击破；

合：将已解决的子问题合并，最终得出“母”问题的解；

快速排序的使用场景是：

   数据量大而杂乱的排序，避免出现最坏的情况。

快速排序的时间复杂度与空间复杂度：

  最优的情况：当数据随机分布时，以第一个关键字为基准分为两个子序列，两个子序列的元素个数接近相等，此时执行效率最好。

  最坏情况：当数据有序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差。

  时间复杂度：最差：O(N*N)   最好：O(N*lgN)  平均：O(Nlog2N)

  空间复杂度：在每次分割的过程中，需要 1 个空间存储基准值。而快速排序的大概需要 Nlog2N次的分割处理，所以占用空间也是 Nlog2N 个。

快速排序算法分析：

  快速排序算法实质是交换排序，它的思想是通过一趟排序将要排序的数据分割为独立的两部分，分割点左边是比它小的，右边是比它大的，再按照这个方法对两部分数据分别快速排序，这个过程可以通过递归进行，从而使得数据变得有序。

  快速排序算法-递归法：

方法一：挖坑法

  1.定义两个指针,left指向起始位置，right指向最后一个元素的位置,然后指定一个基数base(right),作为坑

  2.left寻找比基数(base)大的数字，找到后将left的数据赋给right，left成为一个坑，然后right寻找比基数(base)小的数字，找到将right的数据赋给left，right成为一个新坑，循环这个过程，直到left指针与right指针相遇，然后将base返回给那个坑(最终：base的左边都是比base小的数，base的右边都是比base大的数)，然后进行递归操作。

  如下图分析：

代码部分：

public int division(int[] list, int left, int right) {    // 以最左边的数(left)为基准    int base = list[left];    while (left < right) {        // 从序列右端开始，向左遍历，直到找到小于base的数        while (left < right && list[right] >= base)            right--;        // 找到了比base小的元素，将这个元素放到最左边的位置        list[left] = list[right];                // 从序列左端开始，向右遍历，直到找到大于base的数        while (left < right && list[left] <= base)            left++;        // 找到了比base大的元素，将这个元素放到最右边的位置        list[right] = list[left];    }     // 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；    // 而left位置的右侧数值应该都比left大。    list[left] = base;    return left;} private void quickSort(int[] list, int left, int right) {     // 左下标一定小于右下标，否则就越界了    if (left < right) {        // 对数组进行分割，取出下次分割的基准标号        int base = division(list, left, right);         System.out.format("base = %d:t", list[base]);        printPart(list, left, right);         // 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序        quickSort(list, left, base - 1);         // 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序        quickSort(list, base + 1, right);    }}

方法二：三数取中法

(图引自https://www.cnblogs.com/zwb2jcy/p/8920353.html)

  在有序或者接近有序的时候上面的方法效率会非常低，我们可以用 三数取中法解决。  

  在待排序序列的第一个元素，中间元素和最后一个元素中取大小位于中间的那个元素。每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。

如下图分析：

代码如下：

package sortdemo;import java.util.Arrays;/** * Created by chengxiao on 2016/12/14. * 快速排序 */public class QuickSort {    public static void main(String[] args) {        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};        quickSort(arr, 0, arr.length - 1);        System.out.println("排序结果：" + Arrays.toString(arr));    }    /**     * @param arr     * @param left  左指针     * @param right 右指针     */    public static void quickSort(int[] arr, int left, int right) {        if (left < right) {            //获取枢纽值，并将其放在当前待处理序列末尾            dealPivot(arr, left, right);            //枢纽值被放在序列末尾            int pivot = right - 1;            //左指针            int i = left;            //右指针            int j = right - 1;            while (true) {                while (arr[++i] < arr[pivot]) {                }                while (j > left && arr[--j] > arr[pivot]) {                }                if (i < j) {                    swap(arr, i, j);                } else {                    break;                }            }            if (i < right) {                swap(arr, i, right - 1);            }            quickSort(arr, left, i - 1);            quickSort(arr, i + 1, right);        }    }    /**     * 处理枢纽值     *     * @param arr     * @param left     * @param right     */    public static void dealPivot(int[] arr, int left, int right) {        int mid = (left + right) / 2;        if (arr[left] > arr[mid]) {            swap(arr, left, mid);        }        if (arr[left] > arr[right]) {            swap(arr, left, right);        }        if (arr[right] < arr[mid]) {            swap(arr, right, mid);        }        swap(arr, right - 1, mid);    }    /**     * 交换元素通用处理     *     * @param arr     * @param a     * @param b     */    private static void swap(int[] arr, int a, int b) {        int temp = arr[a];        arr[a] = arr[b];        arr[b] = temp;    }}

  快速排序算法-非递归法：       

利用栈保存左右区间 

1. 左右区间入栈(先右后左) 

2. 取栈顶元素，出栈 

3. 排序 

4. 入栈，先右后左(直到栈为空，停止循环)

//使用LinkedHashMappublic void quickSort1(int s[],int left,int right){        LinkedHashMap<Integer,Integer> lhp=new LinkedHashMap<>();        //将0,n放入LinkedHashMap        lhp.put(left,right);        while(!lhp.isEmpty()){                  //只要有需要排序的段            //读取left，right            Iterator<Map.Entry<Integer,Integer>> it=lhp.entrySet().iterator();            left=it.next().getKey();            right=lhp.get(left);            //并从LinkedHashMap中删除            lhp.remove(left,right);            if(left>=right)continue;            int i=left,j=right,temp=s[right];            while(i//遍历排序一遍                while(s[i]<=temp&&i                if(i                while(s[j]>=temp&&i                if(i            }            s[i]=temp;            lhp.put(left,i-1);            lhp.put(i+1,right);        }    }