Sorting Summary

Bubble Sort

 public static void bubbleSort(int[] arr) {
    // Total run n - 1
    for(int i=0; i<arr.length-1; i++) {
        for(int j=arr.length-1; j>i; j--) {
            if(arr[j] < arr[j-1]) {
                swap(arr, j-1, j);
            }
        }
    }
}

Quick Sort

排序原理：Bubble + partition + recursive

public static void quickSort(int[] arr, int left, int right) {
    if(left >= right)
        return ;
    int pivotPos = partition(arr, left, right);
    quickSort(arr, left, pivotPos-1);
    quickSort(arr, pivotPos+1, right);
}
public static int partition(int[] arr, int left, int right) {
    int pivotKey = arr[left];

    while(left < right) {
        while(left < right && arr[right] >= pivotKey)
            right --;
        arr[left] = arr[right]; //move small to left
        while(left < right && arr[left] <= pivotKey)
            left ++;
        arr[right] = arr[left]; //move big to right
    }
    arr[left] = pivotKey; //put pivot to middle
    return left;
}

Merge Sort

public static void mSort(int[] arr, int left, int right) {
    if(left >= right)
        return ;
    int mid = (left + right) / 2;

    mSort(arr, left, mid); //Recursive left part (left -> mid);
    mSort(arr, mid+1, right); //Recursive right part ( mid + 1 -> righgt)
    merge(arr, left, mid, right); //Merge
}
public static void merge(int[] arr, int left, int mid, int right) {
    //[left, mid] [mid+1, right]
    int[] temp = new int[right - left + 1]; // temperary array

    int i = left;
    int j = mid + 1;
    int k = 0;
    // when left array and right array both have value, put smaller to temp array
    while(i <= mid && j <= right) {
        if(arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];
        }
    }

    // if left array still have value, just copy rest to temp array
    while(i <= mid) {
        temp[k++] = arr[i++];
    }
        // if right array still have value, just copy rest to temp array
    while(j <= right) {
        temp[k++] = arr[j++];
    }

        // Over write array for left + p
    for(int p=0; p<temp.length; p++) {
        arr[left + p] = temp[p];
    }
}