算法设计与分析学习笔记——复杂度分析

 1 template<class Type>
 2 void insertion_sort(Type *a, intn)
 3 {
 4   Type key; // cost times 
 5   for (inti= 1; i< n; i++){                  // c1   n
 6           key=a[i];                          // c2   n-1
 7           intj=i-1;                          // c3   n-1
 8           while( j>=0 && a[j]>key ){         // c4   sum of ti
 9           a[j+1]=a[j];                       // c5   sum of (ti-1)
10           j--;                               // c6   sum of (ti-1)
11       }
12      a[j+1]=key;                             // c7    n-1
13      }
14 }