快速排序、堆排序

快速排序

荷蘭國(guó)旗問題(Dutch National Flag Problem)

給定一個(gè)數(shù)組arr，和一個(gè)數(shù)num;
請(qǐng)把小于等于num的數(shù)放在數(shù)組的左邊，大于num的數(shù)放在數(shù)組的右邊。
要求額外空間復(fù)雜度O(1)，時(shí)間復(fù)雜度O(N)

思路：
給定一個(gè)無序數(shù)組[4,5,6,7,2,1,9,8]，num為5
使用一個(gè)變量p來劃分小于等于num的范圍，剛開始p=-1表示這個(gè)范圍不存在。


image.png

遍歷數(shù)組，當(dāng)出現(xiàn)小于等于num的數(shù)后，當(dāng)前遍歷到的數(shù)字與p的下一個(gè)數(shù)字發(fā)生交換，p加1


image.png

本示例中遍歷到數(shù)組的第一個(gè)數(shù)小于num，所以當(dāng)前數(shù)字和p的下一個(gè)位置的數(shù),即自己交換。后續(xù)過程省略，代碼如下： 
public class Patition {
    public static void patition(int []arr,int num){
        if(arr == null)
            return;

        int p = -1;
        for(int i = 0;i<arr.length;i++){
            if(arr[i]<=num)
                swap(arr,i,++p);
        }
        return ;
    }

    public static void swap(int []arr,int i,int j){
        if(arr == null || i == j)
            return;
        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }
}

問題的升級(jí)：(荷蘭國(guó)旗問題)Dutch National Flag Problem

給定一個(gè)整數(shù)數(shù)組，給定一個(gè)值K，這個(gè)值在原數(shù)組中一定存在;
要求把數(shù)組中小于K的元素放到數(shù)組的左邊，大于K的元素放到數(shù)組的右邊，等于K的元素放到數(shù)組的中間;
最終返回一個(gè)整數(shù)數(shù)組，其中只有兩個(gè)值，分別是等于K的數(shù)組部分的左右兩個(gè)下標(biāo)值。
例如:
給定數(shù)組：[2, 3, 1, 9, 7, 6, 1, 4, 5]，給定一個(gè)值4,
那么經(jīng)過處理原數(shù)組可能得一種情況是：[2, 3, 1, 1, 4, 9, 7, 6, 5].
需要注意的是，小于4的部分不需要有序，大于4的部分也不需要有序，返回等于4部分的左右兩個(gè)下標(biāo)，即[4, 4]

荷蘭國(guó)旗問題較上問題增加了對(duì)等于區(qū)域劃分的判斷，在算法的思路上，我們可以再使用一個(gè)變量來跟蹤大于num的區(qū)域：


image.png

num為5，當(dāng)遍歷到5時(shí)，p1與p2不發(fā)生變化，小于與大于區(qū)域不發(fā)生擴(kuò)張；遍歷到大于num的數(shù)時(shí)，當(dāng)前遍歷的數(shù)與p2前的數(shù)發(fā)生交換，p2減1，表示大于num的數(shù)擴(kuò)張了一個(gè)單位，并且遍歷的索引停止：


image.png

遍歷到了數(shù)組的arr[2]，發(fā)生交換后，繼續(xù)判斷arr[2]位置的數(shù)(8)與num的大小，直到當(dāng)前遍歷到的index與p2“相撞”后,停止。后續(xù)過程省略,代碼如下: 
public class DutchNationalFlag {

    public static int[] partition(int []arr,int L,int R,int num){
        if(arr == null)
            return null;

        int p1 = L - 1;
        int p2 = R + 1;
        int curIndex = L;
        while(curIndex < p2){
            if(arr[curIndex] < num){
               swap(arr,curIndex++,++p1);
            }else if(arr[curIndex] == num){
                curIndex++;
            }else{
                swap(arr,curIndex,--p2);
            }
        }
        return new int[]{++p1,--p2};
    }

    public static void swap(int[] arr,int i,int j){
        if(arr == null || i == j)
            return;

        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }
}

