讀處

(一)觀念:

將第i筆Data插入到前面(i-1)筆已排好之Data中,形成i筆排好之Data

(二)範例:給予5,3,8,2,6寫出排序過程(小->大)

Pass1 : 3,5,8,2,6

Pass2 : 3,5,8,2,6

Pass3 : 2,3,5,8,6

Pass4 : 2,3,5,6,8

(三)Algorithm/Program

(四)時間複雜度分析

1.Best case : O(n)

   情形:若input data 恰好是從小到大呈現/給予

   說明:量化比較(or Swap)次數，每一回合只比較1次即決定好A[i](或r)之位置

          又共作(n-1)回合，所以需要n-1次比較即完成sort，所以 O(n)

2.Worst case:O(n^2)

   情形:若input data 恰好是從大到小(反序)呈現/給予

   說明:量化比較(or Swap)次數

   例如給予 input : n,n-1,n-2,...,2,1

               pass1 : n-1,n,n-2,....,2,1   ->比較1次

               pass2 : n-2,n-1,n,....,2,1   ->比較2次

               pass3 :   ...                       ->比較3次

                  .

                  .

                  .

               pass(n-1) : ...                   ->比較(n-1)次

所以total=1+2+3+...+(n-1)=n(n-1)/2次比較,所以O(n^2)