第10章 内部排序

最坏的情况（关键码在记录序列中逆序有序）：
“比较”次数为(n+2)(n-1)/2 ，“移动”次数为(n+4)(n-1)/2 总的说来，直接插入排序所需进行关键码间的比较次数和记录移动次数均
为n2/4，所以直接插入排序的时间复杂度为O(n2)。 空间效率：需要一个记录的辅助空间，因此空间复杂度为O(1)
性能分析： 时间效率 最好的情况只需进行一趟起泡：“比较”次数为n-1，“移动”次数为0
最坏的情况需进行n-1趟起泡：“比较”的次数为
数与“比较”的次数 相同 。 “移动”次数是“交换”次数的 3倍 所以时间复杂度为：O(n2)—因为要考虑最坏情况
“交换”次
空间效率： O(1)—只在交换时用到一个缓冲单元 稳定性：稳定的
10.3.2 快速排序 基本思想：任取待排序序列中的某个元素作为基准（一般取第一个 元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元
素的排序码均小于基准元素的排序码，右子序列的排序码则大于等于基
准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列 有序。 例子：初始序列
第1次交换后 第2次交换后 第3次交换后 第4次交换后 完成一趟排序 【 46 i 【 17 i 【 17 【 17 【 17 【 17 i 05 i 05 05 13 13 42 55 i 13 13 42 42 94 94 i j 94 55 55 70 】 70 】 05 j 13 42 94 05 j 55 j 55 70 】 70 】 基准元素 55 13 42 94 05 17 j 70 】 j 70 】
例子： 初态
第一趟结果 第二趟结果
[49 38 65 97 76 13 27 49] 13[38 65 97 76 49 27 49] 13 27[65 97 76 49 38 49]
第三趟结果
13 27 38[97 76 49 65 49]
第四趟结果 13 27 38 49[76 97 65 49] 第五趟结果 13 27 38 49 49[97 65 76]
第1趟 (kd=5) 第2趟 (kd=3) 第3趟 (kd=1) 算法（略） 性能分析 ：
0
1 49
49 13 13 13 04
2 38
38 27 27 04 04 13
3 65
65 49* 49* 49* 27
4 97
97 55 55 38 38
5 76
76 04 04 27 27 49*
6 13
例子：关键字序列 T=(21，25，49，25*，16，08）
请写出冒泡排序的具体实现过程。
初态： 第1趟 第2趟 第3趟 第4趟 第5趟
21
25 49
21 25 25*
21 25
21 08
16 08
08 16
16
08 25* 49
16
25 25* 49
21
25 25* 49
21
25 25* 49
插入排序的方法：直接插入排序、折半插入排序、2-路插入排序、表
插入排序和希尔排序。 10.2.1 直接插入排序
新元素插入到哪里？ 在已形成的有序表中线性查找，并在适当位置插 入，把原来位置上的元素向后顺移。
例1：关键字序列T=（13，6，3，31，9，27，5，11）， 请写出直接插入排序的中间过程序列。
【13】, 6, 3, 31, 9, 27, 5, 11
【6, 13】, 3, 31, 9, 27, 5, 11
【3, 6, 13】, 31, 9, 27, 5, 11 【3, 6, 13，31】, 9, 27, 5, 11 【3, 6, 9, 13，31】, 27, 5, 11 【3, 6, 9, 13，27, 31】, 5, 11 【3, 5, 6, 9, 13，27, 31】, 11 【3, 5, 6, 9, 11，13，27, 31】
i j j 42 】 46 【94
算法：
int partition(SqList &L,int low,int high){
L.r[0]=L.r[low] ; //用子表的第一个记录作枢轴记录
pivotkey=L.r[low].key; //枢轴记录关键字 while(low<high){ --high; L.r[low]=L.r[high] ; //将比枢轴记录小的记录移到低端 while(low<high &&L.r[low].key<=pivotkey) //从表两端交替地向中间扫描 while(low<high &&L.r[high].key>=pivotkey)
…
{ R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d] }
其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一
趟排序8，65，97, 76, 13, 27, 49*，55, 04）， 请写出希尔排序的具体实现过程。
r[i] 初态：
}
性能分析：
时间复杂度为O(nlog2n)
空间复杂度为O(1) 稳定性：不稳定的
例如：若对21，25，49，25*，16，08进行快速排序后，25*跑到了25的前面。
10.4 选择排序
每一趟从待排序的记录中选出关键码最小的记录，顺序放在已排好序
的子序列的最后，直到全部记录排序完毕。 选择排序的方法：简单选择排序、树形选择排序、堆排序。 10.4.1 简单选择排序 基本思想：扫描整个线性表，从中选出最小的元素，将它交换到 表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。
L.r[j+1]=L.r[j]；// 记录后移 L.r[j+1]=L.r[0]；// 插入到正确位置 } }
性能分析：
时间效率 实现排序的基本操作有两个： (1)“比较”序列中两个关键码的大小；(2)“移动”记录。 对于直接插入排序： 最好的情况（关键码在记录序列中顺序有序）： “比较”次数为n-1 ，“移动”次数为0
第六趟结果
第七趟结果
13 27 38 49 49 65[97 76]
13 27 38 49 49 65 76 97
算法： void SelectSort(SqList &L)
{ //简单选择排序 for (i=1; i<L.length; ++i) { //在L.r[i..L.length] 中选择key最小的记录
算法： void Insertsort(SqList &L) { for(i=2;i<=L.length;i++)
if(LT(L.r[i]).key,L.r[i-1].key)
{ L.r[0]=L.r[i]；// 监视哨
for(j=i-1;LT(L.r[0].key,L.r[j].key;j--)
第10章 内部排序
10.1 概述
相关术语
1.排序：是计算机内经常进行的一种操作，其目的是将一组“无序”的记 录序列调整为“有序”的记录序列。 2. 排序码：作为排序依据的数据项，也即数据元素的关键码。 3. 排序算法的稳定性：是指对于两个关键码相等的记录，它们在序列中的 相对位置，在排序之前和经过排序之后，没有改变。 4. 内部排序和外部排序：若整个排序过程不需要访问外存便能完成，则称
此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列
的排序过程不可能在内存中完成，则称此类排序问题为外部排序。在本章 内我们只讨论内部排序的各种方法。
5. 内部排序的方法：插入排序、交换排序、选择排序、归并排序、基数排
序等。
10.2 插入排序
每次将一个待排序的记录，按其关键码大小插入到前面已排好序的子 序列的适当位置，直到全部记录插入为止。
low = 1; high = i-1; while (low<=high) { //在r[low..high]中折半查找插入的位置 m = (low+high)/2; // 折半 if (LT(L.r[0].key,L.r[m].key)) high = m-1; // 插入点在低半区 else low = m+1; // 插入点在高半区 } for ( j=i-1; j>=high+1; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[high+1] = L.r[0]; // 插入 } } // BInsertSort
性能分析： 时间效率
折半插入排序比直接插入排序明显地减少了关键码间的“比较”
次数，但记录“移动”的次数不变。因此，时间复杂度为O(n2) 空间效率：也只需要一个记录的辅助空间，因此空间复杂度也为O(1) 稳定性：稳定的。
10.2.3 希尔排序（又称缩小增量排序）
基本思想：对待排记录序列先作“宏观”调整，然后再作“微观”调整。 所谓“宏观”调整：指的是“跳跃式”的插入排序。具体做法为： 将记录序列分成若干子序列，分别对每个子序列进行插入排序。 所谓“微观”调整：指的是对 “基本有序”的全体记录再作最后进行一次 直接插入排序 例如：将 n 个记录{R[1]…R[n]}分成 d 个子序列： { R[1]，R[1+d]，R[1+2d]，…，R[1+kd] } { R[2]，R[2+d]，R[2+2d]，…，R[2+kd] }
k=i; for( j=i+1;j<=L.length ; j++) if ( L.r[j].key <L.r[k].key) k=j; if(k!=i) L.r[i]←→L.r[j];
} } //SelectSort
性能分析 ： 时间效率：对n个记录进行简单选择排序，所需进行的关键码间的比较次