【例10.1】设待排序表有10个元素，其关键字序列为（9，8，7，6,5，4，3，2，1，0）。说明采用直接插入排序方法进行排序的过程。初始[9]8i=1:918i=2:-9i=3:6i=4:i=5:9i=6:9=7:9=8：9i=9:11O9116/69
【例10.1】 设待排序表有10个元素，其关键字序列为（9，8，7，6， 5，4，3，2，1，0）。说明采用直接插入排序方法进行排序的过程。 初始 [9] 8 7 6 5 4 3 2 1 0 i=1： [8 9] 7 6 5 4 3 2 1 0 i=2： [7 8 9] 6 5 4 3 2 1 0 i=3： [6 7 8 9] 5 4 3 2 1 0 i=4： [5 6 7 8 9] 4 3 2 1 0 i=5： [4 5 6 7 8 9] 3 2 1 0 i=6： [3 4 5 6 7 8 9] 2 1 0 i=7： [2 3 4 5 6 7 8 9] 1 0 i=8： [1 2 3 4 5 6 7 8 9] 0 i=9： [0 1 2 3 4 5 6 7 8 9] 16/69
直接插入排序动画insert_sort17/69
17/69
2．排序算法//对R[0..n-1]递增排序public void Insertsort()RecType tmp;中int j;1/从第2个元素即R[11开始for（inti=1;i<n;i++)11反序时( if (R[i].key<R[i-1].key)tmp=R[i];//取出无序区的第一个元素j=i-1;1/有序区中从右向左找R[i插入位置do//关键字大于tmp.key的元素后移R[j+1]=R[j] ;//继续向前比较j--;} while (j>=0 && R[j].key>tmp.key)1/在j+1处插入R[i]R[j+1]=tmp;18/69
public void InsertSort() //对R[0.n-1]递增排序 { RecType tmp; int j; for (int i=1;i<n;i++) //从第2个元素即R[1]开始 { if (R[i].key<R[i-1].key) //反序时 { tmp=R[i]; //取出无序区的第一个元素 j=i-1; //有序区中从右向左找R[i]插入位置 do { R[j+1]=R[j]; //关键字大于tmp.key的元素后移 j-; //继续向前比较 } while (j>=0 && R[j].key>tmp.key); R[j+1]=tmp; //在j+1处插入R[i] } } } 2. 排序算法 18/69
算法分析3.1）最好情况分析初始数据序列正序n-1Cmin1=n-1=0(n),Mmin=0-最好情况下的时间复杂度为0(n)19/69
3. 算法分析 1）最好情况分析 初始数据序列正序 最好情况下的时间复杂度为O(n)。 19/69
2）最坏情况分析初始数据序列反序n-1n(n-1)0(n2)i=Cmax=2i=1n-1(n-1)(n +4)=0(n2)(i + 2)Mmax=2i=1最坏情况下的时间复杂度为0(n2)20/69
2）最坏情况分析 初始数据序列反序 最坏情况下的时间复杂度为O(n 2)。 20/69