快排

快排可以說是在排序中的地位重中之重，不僅在七大排序中速度快，而且也是面試官經常考的排序，也是資料結構中必須掌握的排序

🍕🍔🍟快速排序：

快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序，它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)，

🚗🚓🚕基本思想：

1、從待排序區間選擇一個數作為基準值；

2、遍歷這個待排序區間，比基準值小的放基準值得左邊，比基準值大的放在右邊；

3、采用分治思想，當left和right相遇的時候，就可以分為左右兩個區間，

4、按照第2點同樣的方式進行遍歷，遞回，直到各小區間長度==1，代表有序，長度是0，代表沒有資料，

做題常見選基準值方法有：

• 挖坑法；

• Hoare 法；

下面找基準的方法是對快排的優化：

• 隨機選擇；

• 三數取中；

• 直接插入排序

一、挖坑法

???思路：

最開始設start為基準值，放在tmp中，然后比較大小，比基準值小的放基準值得左邊，比基準值大的放在右邊，如果end比tmp大就–，直到找到比tmp小的值交換，start同理，比tmp小小就++，直到找到比tmp大的值交換，

🍳🧇🥞代碼：

public static int partition(int[] array,int start,int end) {
        int tmp=array[start];
        while(start<end) {
            //start<end 防止有序陣列的時候end超過start  例如：1 2 3 4 5 6
            while(start<end && array[end]>=tmp) {//必須取等號，不然會無限回圈
                end--;
            }
            array[start]=array[end];
            while (start<end && array[start]<=tmp) {
                start++;
            }
            array[end]=array[start];
        }
    //最后start和end相遇，使陣列一分為二，完成分治思想
        array[start]=tmp;
        return start;
    }

注意，一定要加上“=”不然會死回圈

🍖🍗🥩完整代碼：

public static int partition(int[] array,int start,int end) {
        int tmp=array[start];
        while(start<end) {
            while(start<end && array[end]>=tmp) {
                end--;
            }
            array[start]=array[end];
            while (start<end && array[start]<=tmp) {
                start++;
            }
            array[end]=array[start];
        }
        array[start]=tmp;
        return start;
    }

    //待排序區間
    public static void quick(int[] array,int left,int right) {
        if(left>=right) {
            return;
        }
        int pivot=partition(array,left,right);
        //遞回 直到各小區間長度==1，代表有序，長度是0，代表沒有資料，
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    public static void quickSo(int[] array) {
        quick(array,0,array.length-1);
    }

1.1 性能

時間復雜度：O(n*logn)

空間復雜度：O(logn)

穩定些：不穩定

二、Hoare法：

Hoare法思想其實跟挖坑法沒有什么區別，都很好理解，

🍘🍙🍚思路：

最開始設start為基準值，放在tmp中，然后比較大小,同時找到last比基準值小的，begin比基準值大，他兩進行交換，最后begin和last相遇的值再跟start進行交換，

🧚?♀?🧚?♂?🤹?♀?核心代碼：

 public static int parentition2(int[] array,int start,int end) {
        int begin=start;
        int last=end;
        int tmp=array[start];
        while (begin<last) {
            while (begin<last && array[last]>=tmp) {
                last--;
            }
            while (begin<last && array[begin]<=tmp) {
                begin++;
            }
            swap(array,begin,last);
        }
        swap(array,begin,start);
        return begin;
    }

一般情況下，做題通常用的是挖坑法，例如選擇題；

那么當資料有序的情況下，快速排序的時間復雜度會變成O(n^2),空間復雜度O(n)，這也是最壞的情況下，所以引出了快速排序的優化，

三、三數取中法

快速排序的思想就是分而治制，在有序的資料中如果每次將待排序的的序列均勻的分割，時間復雜度就會更快；

🦪🍣🍤三數取中思路：

取中就是這一組資料中找到中間值，使中間值作為基準，進行分治；

條件為array[mid] <= array[left] <= array[right]

🍰🎂🍪核心代碼：

public static void medianOfThree (int[] array,int left,int right) {
        int mid=(left+right)/2;
        if(array[mid]>array[left]) {
            int tmp=array[mid];
            array[mid]=array[left];
            array[left]=tmp;
        }
        if(array[left]>array[right]) {
            int tmp=array[left];
            array[left]=array[right];
            array[right]=tmp;

        }
        if(array[mid]>array[right]) {
            int tmp=array[mid];
            array[mid]=array[right];
            array[right]=tmp;
        }
    }

四、 隨機選擇

也是為了防止有序陣列，采用在待排序列中任意取里面的元素作為基準；

🍵🧉🍶核心代碼：

 public static void pivotRandow(int[] array,int left,int right) {
        //隨機選擇法
        Random random=new Random();
        int rand=random.nextInt(right-left)+left+1;
        int tmp=array[left];
        array[left]=array[rand];
        array[rand]=tmp;
    }

五、直接插入排序優化

一組資料越有序，那么直接插入排序是最快的，快排遞回到某一個區間的時候會逐漸有序，我們就可以采用直接插入排序來優化

public static void quick(int[] array,int left,int right) {
        if(left>=right) {
            return;
        }
        int pivot=parentition2(array,left,right);

        //執行到一個區間之后  進行直接插入排序會更快
        if((right - left + 1) <= 100) {
            insertSort(array,left,right);
            return;
        }
        medianOfThree(array,left,right);
        //遞回
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

六、非遞回快排

非遞回快排比遞回要麻煩點，分析的程序也要繁瑣一點，但是有了前面挖坑法，Hoare法的基礎也可以好理解；

🥂🥃🥤基本思路：

首先我們還是分治思想和前面的pivot一樣，然后我們需要一個堆疊，pivot是一個基準，就各自分為兩組待排序區間，在堆疊中放入開始和結束的下標，兩個一組彈出，再跟上一步操作一樣找基準點，相遇過后，又放入堆疊中，重復找基準點，直到完成排序

需邀注意的點：

壓堆疊的基準點左右兩點是否有兩個以上資料，所判斷的公式是：pivot<right-1,不滿足條件說明只有一個資料，就壓堆疊前面的兩個下標即可，左邊的待排區間也是一樣，基準的左邊判斷是否有兩個資料的公式是：pivot>start+1，

👨?🦲👩?🦲👩?🔬代碼：

public static void quickSort(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        int end = array.length-1;
        int pivot = partition(array,start,end);
        if(pivot > start+1) {//判斷左邊是否有兩個資料
            stack.push(start);
            stack.push(pivot-1);
        }
        if(pivot < end-1) {//判斷右邊是否有兩個資料
            stack.push(pivot+1);
            stack.push(end);
        }
        while (!stack.empty()) {
            end = stack.pop();
            start = stack.pop();
            pivot = partition(array,start,end);
            if(pivot > start+1) {
                stack.push(start);
                stack.push(pivot-1);
            }
            if(pivot < end-1) {
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }

以上就是快排最核心的點了，必須全掌握，若想看全代碼可以 點擊 Github ,

鐵汁們，覺得筆者寫的不錯的可以點個贊喲?🧡💛💚💙💜🤎🖤🤍💟，收藏關注唄，你們支持就是我寫博客最大的動力