Sort Algorithm

Sorting is based on Priority, priority could be defined.

Selection Sort

• 双指针站肩

  • 被站肩的i是否需要走完

  • 站在i的肩膀上从哪儿开始走

  • TC＝n-1 + n-2 + n-3 ....+2 + 1 = O(n^2)

  • SC = O(1)

• the output could be void, explain how the java store the object such as arr;

• java is always passed by reference value copy.

• need to demo stack and heap structure;

• actually store in arr'

  • stack heap

  • arr {21359}

  • arr'

public int[] selectionSort(int[] arr){ 
    if(arr == null || arr.length <= 1) return arr;
    
    for(int i = 0; i < arr.length-1; i++){
        int minIdex = i;
        for(int j = i+1; j < arr.length; j++){
            if(arr[j] < arr[midIndex]) minIndex = j;
        }
        swap(arr, i, minIndex);
    }
    return arr;
}
private void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    //return;
}

Merge Sort

• TC: O(nlogn)

• SC: O(n)

public ArrayList<Integer> divideAndMerge(ArrayList<Integer> arr, int left , int right){
    ArrayList<Integer> res = new  ArrayList<>();
    if(left == right){
        res.add(arr.get(left));
        return res;
    }
    int mid = left + (right - left)/2;
    ArrayList<Integer> leftRes = divideAndMerge(arr, left, mid);
    //wall
    ArrayList<Integer> rightRes = divideAndMerge(arr, mid+1, right);
    return merge(leftRes, rightRes)
}

Quick Sort

• pivot分成两半，do a partition two; left指针找比最后一个大的，right找小的

• TC: 现办事后recursion best：O(nlogn) worst: O(n^2)

• S1 双指针相向 not stable --> while

• S2 双指针同向 not stable --> for loop

• + recursion

• MoveZeros SortColor

Sort with Heap / Heap Sort

有项无环图 Topological Sort DAG(directed acyclic graph)

• check cycle first, if there is not cycle, we could use topological sort

Summary:

• MergeSort

  • stable

  • extra space

  • TC: O(nlogn) SC: O(n)

• QuickSort

  • unstable

  • TC: O(nlogn) worst O(n^2); SC:O(1)

  • optimize: random select 5 pivots, and select the medium num from these 5 pivots --> O(nlogn)

Master Theory for Time Complexity

T(n) = a * T(n/b) + O(n^k)

• eg: T(n) = 2 * T(n/2) + O(n) --> a = b^k, TC is O(n^k * logn)

Recursion I

• function call function self

• for stop, we need base case

• recursion rule : f(n) = F(f(n-1)) 大问题变小问题

L70 Climbing Stairs

• Fibonacci Sequence

  • too large

  • input valid?

  • how many base case

  S1: recursion: Time Limit Exceeded on Leetcode

• there is a wall between Fibonacci(n-1) + Fibonacci(n-2);

public int Fibonacci(int n){ // TODO long
    // corner case
    if(n < 0) throw new IllegalArgumentException();
    // base case
    if(n == 0 || n == 1) return n;
    return Fibonacci(n-1) + Fibonacci(n-2);   
}

Dynamic Programming I

• 从小到大考虑－－状态转移方程

• dp 的base case也是recursion 的base case

• dp的优化主要考虑的是空间复杂度

• Test case：不重复不遗漏

  • 特殊到一般

  • int：biggest，smallest，－1，0，2

  • null{} {1}{1 2} {2 1}

Q2 implement MyPow(x,n)

• S1: x^n， bruce force, primitive recursion TC O(n)

• S2: MyPow(x,n) --> MyPow(x, 2/n)*MyPow(x, n -2/n) 奇偶都可以

  • TC: O(2^logn ) --> O(n)

pubic int MyPow(int x, int n){ //TODO long
    
    if(n == 1) return x;
    return MyPow(x, 2/n) * MyPow(x, n-n/2);
    
}

• S3: TC: O(logn)

public long myPow(int x, int n){
    if(n == 0) return 1;
    long temp = myPow(x, n/2); // cache variable for duplicate value / statement catche 到函数里面
    return n % 2 == 0? temp * temp : temp * temp * x
}