常见排序算法整理

import java.util.Random;

public class Sorting {

    /**
     *  For each element, compare with all the elements before it and swap position accordingly
     *  https://www.toptal.com/developers/sorting-algorithms/insertion-sort
     *  https://www.geeksforgeeks.org/insertion-sort/
     */
    public int[] insertionSort(int[] nums){
        int n = nums.length;
        //starting from i=1
        for(int i = 1; i < n; i++) {
            //save the current number to key
            int key = nums[i];
            //keep shifting the element to find the place for "insertion"
            int j = i - 1;
            while (j >= 0 && nums[j] > key) {
                nums[j + 1] = nums[j];
                j--;
            }
            //place the current element
            nums[j + 1] = key;
        }
        return nums;
    }

    /**
     * For each element, search all the elements after it to find the minimal one and swap with it.
     * https://www.toptal.com/developers/sorting-algorithms/selection-sort
     * https://www.geeksforgeeks.org/selection-sort/
     */
    public int[] selectionSort(int[] nums){
        int n = nums.length;
        //starting from i=0
        for(int i=0;i<n-1;i++) {
            //define cur as minIdx and update minIdx for all the elements after cur element
            int minIdx = i;
            for(int j = i+1;j<n;j++){
                if(nums[j] < nums[minIdx]){
                    minIdx = j;
                }
            }
            //swap cur with the minimal after it
            swap(nums,i,minIdx);
        }
        return nums;
    }

    /**
     * For each round, compare adjacent element for all the unsorted elements to pop up one maximum element.
     * https://www.toptal.com/developers/sorting-algorithms/bubble-sort
     * https://www.geeksforgeeks.org/bubble-sort/
     */
    public int[] bubbleSort(int[] nums){
        int n = nums.length;
        //if no swap for this iteration, sort can exit earlier
        boolean swapped;
        for(int i=0;i<n-1;i++){
            swapped = false;
            //for all the elements before cur, swap with adjacent element
            for(int j=0;j<n-1-i;j++){
                if(nums[j]>nums[j+1]){
                    swap(nums,j,j+1);
                    swapped = true;
                }
            }
            if(!swapped){
                break;
            }
        }
        return nums;
    }

    /**
     * Shell sort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead.
     * When an element has to be moved far ahead, many movements are involved. The idea of ShellSort is to allow the
     * exchange of far items. In Shell sort, we make the array h-sorted for a large value of h.
     * We keep reducing the value of h until it becomes 1
     *
     * https://www.toptal.com/developers/sorting-algorithms
     * https://www.geeksforgeeks.org/shellsort/
     */
    public int[] shellSort(int[] nums){
        int n = nums.length;
        //define the gap and then reduce the gap
        for(int gap = n/2; gap>0; gap /=2){
            //Do a gapped insertion sort for this gap size;
            for(int i = gap; i< n ; i++){
                //for each element, find the correct place to put it
                int temp = nums[i];
                int j;
                for(j = i; j>=gap && nums[j-gap] > temp; j -=gap){
                    nums[j] = nums[j-gap];
                }
                nums[j] = temp;
            }
        }
        return nums;
    }

    /**
    * A recursive algorithm continuously splits the array in half until it cannot be further divided.
    * Finally, when both halves are sorted, the merge operation is applied.
    * https://www.toptal.com/developers/sorting-algorithms/merge-sort
    * https://www.geeksforgeeks.org/merge-sort/
    **/
    public int[] mergeSort(int[] nums){
        int n = nums.length;
        mergeSort(nums,0,n-1);
        return nums;
    }

    private void mergeSort(int[] nums, int l, int r){
        if(l<r){
            int m = l +(r-l)/2;
            mergeSort(nums,l,m);
            mergeSort(nums,m+1,r);
            merge(nums,l,m,r);
        }
    }

    //merge subarray nums[l,m] and nums[m+1,r]
    private void merge(int[] nums, int l, int m, int r){
        int n1 = m-l+1;
        int n2 = r-m;

        int[] lTmp = new int[n1];
        int[] rTmp = new int[n2];
        //copy into tmp arrays
        for(int i=0;i<n1;i++){
            lTmp[i] = nums[l+i];
        }
        for(int j=0;j<n2;j++){
            rTmp[j] = nums[m+1+j];
        }

        //merge, be careful k = l
        int i =0, j =0;
        int k = l;
        while(i<n1 && j<n2){
            if(lTmp[i] <= rTmp[j]){
                nums[k++] = lTmp[i++];
            }else{
                nums[k++] = rTmp[j++];
            }
        }
        while(i<n1){
            nums[k++] = lTmp[i++];
        }
        while(j<n2){
            nums[k++] = rTmp[j++];
        }
    }

    /**
     * Build a max heap and then keeps popping out the max
     * https://www.toptal.com/developers/sorting-algorithms/heap-sort
     * https://www.geeksforgeeks.org/heap-sort/
     * https://www.cnblogs.com/jdflyfly/p/3913571.html
     *
    */
    public int[] heapSort(int[] nums){
        //be careful with the index here, n,n-1
        int n = nums.length;
        buildHeap(nums);
        //swap cur with element 0 and then heapify 0
        for(int i = n-1;i>0;i--){
            swap(nums,i,0);
            heapify(nums,--n,0);
        }
        return nums;
    }

    private void buildHeap(int[] nums){
        //use heapify to build heap
        for(int i=nums.length/2; i>=0; i--){
            heapify(nums,nums.length,i);
        }
    }

    private void heapify(int[] nums, int n, int i){
        int l = 2*i+1;
        int r = 2*i+2;
        //define the largest and update it
        int largest = i;
        if(l<n && nums[l] > nums[i]){
            largest = l;
        }
        if(r<n && nums[r] > nums[largest]){
            largest = r;
        }
        if(largest != i){
            //if swapped with one child, continue to heapify
            swap(nums,largest,i);
            heapify(nums,n,largest);
        }

    }

    /**
     * 快排算法核心的部分便是partition过程，这里的partition采取最后一个元素作为pivot,也可以采用其他方法决定pivot然后跟last element交换
     * https://www.cnblogs.com/jdflyfly/p/3897331.html
     * https://www.toptal.com/developers/sorting-algorithms/quick-sort
     * https://www.geeksforgeeks.org/quick-sort/
     */
    Random random = new Random();
    public int[] quickSort(int[] nums){
        qSort(nums,0,nums.length-1);
        return nums;
    }

    private void qSort(int[] a, int p, int r){
        if(p<r){
            int q = partition(a,p,r);
            qSort(a,p,q-1);
            qSort(a,q+1,r);
        }
    }

    private int partition(int[] a, int p, int r){
        //x is the privot element, i points to the last small element, j scans all the elements
        int randomIdx = random.nextInt(r-p+1) + p;
        swap(a,randomIdx, r);
        int x = a[r];
        int i = p-1;
        int j = p;
        for(j = p; j<r; j++){
            if(a[j]<=x){
                i++;
                swap(a,i,j);
            }
        }
        swap(a,i+1,r);
        return i+1;
    }

    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}