2.2-1:
Θ (n3)2.2-2:插入排序
void selectionSort(int a[], int n) { int i, j, k, key; for(i=0; i<n-1; i++) { k = i; for(j=i+1; j<n; j++) if(a[k] > a[j]) k = j; if(k != i) { key = a[k]; a[k] = a[i]; a[i] = key; } } }
最佳情况：Θ(n2)
最差情况：Θ(n2)
2.2-3:线性排序
平均情况：n/2
最差情况：n
2.2-4:
方法：首先判断是否已满足完成条件，则在最佳情况下程序可以有更好的效果。
原文：http://www.cnblogs.com/xuanzhang/p/4641257.html
