算法入门

problem sorting:
Input: n个数
Output: 输入序列的一个排序，为非递减序列

插入排序(Java)

  1. public void InsertionSort(int[] A, int n){
  2.     for(int j=2; j<n; j++){
  3.       int key = A[j];
  4.     int i = j-1;
  5.     while(i>=0 && A[i]>key){
  6.         A[i+1] = A[i];
  7.       i = i-1;
  8.     }
  9.     A[i+1] = key;
  10.   }
  11. }

Running Time ：

  • Depends on input(e.g. already sorted)
  • Depends on input size(6 elements vs 6000000 elements)

Kind of analysis :
Worst-Case( usually ): T(n) = max time on any input of size n;
Average-Case( sometimes ): T(n) = expected time over all inputs of size n; 需要概率分析假设
Best-Case
What is insertionSort’s use time?
Depends on Computer！

  • relative speed(on same computer)
  • absolute speed(on different computer)

BIG IDEA!

  • Ignore machine-dependent constant

  • Look at growth of the running time as n to 无穷

    归并排序

    Idea:

  • if n=1, DONE

  • Recursively sort A[1,…,n/2] and A[n/2+1,…,n]
  • merge 2 sorted list