2.2-1:
Θ (n3)2.2-2:插入排序
void selectionSort(int a[], int n)
{
int i, j, k, key; for(i=; i<n-; i++)
{
k = i;
for(j=i+; 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:
方法：首先判断是否已满足完成条件，则在最佳情况下程序可以有更好的效果。