Sort: merge sort and quick sort

Power button leetcode：912. Sort array , Can be used to practice sorting algorithm

subject ： Give you an array of integers  nums, Please arrange the array in ascending order .

Catalog

Merge sort

Quick sort

---

Both merging and fast sorting use the idea of recursion and divide and conquer . Merger ： The following traversal of binary tree ; Quick line up ： Preorder traversal of two tree .

Why don't you say so ？ The core code framework of sorting ：

 Merge sort 
public void sort(int[] nums,int low,int high){
        if(low == high) return;
        int mid = low + (high - low)/2;
        // Sort left half array ,nums[low...mid]
        sort(nums,low,mid);
        // Sort the right half of the array ,nums[mid+1...high]
        sort(nums,mid+1,high);
        
        // Subsequent positions of binary tree traversal , Merge nums[low...mid] and nums[mid+1...high]
        merge(nums,low,mid,high);
}

First sort the left and right arrays , Re merger . 

 Quick sort 
public void sort(int[] nums,int low,int high){
        if(low >= high) return;
        // The preorder position of a binary tree , division 
        int p = partition(nums,low,high);

        // To the left half of the partition nums[low...p-1] Sort 
        sort(nums,low,p - 1);
        // Right half of the division nums[p+1...high] Sort 
        sort(nums,p + 1,high);
} 

  First construct the boundary point , Then go to the dividing point of the left and right subtree groups .

Merge sort

The process ：

• First, divide the array to be sorted into two parts Left and Right
• Yes Left Partial sorting
• Yes Right Partial sorting
• Merge Left and Right Two parts , Merge into an ordered array

Code ：

class Solution {
    int[] temp; // Auxiliary array of merge sort 
    public int[] sortArray(int[] nums) {
        // Merger 
        temp = new int[nums.length];
        sort(nums,0,nums.length-1);
        return nums;

    }

    public void sort(int[] nums,int low,int high){
        if(low == high) return;
        // Effectively prevent overflow , Actually sum (low + high)/2 Equivalent 
        int mid = low + (high - low)/2;
        // Sort left half array 
        sort(nums,low,mid);
        // Sort the right half of the array 
        sort(nums,mid+1,high);
        merge(nums,low,mid,high);
    }

    public void merge(int[] nums,int low,int mid,int high){
        // First the nums[low...high] The value of is stored in the auxiliary array temp in 
        for(int i = low;i <= high;i++){
            temp[i] = nums[i];
        }
        // Double pointer merge 
        int i = low,j = mid + 1;
        for(int m = low; m <= high; m++){
            if(i == mid + 1) nums[m] = temp[j++];
            else if( j == high + 1) nums[m] = temp[i++];
            else if(temp[i] > temp[j]) nums[m] = temp[j++];
            else nums[m] = temp[i++]; 
        }
    }
}

Quick sort

Quick sort is to sort an element first , Then put the remaining elements in order . The core function is partition function ：

The process ：

• Is in nums[low...high] Find a dividing point in p
• Exchange elements so that nums[low...p-1] All elements of are less than or equal to nums[p]
• nums[p+1...high] All of the elements are greater than nums[p]

partition It's just a way of nums[p] This element is in order

  Code ：

class Solution {
    public int[] sortArray(int[] nums) {
       // Quick line up 
       sort(nums,0,nums.length - 1);
       return nums;
    }
    public void sort(int[] nums,int low,int high){
        if(low >= high) return;
        // Yes nums[low...high] division 
        // bring nums[low...p-1] <= nums[p] < nums[p+1...high]
        int p = partition(nums,low,high);
        sort(nums,low,p - 1);
        sort(nums,p + 1,high);
    } 

    public int partition(int[] nums,int low,int high){
        int pivot = nums[low];
        int i = low + 1,j = high;
        while(i <= j){ // Continuous exchange , Until the left side is satisfied, it is less than , The right side is larger than 
            while(i < high && nums[i] <= pivot) i++; // The while At the end num[i] > pivot
            while(j > low && nums[j] > pivot) j--; // The while At the end num[j] <= pivot 
            if(i >= j) break;
            swap(nums,i,j); // Exchange these two 
        }
        // take pivot Put it in the right place ,pivot The element on the left is smaller than it ,pivot The element on the right is bigger than it 
        swap(nums,low,j);
        return j;
    }
    public void swap(int[] nums,int a,int b){
        int temp = nums[b];
        nums[b] = nums[a];
        nums[a] = temp;
    }
}