經(jīng)典快排與改進(jìn)

經(jīng)典快排

經(jīng)典快排的思路即：partition+recursion
partition選擇數(shù)組的最后一個(gè)數(shù)為參考值，將小于等于該數(shù)字的數(shù)羅列到左邊，該數(shù)字放在中間，大于這個(gè)數(shù)的數(shù)羅列到該數(shù)字的右邊，然后對(duì)該數(shù)字左邊的數(shù)和右邊的數(shù)進(jìn)行遞歸，完成排序。經(jīng)典快排以及測(cè)試代碼如下：

import java.util.Arrays;

public class ClassicQuickSort {

    public static void quickSort(int [] arr){
        sort(arr,0,arr.length-1);
    }

    public static void sort(int []arr,int L,int R){
        if(L < R){
            int mid = partition(arr,L,R);
            sort(arr,L,mid-1);
            sort(arr,mid+1,R);
        }
    }
    public static int partition(int []arr,int L,int R){
        int p = L-1;
        for(int i = L;i<R+1;i++){
            if(arr[i]<=arr[R])
                swap(arr,i,++p);
        }
        return p;
    }

    public static void swap(int []arr,int i,int j){
        if(arr == null || i == j)
            return;

        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }

    // test:comparator
    public static void comparator(int []arr){
        Arrays.sort(arr);
    }

    // test :printer
    public static void printArray(int[]arr){
        if(arr == null)
            return;

        for(int i = 0;i<arr.length;i++){
            System.out.print(arr[i]+ " ");
        }
        System.out.println();
    }
    // test: copier
    public static int[] copier(int []arr){
        if(arr == null)
            return null;

        int [] copyArr = new int[arr.length];
        for(int i = 0;i<arr.length;i++){
            copyArr[i] = arr[i];
        }

        return copyArr;
    }
    // test: generateRandomArray
    public static int[] generateRandomArray(int maxSize,int maxValue){
        int size = (int)((maxSize+1)*Math.random());
        int[] arr = new int[size];
        for(int i = 0;i<size;i++){
            // (-maxValue,maxValue)
            arr[i] = (int)((maxValue+1)*(Math.random()) - maxValue*Math.random());
        }
        return arr;
    }
    // test: isEqual
    public static boolean isEqual(int[] arr1, int[] arr2){
        if(arr1 != null&& arr2 == null || arr2 != null && arr1 == null)
            return false;
        if(arr1.length != arr2.length)
            return false;
        if(arr1 == null && arr2 == null)
            return true;

        for(int i = 0;i<arr1.length;i++){
            if(arr1[i] != arr2[i])
                return false;
        }

        return true;
    }

  public static void main(String[]args){
        int testTime = 5000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for(int i = 0;i<testTime;i++){
            int [] arr1 = generateRandomArray(maxSize,maxValue);
            int [] arr2 = copier(arr1);
            quickSort(arr1);
            comparator(arr2);
            if(!isEqual(arr1,arr2)){
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed?"Nice":"Wrong");
    }
}

改進(jìn)快排

經(jīng)典快排的問題是，每次只能排出一個(gè)數(shù)字，partition過程中是將num這個(gè)數(shù)字與小于等于區(qū)域和大于區(qū)域進(jìn)行劃分，如果有多個(gè)和num相等的數(shù)字，那么排序效率會(huì)變得十分低，由荷蘭國(guó)旗問題的思考總結(jié)，我們可以進(jìn)一步將快排進(jìn)行優(yōu)化改進(jìn)。將partition過程變?yōu)閷?shù)組劃分為小于區(qū)域，等于區(qū)域以及大于區(qū)域，然后對(duì)小于區(qū)域和大于區(qū)域再進(jìn)行partition的遞歸。代碼如下，省略測(cè)試代碼：

public class QuickSort {

    public static void quickSort(int[] arr){
        sort(arr,0,arr.length-1);
    }

