例10.2设待排序的表有10个记录.其关键字分别为说明采用希尔排序方法进行排序9,8,7,6,5,4,3,2,1,0。1的过程。89（连线部分为下一趟作准备）762初始状态03298765（d=5执行结果）40d=580235679 (d=2 执行结果)d=241-18679 (d=1执行结果)023451d-116
16 例10.2 设待排序的表有10个记录,其关键字分别为 {9,8,7,6,5,4,3,2,1,0}。说明采用希尔排序方法进行排序 的过程。 初始状态 9 8 7 6 5 4 3 2 1 0 (连线部分为下一趟作准备) d=5 4 3 2 1 0 9 8 7 6 5 (d=5 执行结果) d=2 0 1 2 3 4 5 6 7 8 9 (d=2 执行结果) d=1 0 1 2 3 4 5 6 7 8 9 (d=1 执行结果)
10.3交换排序交换排序的基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。两种交换排序(1)冒泡排序(2)快速排序17
17 10.3 交换排序 交换排序的基本思想：两两比较待排序记录的关 键字,发现两个记录的次序相反时即进行交换,直到 没有反序的记录为止。 两种交换排序: (1)冒泡排序 (2)快速排序
11. 3. 1冒泡排序冒泡排序的基本思想是：通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”整个算法是从最下面的记录开始，对每两个相邻的关键字进行比较，且使关键字较小的记录换至关键字较大的记录之上，使得经过一趟冒泡排序后，关键字最小的记录到达最上端，接看，再在剩下的记录中找关键字次小的记录，并把它换在第二个位置上。依次类推一直到所有记录都有序为正18
18 11.3.1 冒泡排序 冒泡排序的基本思想是： 通过无序区中相邻记录关键字间的比较和位置的 交换,使关键字最小的记录如气泡一般逐渐往上“漂 浮”直至“水面” 。 整个算法是从最下面的记录开始,对每两个相邻的 关键字进行比较,且使关键字较小的记录换至关键字 较大的记录之上,使得经过一趟冒泡排序后,关键字最 小的记录到达最上端,接着,再在剩下的记录中找关键 字次小的记录,并把它换在第二个位置上。依次类推, 一直到所有记录都有序为止
假设在排序过程中，记录序列R[0.n-1的状态为n-i+1无序序列R[O..n-i+1]有序序列R[n-i+2..n-1众众众众众众比较相邻记录，将关键字第i起泡排序最大的记录交换到n-i+1的位置上有序序列R[n-i+1..n-1]无序序列R[O..n-i19
19 假设在排序过程中，记录序列R[0.n-1]的状态为： 第 i 趟起泡排序 无序序列R[0.n-i+1] 有序序列 R[n-i+2.n-1] n-i+1 无序序列R[0.n-i] 有序序列 R[n-i+1.n-1] 比较相邻记录，将关键字 最大的记录交换到 n-i+1 的位置上
例10.3设待排序的表有10个记录，其关键字分别1为,9,8,7,6,5,4,3,2,1,01。说明采用冒泡排序方法进行排序的过程。98753210初始关键字649832i=07654119i-183206547293i=285076413985i=30764249875i=4023615902386i=5714回09812357i=64团012569834i=7图0123569i=84720
20 例10.3 设待排序的表有10个记录,其关键字分别 为{9,8,7,6,5,4,3,2,1,0}。说明采用冒泡排序方法进行 排序的过程。 初始关键字 9 8 7 6 5 4 3 2 1 0 i=0 0 9 8 7 6 5 4 3 2 1 i=1 0 1 9 8 7 6 5 4 3 2 i=2 0 1 2 9 8 7 6 5 4 3 i=3 0 1 2 3 9 8 7 6 5 4 i=4 0 1 2 3 4 9 8 7 6 5 i=5 0 1 2 3 4 5 9 8 7 6 i=6 0 1 2 3 4 5 6 9 8 7 i=7 0 1 2 3 4 5 6 7 9 8 i=8 0 1 2 3 4 5 6 7 8 9