快速排序、歸并排序、數組切分(Partition Array)、Quick Select算法總結

文章目錄

• 1. 快速排序
• • 思路
  • 代碼
• 2. 歸并排序
• • 思路
  • 代碼
• 3. 數組切分問題(Partition Array)
• • 3.1 [LintCode-31. Partition Array](https://www.lintcode.com/problem/partition-array/description)
  • • 題意
    • 思路
    • 代碼
  • 3.2 [LintCode373. Partition Array by Odd and Even](https://www.lintcode.com/problem/partition-array-by-odd-and-even/description)
  • • 題意
    • 思路
    • 代碼
  • 3.3 [LintCode49.Sort Letters by Case](https://www.lintcode.com/problem/sort-letters-by-case/description)
  • • 題意
    • 思路
    • 代碼
  • 3.4 [LintCode144-Interleaving Positive and Negative Numbers](https://www.lintcode.com/problem/interleaving-positive-and-negative-numbers/description)
  • • 題意
    • 思路
    • 代碼
• 4. QuickSelect問題
• • 4.1 [LeetCode215. Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/)
  • • 題意
    • 思路
    • 代碼
  • 4.2 [LintCode80. Median](https://www.lintcode.com/problem/median/description)
  • • 題意
    • 思路
    • 代碼

1. 快速排序

• 以LeetCode912為載體

思路

• 先整體有序，後局部有序
• 先将整個大數組以某個

  pivot

  劃分成左右有序的狀态，然後縮小區間，重複這個過程
• 具體的實作細節均在代碼中

代碼

class LeetCode912 {
    public List<Integer> sortArray(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0){
            return result;
        }
        int start = 0;
        int end = nums.length - 1;
        quickSort(nums,start,end);

        for (int num : nums) {
            result.add(num);
        }
        return result;
    }
    //0. 這是個遞歸函數，它的定義是 在閉區間[start,end]中，把所有小于 nums[(start+end)/2]的數都放在它左邊
    //   把所有大于這個的數都放在它右邊。然後不斷的去縮小這個區間
    //   也就是先整體有序 後局部有序
    private void quickSort(int[] nums, int start, int end) {
        //1. 遞歸出口
        if (start >= end){
            return;
        }
        //1.1 緩存區間端點 後面縮小區間的時候還需要這兩個端點的資訊
        int left = start;
        int right = end;

        //2. get value not index
        int pivot = nums[(end + start)/2];
        //2.1 接下來的操作就是以pivot為錨點 切分數組
        //    注意這裡的細節 left <= right,為何要等于呢？
        //    就是為了跳出while後，能達到這樣的狀态:start......right,left,.....end
        while (left <= right){
            //2.2 找到第一個應該在 pivot右邊的數
            while (left <= right && nums[left] < pivot ){
                left++;
            }
            //2.3 找到第一個應該在 pivot左邊的數
            while (left <= right && nums[right] > pivot){
                right--;
            }
            //2.4 找到後，完成交換
            if (left <= right){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        //3. 跳出while，完成了本次區間内的切分，接下來縮小區間
        //3.1 此時left和right的狀态一定是  start......right,left,.....end
        quickSort(nums, start, right);
        quickSort(nums, left, end);
    }
}
           

2. 歸并排序

• 以LeetCode912為載體

思路

• 先局部有序，後整體有序
• 先一直把數組二分下去，直到找到最小有序的部分，那麼就開始向上合并兩個有序的部分
• 顯然最開始最小的有序部分就是單個數字本身嘛
• 既然需要合并兩個有序的數組，那麼肯定就額外需要另一個數組來騰挪，這也是歸并相對于快排劣勢的一點，需要額外的開辟一個數組的額外空間
• 細節都在代碼裡

代碼

class LeetCode912 {
    public List<Integer> sortArray(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0){
            return result;
        }
        int start = 0;
        int end = nums.length - 1;
        //用于合并兩個有序數組
        int[] temp = new int[nums.length];
        mergeSort(nums,start,end,temp);
        for (int num : nums) {
            result.add(num);
        }
        return result;
    }
    //0. 這是一個遞歸函數，其定義是：将閉區間[start,end]劃分為兩半
    private void mergeSort(int[] nums, int start, int end, int[] temp) {
        //3.出
        //3.1 當切分到隻剩一個元素的時候，就無需再繼續往下了，此時已經是最小的有序區間
        if (start >= end){
            return;
        }
        //1.分
        //  就是分治法的味道，先分下去
        int mid = (end - start)/2 + start;
        mergeSort(nums, start, mid, temp);
        mergeSort(nums, mid+1, end, temp);
        //2.合
        //  從上述遞歸中出來後，可以認為 區間：[start,mid]和[mid+1,end]已經是有序了
        //  那麼接下來隻需要合并這兩個有序區間即可
        merge(nums,start,mid,end,temp);
    }
    //此函數可認為是合并兩個有序數組
    private void merge(int[] nums, int start, int mid, int end, int[] temp) {
        //1. 兩有序數組的起始點
        int left = start;
        int right = mid +1;
        //2. 有序數組的index
        int index = 0;
        //3. 這裡都是index，是以可以取到
        while (left <= mid && right <= end){

            if (nums[left] < nums[right]){
                temp[index++] = nums[left++];
            }else {
                temp[index++] = nums[right++];
            }
        }
        //3.1 double check
        while (left <= mid){
            temp[index++] = nums[left++];
        }
        while (right <= end){
            temp[index++] = nums[right++];
        }

        //4. 現在數組nums中[start,end]都是有序的,但是呢，這一部分的值還暫存在temp的[0,index]區間内
        //4.1 現在要把這個有序的部分指派給nums的[start,end]部分
        //4.2 要注意這裡index不能取等，因為你想，最後一個元素指派給temp後，index完成了一次自加操作
        for (int i = 0; i < index; i++) {
            nums[start++] = temp[i];
        }
    }
}
           

3. 數組切分問題(Partition Array)

3.1 LintCode-31. Partition Array

題意

• 給定數組和一個數

  k

  ，要求把數組中

  <k

  的數放在左邊，

  >=k

  的數放在右邊，傳回第一個大于等于

  k

  的數的索引

思路

• 這不就是快排中每一次劃分的算法嘛
• 隻要快排了解了，這一道題就很簡單了

代碼

public int partitionArray(int[] nums, int k) {
        // write your code here

        if (nums == null || nums.length == 0){
            return 0;
        }

        int left = 0;
        int right = nums.length - 1;
        while (left <= right){

            while (left <= right && nums[left] < k){
                left++;
            }
            while (left <= right && nums[right] >= k){
                right--;
            }

            if (left <= right){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        // start ... right left ... end
        return left;
    }
           

3.2 LintCode373. Partition Array by Odd and Even

題意

• 給定數組
• 将數組中的奇數放在前面(左邊)
• 将數組中的偶數放在後面(右邊)

思路

• 和上題完全一樣嘛，隻是條件變了

代碼

public void partitionArray(int[] nums) {

        if (nums == null || nums.length == 0){
            return;
        }

        int left = 0;
        int right = nums.length - 1;
        while (left <= right){

            //0. 找到第一個應該在 右側的偶數
            while (left <= right && nums[left] %2 == 1 ){
                left++;
            }
            //1. 找到第一個應該在 左側的奇數
            while (left <= right && nums[right] % 2 == 0){
                right--;
            }
            //2.交換
            if (left <= right){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }

    }
           

3.3 LintCode49.Sort Letters by Case

題意

• 給定字元數組
• 把小寫字母放在前面
• 把大寫字母放在後面

思路

• 和上題完全一緻，隻是判斷條件變成了字母是否為大小寫

代碼

public void sortLetters(char[] chars) {
        // write your code here

        if (chars == null || chars.length == 0){
            return;
        }
        int left = 0;
        int right = chars.length - 1;
        while (left <= right){
            //0. 找到第一個應該 在右側的大寫字母
            while (left <= right && Character.isLowerCase(chars[left])){
                left++;
            }
            //1. 找到第一個應該 在左側的小寫字母
            while (left <= right && Character.isUpperCase(chars[right])){
                right--;
            }
            if (left <= right){
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                left++;
                right--;
            }
        }

    }
           

3.4 LintCode144-Interleaving Positive and Negative Numbers

題意

• 給定數組
• 要求将數組劃分為正負相間的樣式

思路

• 關鍵在于處理正負數數量的影響
• 1.首先把所有的負數放在左邊 正數放在右邊
• 2.然後統計數量
• 3.數量多的代表第一個數和最後一個數都是它
• 4.然後按照步長為2前後交換即可

代碼

public void rerange(int[] A) {
        // write your code here
        if (A == null || A.length == 0){
            return;
        }
        int left = 0;
        int right = A.length - 1;
        //0. 先把所有的負數放在左側 正數放在右側
        while (left <= right){
            while (left <= right && A[left] < 0){
                left++;
            }
            while (left <= right && A[right] > 0){
                right--;
            }
            if (left <= right){
                int t = A[left];
                A[left] = A[right];
                A[right] = t;
                left++;
                right--;
            }
        }

        //1. 統計正負數的數量
        int posNum = 0;
        int negNum = 0;
        for (int num : A) {

            if (num > 0){
                posNum++;
            }
            if (num < 0){
                negNum++;
            }
        }
        //2. 根據正負數數量來決定完成劃分後誰位于首位和尾位
        //2.1 數量多的那一方 占據首尾
        //2.2 left和right代表交換的起始位置
        if (posNum > negNum){
            //2.3 那麼第一個數和最後一個數都是正數
            left = 0;
            right = A.length - 2;
        }else if (posNum < negNum){
            //2.4 那第一個數和最後一個數都是負數
            left = 1;
            right = A.length -1;
        }else {
            //2.5 一樣多,那就按照負正負正的次序進行排列即可
            left = 0;
            right = A.length - 1;
        }
        //3. 随後進行交換，注意步長為2
        while (left <= right){
            int t = A[left];
            A[left] = A[right];
            A[right] = t;
            left+=2;
            right-=2;
        }
    }
           

4. QuickSelect問題

4.1 LeetCode215. Kth Largest Element in an Array

題意

• 給定無序數組和一個數

  k

  ，要求找到改數組中第

  k

  大的數

思路

• 利用數組劃分和快速排序思想
• 不斷的縮小第

  k

  大可能存在的區間
• 具體細節都在代碼注釋中

代碼

class LeetCode215 {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0){
            return -1;
        }
        
        return quickSelect(nums,0,nums.length - 1,k);
        
    }
    //0. 思想就在于通過切分數組 不斷的壓縮 k-th可能在的區間
    private int quickSelect(int[] nums, int start, int end, int k) {
        //2.遞歸出口
        //2.1 為何相等的時候就要退出了呢，因為此時區間中就隻有一個數了嘛，那這個數肯定就是要找的
        if (start == end){
            return nums[start];
        }


        int left = start;
        int right = end;
        int pivot = nums[(left + right)/2];
        //0. 以pivot為界，把數組元素切分為兩部分，左側大于它，右側小于它
        //0.1 注意這裡和快排不同，因為這裡是求第k大
        while (left <= right){

            //0.2 找到第一個應該在右邊的數
            while (left <= right && nums[left] > pivot){
                left++;
            }
            while (left <= right && nums[right] < pivot){
                right--;
            }
            //0.3 交換
            if (left <= right){
                int t = nums[left];
                nums[left] = nums[right];
                nums[right] = t;
                left++;
                right--;
            }
        }
        //1. 完成劃分，現在left和right的位置關系有兩種可能
        //1.1 start....right,left....end
        //1.2 start.....right,A,left...end 這種隔了一個的狀态是由于上面while中的if導緻的
        //1.3 當if中二者 left = right後，滿足添加，執行if内的代碼，然後會 left++,right--，就會導緻這種剛好錯開一個的情況
        //1.4 我們要找第k大，那麼就需要判斷 第k大 可能會落在哪個區間
        //1.5 現在一個好消息在于區間[start，right]中的數都大于區間[left,end]
        //1.6 那麼需要判斷k是否落在這兩個區間内，第k大是基于1的，而上述的left這些都是索引，基于0，是以需要k-1
        if (start + k - 1 <= right){
            //1.7 第k大在左半區間，是以扔掉右邊的一半
            return quickSelect(nums, start, right, k);
        }
        if (start + k - 1 >= left){
            //1.8 第k大在右半區間,是以扔掉左邊的一半
            //1.8.1 左邊一半的數量是多少呢
            return quickSelect(nums,left,end,k - (left - start));
        }
        //1.9 如果落在中間，即情況1.2
        return nums[right+1];
    }
}

           

4.2 LintCode80. Median

題意

• 給定未排序數組，求其中位數

思路

• 隻要分析清楚中位數是第幾大的數
• 那麼問題就轉換為了在無序數組中求第k大的數問題
• 分奇數和偶數不難分析出中位數都是第

  n/2 - 1

  大的數

代碼

public class Solution {
  public int median(int[] nums) {

        //0. 簡單分析發現，不管數字個數是奇數還是偶數，其中位數都是第(n/2) + 1大的數
        int k = nums.length/2 + 1;
        //1. 那麼剩餘的工作就是在一個未排序的數組中找第k大的數
        return findKthLargest(nums, k);
    }

    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0){
            return -1;
        }

        return quickSelect(nums,0,nums.length - 1,k);

    }
    //0. 思想就在于通過切分數組 不斷的壓縮 k-th可能在的區間
    private int quickSelect(int[] nums, int start, int end, int k) {
        //2.遞歸出口
        //2.1 為何相等的時候就要退出了呢，因為此時區間中就隻有一個數了嘛，那這個數肯定就是要找的
        if (start == end){
            return nums[start];
        }


        int left = start;
        int right = end;
        int pivot = nums[(left + right)/2];
        //0. 以pivot為界，把數組元素切分為兩部分，左側大于它，右側小于它
        //0.1 注意這裡和快排不同，因為這裡是求第k大
        while (left <= right){

            //0.2 找到第一個應該在右邊的數
            while (left <= right && nums[left] > pivot){
                left++;
            }
            while (left <= right && nums[right] < pivot){
                right--;
            }
            //0.3 交換
            if (left <= right){
                int t = nums[left];
                nums[left] = nums[right];
                nums[right] = t;
                left++;
                right--;
            }
        }
        //1. 完成劃分，現在left和right的位置關系有兩種可能
        //1.1 start....right,left....end
        //1.2 start.....right,A,left...end 這種隔了一個的狀态是由于上面while中的if導緻的
        //1.3 當if中二者 left = right後，滿足添加，執行if内的代碼，然後會 left++,right--，就會導緻這種剛好錯開一個的情況
        //1.4 我們要找第k大，那麼就需要判斷 第k大 可能會落在哪個區間
        //1.5 現在一個好消息在于區間[start，right]中的數都大于區間[left,end]
        //1.6 那麼需要判斷k是否落在這兩個區間内，第k大是基于1的，而上述的left這些都是索引，基于0，是以需要k-1
        if (start + k - 1 <= right){
            //1.7 第k大在左半區間，是以扔掉右邊的一半
            return quickSelect(nums, start, right, k);
        }
        if (start + k - 1 >= left){
            //1.8 第k大在右半區間,是以扔掉左邊的一半
            //1.8.1 左邊一半的數量是多少呢
            return quickSelect(nums,left,end,k - (left - start));
        }
        //1.9 如果落在中間，即情況1.2
        return nums[right+1];
    }
}