    public static void sort(int[] arr,int L,int R){
        if(L < R){
            int [] indexArr = partition(arr,L,R);
            sort(arr,L,indexArr[0]-1);
            sort(arr,indexArr[1]+1,R);
        }
    }
    public static int[] partition(int[] arr,int L,int R){
        int p1 = L - 1;
        int p2 = R ;
        int curIndex = L;
        while(curIndex < p2){
            if(arr[curIndex] < arr[R]){
                swap(arr,curIndex++,++p1);
            }else if(arr[curIndex] > arr[R]){
                swap(arr,curIndex,--p2);
            }else{
                curIndex++;
            }
        }
        swap(arr,p2,R);
        return new int[]{++p1,--p2};
    }

    public static void swap(int[] arr,int i,int j){
        if(arr == null || i == j)
            return;

        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }
}

快排時(shí)間復(fù)雜度與額外空間復(fù)雜度分析

快排的時(shí)間復(fù)雜度與數(shù)據(jù)狀況有關(guān)，一個(gè)有序的數(shù)組[0,1,2,3,4,5,6,7],如果使用快排排序，那么狀況就是最差的。但是如果每次參考的基準(zhǔn)數(shù)都能把數(shù)組均分成兩部分那么我們就可以按照master公式來計(jì)算時(shí)間復(fù)雜度：T(N) = a*T(N/b) + O(N^d).快排分為兩個(gè)子過程遞歸，除去遞歸外partition的時(shí)間復(fù)雜度為O(N),所以其時(shí)間復(fù)雜度為O(N^d * logN)即：O(NlogN)。但是如何使基準(zhǔn)數(shù)能夠?qū)?shù)組均分成兩坨呢？為了解決這個(gè)問題，我們可以打亂當(dāng)前的數(shù)據(jù)狀況，sort部分的代碼改動(dòng)如下：

 public static void sort(int[] arr,int L,int R){
        if(L < R){
            swap(arr,L+(int)((R-L+1)*Math.random()),R);// 隨機(jī)讓任意位置的數(shù)與基準(zhǔn)數(shù)位置R的數(shù)調(diào)換
            int [] indexArr = partition(arr,L,R);
            sort(arr,L,indexArr[0]-1);
            sort(arr,indexArr[1]+1,R);
        }
    }

通過添加一句代碼，就可以讓未知狀況的數(shù)組取基準(zhǔn)數(shù)，轉(zhuǎn)換成一個(gè)概率問題，通過長(zhǎng)期數(shù)學(xué)期望最終計(jì)算得到隨即快速排序的時(shí)間復(fù)雜度為O(NlogN)。
隨機(jī)快速排序的額外空間復(fù)雜度為O(logN),原因在于，partition最后要返回一個(gè)數(shù)組來記錄與基準(zhǔn)數(shù)相等的區(qū)域索引范圍，這樣的額外數(shù)組量為一個(gè)二叉樹的高度即logN。

堆排序

最大堆與最小堆

滿二叉樹

什么是滿二叉樹？國(guó)內(nèi)定義如果一個(gè)二叉樹的層數(shù)為K,且節(jié)點(diǎn)的總數(shù)是2^K-1,那么這棵樹就是一個(gè)滿二叉樹，示例：


image.png

完全二叉樹

節(jié)點(diǎn)從左至右依次排布的樹就是完全二叉樹，示例：


image.png

堆

