例12设待排序的表有10个记录,其关键字分别为 {9,8,7,6,54,3,2,1,0}。说明采用希尔排序方法进行排序的过程。 初始状态98 0(连线部分为下一趟作准备) d=5 098765(d=5执行结果) d=2 23456789(d=2执行结果) d=1 0 23456789(d=1执行结果)
例11.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 执行结果)
11.3交换排序 交换排序的基本思想:两两比较待排序记录的关键字,发现 两个记录的次序相反时即进行交换直到没有反序的记录为 止 两种交换排序: 1)冒泡排序 (2)快速排序
11.3 交换排序 交换排序的基本思想：两两比较待排序记录的关键字,发现 两个记录的次序相反时即进行交换,直到没有反序的记录为 止。 两种交换排序: (1)冒泡排序 (2)快速排序
11.3.1冒泡排序 冒泡排序的基本思想是: 通过无序区中相邻记录关键字间的比较和位置的交换,使关 键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。 整个算法是从最下面的记录开始,对每两个相邻的关键字进行 比较,且使关键字较小的记录换至关键字较大的记录之上,使得 经过一趟冒泡排序后,关键字最小的记录到达最上端接着,再在 剩下的记录中找关键字次小的记录,并把它换在第二个位置上。 依次类推一直到所有记录都有序为止 冒泡排序的算法如下:
11.3.1 冒泡排序 冒泡排序的基本思想是： 通过无序区中相邻记录关键字间的比较和位置的交换,使关 键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面” 。 整个算法是从最下面的记录开始,对每两个相邻的关键字进行 比较,且使关键字较小的记录换至关键字较大的记录之上,使得 经过一趟冒泡排序后,关键字最小的记录到达最上端,接着,再在 剩下的记录中找关键字次小的记录,并把它换在第二个位置上。 依次类推,一直到所有记录都有序为止。 冒泡排序的算法如下：
//void BubbleSort(Rec Type RIlint n) t int i,j; RecType temp; for(i=0;<n-1;i++) for(j=n-1ij>i-)/比较找本趟最小关键字的记录/ if (Rli. key<R[j-1.key) temp=Ril;R印订与R1进行交换* Rj|=R[j-1; RI-1=temp;
void BubbleSort(RecType R[],int n) { int i,j; RecType temp; for (i=0;i<n-1;i++) { for (j=n-1;j>i;j--) /*比较找本趟最小关键字的记录*/ if (R[j].key<R[j-1].key) { temp=R[j]; /*R[j]与R[j-1]进行交换*/ R[j]=R[j-1]; R[j-1]=temp; } } }
例113设待排序的表有10个记录其关键字分别为 {9,8,76,5,4,3,2,1,0}。说明采用冒泡排序方法进行排序的过程。 初始关键字9876543210 09876543 987654 i=20129876 2345 3 i=3012 9876 40123 98765 i=501234 9876 i=7012345687 798 i=801234567
例11.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