NC Note: Quick sort, merge sort and quick select

1. Quick Sort

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

public class Solution {     /**      * @param A an integer array      * @return void      */     public void sortIntegers2(int[] A) {         quickSort(A, 0, A.length - 1);     }           private void quickSort(int[] A, int start, int end) {         if (start >= end) {             return;         }                   int left = start, right = end;         // key point 1: pivot is the value, not the index         int pivot = A[(start + end) / 2];           while (left <= right) {             while (left <= right && A[left] < pivot) {                 left++;             }                           while (left <= right && A[right] > pivot) {                 right--;             }                           if (left <= right) {                 swap(A, left, right);                 left++;                 right--;             }         }                   quickSort(A, start, right);         quickSort(A, left, end);     }           private void swap(int[] A, int i, int j) {         int temp = A[i];         A[i] = A[j];         A[j] = temp;     } }

2. Merge Sort

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

public class Solution {     /**      * @param A: an integer array      * @return: nothing      */     public void sortIntegers2(int[] A) {         if (A == null || A.length < 2) {             return;         }           int[] temp = new int[A.length];           sortIntegers2Helper(A, temp, 0, A.length - 1);     }       private void sortIntegers2Helper(int[] A, int[] temp, int start, int end) {         if (start >= end) {             return;         }           int mid = start + (end - start) / 2;         sortIntegers2Helper(A, temp, start, mid);         sortIntegers2Helper(A, temp, mid + 1, end);           // merge         //         merge(A, temp, start, end);     }       private void merge(int[] A, int[] temp, int start, int end) {         int mid = start + (end - start) / 2;         int i = start;         int j = mid + 1;         int k = start;           while (i <= mid || j <= end) {             if (i > mid) {                 temp[k++] = A[j++];             } else if (j > end) {                 temp[k++] = A[i++];             } else if (A[i] < A[j]) {                 temp[k++] = A[i++];             } else {                 temp[k++] = A[j++];             }         }           for (i = start; i <= end; i++) {             A[i] = temp[i];         }     } }

3. Quick Select

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

public class Solution {     /**      * @param n: An integer      * @param nums: An array      * @return: the Kth largest element      */     public int kthLargestElement(int n, int[] nums) {         if (nums == null || nums.length == 0) {             return 0;         }                   return kthLargestElementHelper(nums, 0, nums.length - 1, nums.length - n);     }           private int kthLargestElementHelper(int[] nums, int start, int end, int k) {         if (start == end) {             return nums[start];         }                   int i = start;         int j = end;         int pivot = nums[(i + j) / 2];                   while (i <= j) {             while (i <= j && nums[i] < pivot) {                 i++;             }                           while (i <= j && nums[j] > pivot) {                 j--;             }                           if (i <= j) {                 swap(nums, i, j);                 i++;                 j--;             }         }                   if (k <= j) {             return kthLargestElementHelper(nums, start, j, k);         } else if (k >= i) {             return kthLargestElementHelper(nums, i, end, k);         } else {             return nums[k];         }     }           private void swap(int[] nums, int i, int j) {         int temp = nums[i];         nums[i] = nums[j];         nums[j] = temp;     } }

Another version:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

public class Solution {     /**      * @param n: An integer      * @param nums: An array      * @return: the Kth largest element      */     public int kthLargestElement(int n, int[] nums) {         // write your code here         if (nums == null || nums.length == 0 || n > nums.length) {             return -1;         }           return kthLargestElementHelper(nums, 0, nums.length - 1, n);     }       private int kthLargestElementHelper(int[] nums, int start, int end, int k) {         if (start >= end) {             return nums[start];         }           int i = start;         int j = end;           int pivot = nums[(i + j) / 2];           while (i <= j) {             while (i <= j && nums[i] > pivot) {                 i++;             }               while (i <=j && nums[j] < pivot) {                 j--;             }               if (i <= j) {                 int temp = nums[i];                 nums[i] = nums[j];                 nums[j] = temp;                   i++;                 j--;             }         }           if (j - start + 1 >= k) {             return kthLargestElementHelper(nums, start, j, k);         }           if (i - start + 1 <= k) {             return kthLargestElementHelper(nums, i, end, k - i + start);         }           return nums[j + 1];     } }

Another version:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

public class Solution {     /**      * @param n: An integer      * @param nums: An array      * @return: the Kth largest element      */     public int kthLargestElement(int n, int[] nums) {         // write your code here         return kthLargestElementHelper(nums, 0, nums.length - 1, nums.length - n + 1);     }           private int kthLargestElementHelper(int[] nums, int start, int end, int k) {         if (start >= end) {             return nums[start];         }                   int i = start;         int j = end;         int pivot = nums[(i + j) / 2];                   while (i <= j) {             while (i <= j && nums[i] < pivot) {                 i++;             }                           while (i <= j && nums[j] > pivot) {                 j--;             }                           if (i <= j) {                 int temp = nums[i];                 nums[i] = nums[j];                 nums[j] = temp;                                   i++;                 j--;             }         }                   if (j - start + 1 >= k) {             return kthLargestElementHelper(nums, start, j, k);         }                   if (i - start + 1 <= k) {             return kthLargestElementHelper(nums, i, end, k - i + start);         }                   return nums[j + 1];     } }