堆是一種完全二叉樹，分為最大堆(大根堆)和最小堆(小根堆)。當(dāng)父節(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最大堆，反之，當(dāng)父節(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最小堆。示例：


image.png

最大堆或最小堆的子樹仍然是最大堆或最小堆。

heapInsert與heapify

heapInsert 與 heapify是堆結(jié)構(gòu)中重要的兩個(gè)方法。

heapInsert

heapInsert顧名思義，是向堆中插入節(jié)點(diǎn)，插入節(jié)點(diǎn)后，要判斷該節(jié)點(diǎn)與其父節(jié)點(diǎn)的大小，如果大于父節(jié)點(diǎn)，那么則插入的節(jié)點(diǎn)與父節(jié)點(diǎn)交換位置，并繼續(xù)向上判斷，直到小于等于父節(jié)點(diǎn)為止。一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)的索引為(index-1)/2。

public static void heapInsert(int[] arr,int index){
        while(arr[index] > arr[(index-1)/2]){
            swap(arr,index,(index-1)/2);
            index = (index-1)/2;
        }
    }
public static void swap(int[] arr,int i,int j){
        if(arr == null || i == j)
            return;

        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }

heapify

heapify的作用舉例：

假設(shè)有一個(gè)流，它源源不斷向外吐出數(shù)字，這些數(shù)字是沒有規(guī)律的；
現(xiàn)在希望你設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)，可以快速地收集并獲取吐出所有數(shù)字的中位數(shù)

如果你用一個(gè)數(shù)組去接收流吐出的數(shù)字，那么收集流吐出的數(shù)字很簡(jiǎn)單，但是如果要獲取中位數(shù)的話就要對(duì)數(shù)組進(jìn)行一次排序，如果要求流每次吐出一個(gè)數(shù)字就獲取一次中位數(shù)，那么就要頻繁地對(duì)數(shù)組進(jìn)行排序操作。解決的方法就是使用堆結(jié)構(gòu)來解決這個(gè)問題：設(shè)計(jì)一個(gè)最大堆，和一個(gè)最小堆，每次流吐出數(shù)字的時(shí)候都和最大堆的堆頂作比較，如果小于等于最大堆堆頂就放入最大堆，如果大于最大堆的堆頂則放入最小堆，入堆這個(gè)操作就是heapInsert。同時(shí)我們還需要保證最大堆的數(shù)據(jù)量不能比最小堆中的數(shù)據(jù)量大超過1，反之亦是如此/也就是要保持最大堆數(shù)據(jù)量N和最小堆的數(shù)據(jù)量M的關(guān)系為 |N-M| <= 1,如何保持這種關(guān)系呢？一旦破壞了這種關(guān)系的平衡，我們就讓最大堆的頂部或者最小堆的頂部彈出，讓這個(gè)最大的數(shù)字進(jìn)入到最小堆里面，或者是讓最小堆的最小的數(shù)字insert到最大堆里面，如圖示意：


image.png

假設(shè)這個(gè)數(shù)據(jù)流吐出的數(shù)字依次是 5->6->4->7->3->8->1
左側(cè)為最大堆數(shù)字?jǐn)?shù)量為N，右側(cè)為最小堆數(shù)字?jǐn)?shù)量為M,沒有破壞過 |N-M| <= 1的規(guī)定，如果這個(gè)時(shí)候數(shù)據(jù)流吐出的數(shù)字為0，那么就要heapInsert到最大堆里面，這個(gè)時(shí)候N-M = 2破壞了兩堆數(shù)量上的平衡，所以要把最大堆的堆頂彈入到最小堆中去，操作如下：

首先將數(shù)字0 heapInsert到最大堆中


image.png

交換最大堆首尾數(shù)字


image.png

將最大堆末尾數(shù)字(5) heapInsert到最小堆
image.png

接下來就是heapify操作了，對(duì)最大堆中的堆頂0進(jìn)行heapify,首先要判斷它的兩個(gè)孩子誰更大，誰大跟誰交換，直到滿足最大堆的結(jié)構(gòu)為止


image.png

heapify的代碼如下： 
public static void heapify(int[] arr,int heapSize,int index){
        int leftIndex = 2*index+1;
        while(leftIndex < heapSize){
            int largestIndex = leftIndex+1<heapSize && arr[leftIndex]<arr[leftIndex+1]?leftIndex+1:leftIndex;
            largestIndex = arr[index]>arr[largestIndex]?index:largestIndex;
            if(largestIndex != index){
                swap(arr,index,largestIndex);
                index = largestIndex;
                leftIndex = largestIndex*2+1;
            }else {
                break;
            }
        }
    }

