for（intj=2;j=n;jt+) e=list[j];i=j-1; while (e.GetKey()<list[i].GetKey()) {1ist[i+1]=1ist[i];i--;} 1ist[i+1]=e;}) k0] k(1] k2] k[3] k4] K5] j 8 7 2 4 6 2 -0 [8] 7 2 4 6 3 -0 [7 8] 2 4 6 4 -0 [2 7 8] 4 6 5 -00 [2 4 7 8] 6 -0 [2 4 6 7 8]
for ( int j=2；j<=n；j++ ) { e = list[j]；i = j–1； while ( e. GetKey( ) < list[i]. GetKey( ) ) { list[i+1] = list[i]；i − −；} list[i+1] = e； } } k[0] k[1] k[2] k[3] k[4] k[5] j －∞ 8 7 2 4 6 －∞ [2 4 6 7 8] 2 －∞ [8] 7 2 4 6 4 －∞ [2 7 8] 4 6 3 －∞ [7 8] 2 4 6 5 －∞ [2 4 7 8] 6
·直接插入排序算法 ◆优点：是算法的执行过程相当清晰，并 ◆ 且书写容易. ◆缺点：期望复杂性为0(n) ◆稳定性：直接插入排序是稳定的排序方法。 ·最好情况是：当被排序文件初态为正序时， 算法的时间复杂度为0(n) ◆空间复杂度：0(1)
直接插入排序算法 优点:是算法的执行过程相当清晰，并 且书写容易. 缺点:期望复杂性为O(n2) . 稳定性：直接插入排序是稳定的排序方法。 最好情况是：当被排序文件初态为正序时， 算法的时间复杂度为O(n) . 空间复杂度： O(1)
8.2.2希尔排序 。希尔排序（渐减增量排序法）思想： 把记录按下标的一定增量分组，对每组使用直接 插入排序法，随着增量逐渐减少，所分成的组包 含的关键词越来越多，到增量值减至1时，整个 文件恰好被分成一个组，算法便告终止 。希尔排序增量的取法： d1=Ln/2」=L10/2」=5 d2Ld1/2」=L5/2」=2 d3=Ld2/2」=L2/2」=1
8.2.2 希尔排序 ● 希尔排序（渐减增量排序法）思想： 把记录按下标的一定增量分组，对每组使用直接 插入排序法，随着增量逐渐减少，所分成的组包 含的关键词越来越多，到增量值减至1时，整个 文件恰好被分成一个组，算法便告终止. ● 希尔排序增量的取法： d1= = =5 ∟n/2 ∟ ∟10/2 ∟ d2= = =2 ∟d1/2 ∟ ∟5/2 ∟ d3= = =1 ∟d2/2 ∟ ∟2/2 ∟
[例]将十个数进行希尔排序的示例。 下标 01234 56789 36.25.4812.6525.43…58.7632 d1=5 25 36 43 48 58 2 32 65 一趟 25254812323643587665 排序结果
[例] 将十个数进行希尔排序的示例。 0 1 2 3 4 5 6 7 8 9 36 25 48 12 65 25 43 58 76 32 下标 d1=5 36 25 25 43 48 58 12 76 65 32 25 36 32 65 一趟 25 25 48 12 32 36 43 58 76 65 排序结果
[例]将十个数进行希尔排序的示例。 下标 01234567 89 25254812323643587665 d2=2 距 32 43 48 76 12 25 36 58 65 二趙 251232254336 48587665 排序结果 三趟 12252532364348586576 排序结果 d=1
[例] 将十个数进行希尔排序的示例。 下标 0 1 2 3 4 5 6 7 8 9 d2=2 25 25 48 12 32 36 43 58 76 65 25 48 32 43 76 25 12 36 58 65 32 43 48 12 25 二趟 25 12 32 25 43 36 48 58 76 65 排序结果 三趟 12 25 25 32 36 43 48 58 65 76 排序结果 d3=1