Sorting Algorithms

Recursion

分析要点是： Base Case: Smallest Problem to Solve & Recursive Rule: How to make a problem smaller

a^b

首先base case 是 b = 0 和 b = 1这两种情况，我们把问题不断拆分，即 2^1000 = 2^500 * 2^500

public int pow(int a, int b){
    if(b == 0){
        return 1;
    }
    if(b == 1){
        return a;
    }
    int halfResult = pow(a, b / 2);
    if(b % 2 == 0){
        return halfResult  * halfResult ;
    }else{
        return halfResult * halfResult * a
    }
}

由于不断把pow进行拆分，所以这里时间复杂度为O(log b)， 空间为 O(log b)

Merge Sort

merge sort 就是把一个数组不断分拆分，直到拆为两两比较，再把它们合起来

3，1，5，7，9，8，6，4，2，0

31579 86420 O(1) 这个是找到中点，并把数组分为两类所需要的时间

315 79 864 20 O(2)

31 5 7 9 86 4 2 0 O(4)

因此，分开的时间是 1 + 2 + 4 + ... + n/2 = O(n) (对这个式子+1 -1 即可)

而需要的空间则是 n + n/2 + n/4 + .... + 1 = O(n)

完成分割之后，则进行合并，每次合并的总时间为O(n)， 在这里我们被分割为logn 层，所以总的合并时间为O(nlogn)

public int[] mergeSort(int[] array, int n){
    if(n < 2){
        return a;
    }
    int mid = n / 2;
    int[] l = new int[mid];
    int[] r = new int[n-mid];
    for(int i = 0; i < mid; i++){
        l[i] = array[i];
    }
    for(int i = mid; i < end; i++){
        r[i-mid] = array[i];
    }
    mergeSort(l, mid);
    mergeSort(r, n-mid);
    merge(array, l, r, mid, n-mid)
    
}
public void merge(
  int[] a, int[] l, int[] r, int left, int right) {
  
    int i = 0, j = 0, k = 0;
    while (i < left && j < right) {
        if (l[i] <= r[j]) {
            a[k++] = l[i++];
        }
        else {
            a[k++] = r[j++];
        }
    }
    while (i < left) {
        a[k++] = l[i++];
    }
    while (j < right) {
        a[k++] = r[j++];
    }
}

Quick Sort

public Solution{
    public int[] quickSort(int[] array){
        if(array == null){
            return array;
        }
        quickSort(array, 0, array.length - 1);
        return array;
    }
    
    public void quickSort(int[] array, int left, int right){
    if (left >= right) {
      return;
    }
    int pivotIdx = partition(array, left, right);
    quickSort(array, left, pivotIdx-1);
    quickSort(array, pivotIdx+1, right);
  }
  
    private void partition(int[] array, int start, int end){
        int pivotIdx = start + (int)(Math.random()*(end- start));
        int pivot    = array[pivotIdx];
        swap(array, pivot, end);
        int leftBound = start;
        int rightBound = end - 1;
        while(leftBound <= rightBount){
            if(arrat[leftBound] < pivot){
                leftBound++;
            }else{
                swap(array, leftBound, rightBound);
                rightBound--;
            }
        }
        swap(array, leftBound, end);
        return leftBound;
    }
}