arr代表最大堆的數(shù)據(jù)，heapSize為最大堆數(shù)字的個(gè)數(shù)，index代表對(duì)哪個(gè)索引的數(shù)字進(jìn)行heapify

堆排序

堆排序的思路就是對(duì)數(shù)組中的每個(gè)數(shù)字進(jìn)行heapInsert操作，然后置換堆頂和堆末的數(shù)字，交換之后，最大的數(shù)字就排序好了，這時(shí)heapSize-1，然后對(duì)heapSize-1的這個(gè)堆的堆頂進(jìn)行heapify,heapify操作后，這個(gè)heapSize-1的堆再次變?yōu)樽畲蠖眩缓笤僦脫Q堆頂和堆末的數(shù)字，排出最大數(shù)字......代碼如下：

public class HeapSort {

    public static void heapSort(int[] arr){
        // 形成最大堆
        for(int i = 0;i<arr.length;i++){
            heapInsert(arr,i);
        }

        int heapSize = arr.length;
        
        while(heapSize > 0){
            swap(arr,0,heapSize-1);
            heapSize--;
            heapify(arr,heapSize,0);
        }

    }

    public static void swap(int[] arr,int i,int j){
        if(arr == null || i == j)
            return;

        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }

    public static void heapInsert(int[] arr,int index){
        while(arr[index] > arr[(index-1)/2]){
            swap(arr,index,(index-1)/2);
            index = (index-1)/2;
        }
    }

    public static void heapify(int[] arr,int heapSize,int index){
        int leftIndex = 2*index+1;
        while(leftIndex < heapSize){
            int largestIndex = leftIndex+1<heapSize && arr[leftIndex]<arr[leftIndex+1]?leftIndex+1:leftIndex;
            largestIndex = arr[index]>arr[largestIndex]?index:largestIndex;
            if(largestIndex != index){
                swap(arr,index,largestIndex);
                index = largestIndex;
                leftIndex = largestIndex*2+1;
            }else {
                break;
            }
        }
    }
}

堆排序heapInsert花費(fèi)的時(shí)間為log1+log2+log3+log4...+logN；heapify的操作也是相當(dāng)于每個(gè)元素依次遍歷二叉樹的高度，因?yàn)橛蠴(log1+log2+...+logn)=O(log(n!))=O(nlogn)所以堆排序的時(shí)間復(fù)雜度為O(NlogN)，且堆排序的額外空間復(fù)雜度為O(1)。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 從廣義上來講：數(shù)據(jù)結(jié)構(gòu)就是一組數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) ， 算法就是操作數(shù)據(jù)的方法數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的，算法是要作用在特定...
    冰風(fēng)v落葉閱讀 3,928評(píng)論 0贊 12
  • 排序算法基礎(chǔ) 排序算法，是一種能將一串?dāng)?shù)據(jù)按照特定的排序方式進(jìn)行排列的一種算法，一個(gè)排序算法的好壞，主要從時(shí)間復(fù)雜...
    jackyshan閱讀 4,296評(píng)論 3贊 11
  • 排序算法說明 （1）排序的定義：對(duì)一序列對(duì)象根據(jù)某個(gè)關(guān)鍵字進(jìn)行排序； 輸入：n個(gè)數(shù)：a1,a2,a3,…,an 輸...
    code武閱讀 737評(píng)論 0贊 0
  • 本文首發(fā)于我的個(gè)人博客：尾尾部落 排序算法是最經(jīng)典的算法知識(shí)。因?yàn)槠鋵?shí)現(xiàn)代碼短，應(yīng)該廣，在面試中經(jīng)常會(huì)問到排序算法...
    繁著閱讀 4,679評(píng)論 3贊 118
  • 其實(shí)一些類似于奧卡姆剃刀的原理可以應(yīng)用到一切領(lǐng)域。這個(gè)世界上越簡(jiǎn)單的東西越有價(jià)值，越有可能正確。 大一時(shí)教微積分的...
    鷇音bird閱讀 491評(píng)論 0贊 0

友情鏈接更多精彩內(nèi)容