发布时间 : 星期五 文章第10章-内部排序更新完毕开始阅读98b20a170b4e767f5bcfce05
第10章 排 序
10．1 排序的基本概念
1. 排序是数据处理的重要内容。
所谓排序是指将一个无序序列整理成按值顺序排列的有序序列。排序的方法有很多, 根据待排序序列的规模以及对数据处理的要求, 可以采用不同的排序方法。
2. 升序：值从小到大排列。 降序：值从大到小排列。
3. 内排序：整个排序过程均在内存中进行
外排序：对磁盘中的数据进行排序；
4. 排序算法的稳定性
排序可以在各种不同的存储结构上实现。在本节所介绍的排序方法中, 其排序的对象一般认为是顺序存储的线性表, 在程序设计语言中就是一维数组。
10．2 插入排序
1. 直接插入排序
所谓插入排序, 是指将无序序列中的各元素依次插入到已经有序的线性表中。 ? 算法思想
在线性表中, 只包含第 1 个元素的子表显然可以看成是有序表。然后, 从线性表的第 2 个元素开始直到最后一个元素, 逐次将其中的每一个元素插入到前面已经有序的子表中。
一般来说, 假设线性表中前 j -1 个元素已经有序, 现在要将线性表中第 j 个元素插入到前面的有序子表中, 插入过程如下 :
首先将第 j 个元素放到一个变量 T 中。然后从有序子表的最后一个元素 ( 即线性表 中第 j -1 个元素 ) 开始 , 往前逐个与 T 进行比较 , 将大于 T 的元素均依次向后移动一个位置, 直到发现一个元素不大于 T
为止, 此时就将 T( 即原线性表中的第 j 个元素 ) 插入到刚移出的空位置上, 有序子表的长度就变为 j 了。
? 以插入排序的示意图讲解插入排序的算法思想。
图 9.1 直接插入排序示意图 ( 参见教材 P228)
j i j=i-1
R[0] R[1] R[2] R[3] R[4] R[5] R[6] R[7] R[8] 初始关键字： [49] 38 65 97 76 13 27 49 i=2 ( 38 ) [38 49] 65 97 76 13 27 49 i=3 ( 65 ) [38 49 65] 97 76 13 27 49 i=4 ( 97 ) [38 49 65 97] 76 13 27 49 i=5 ( 76 ) [38 49 65 76 97] 13 27 49 i=6 ( 13 ) [13 38 49 65 76 97] 27 49 i=7 ( 27 ) [13 27 38 49 65 76 97] 49 i=8 ( 49 ) [13 27 38 49 49 65 76 97]
监视哨R[0]
直接插入排序过程示例
? 监视哨R[0]的作用： （1） 进入查找插入位置循环之前，它保存了R[i]的副本，后移数据
时不丢失
R[i]的内容。 （2） 在while循环中“监视”下标变量j是否越界，一旦越界（即j=0），
R[0]和自己比较，肯定相等，使得循环判定条件不成立，而 结束循环。
在简单插入排序中, 每一次比较后最多移掉一个逆序, 因此, 这种排序方法的效率与冒泡排序法相同。在最坏情况下, 简单插入排序需要 n(n-1)/2 次比较。
? 直接插入排序算法的 C 语言描述如下 :
Void insort ( int R[ ], int n) {
int j ,k, t；
for ( i=2；i〈=n；i ++ 〉 {
R[0]=R[i]; // 无序序列的第 1 个元素 j= i -1； // 有序序列的最后 1 个元素 while ( R[0] } } } R[ j+1] =R[j]； j--； R[ j+1] =R[0]； 2、折半插入排序 由于插入排序的基本操作是在一个有序表中进行查找和插入，因此这个“查找”操作可以利用“折半查找”来实现，由此进行的插入排序被称为折半插入排序。 R[0] R[1] R[2] R[3] R[4] R[5] R[6] R[7] R[8] 初始关键字： [49] 38 65 97 76 13 27 49 j=2 ( 38 ) [38 49] 65 97 76 13 27 49 j=3 ( 65 ) [38 49 65] 97 76 13 27 49 j=4 ( 97 ) [38 49 65 97] 76 13 27 49 j=5 ( 76 ) [38 49 65 76 97] 13 27 49 j=6 ( 13 ) [13 38 49 65 76 97] 27 49 j=7 ( 27 ) [13 27 38 49 65 76 97] 49 j=8 ( 49 ) [13 27 38 49 49 65 76 97] 监视哨R[0] 折半插入排序过程示例 Void insort ( int R[ ], int n) { int i,j ,L,h,m ； for ( i=2；i〈=n；i ++ 〉 { R[0]=R[i]; // 无序序列的第 1 个元素 L=1; h=i-1; // h是有序序列的最后 1 个元素 while ( L<= h ) { // 找插入位置 m=(L+h)/2; if(R[0]< R[m]) h=m-1; else L=m+1； } For( j=i-1;j>=h+1; --j ) //? h+1 R[ j+1] =R[j]； R[h+1]=R[0]； } } 3、希尔排序( Sheell’s Sort) 希尔排序又称缩小增量排序，它也属于插入排序类的一种排序方法，但在实际效率上较前述几种方法有较大的改进。 其基本思想是：先将整个待排序记录序列分割为若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。