文档介绍：第十章. 内部排序(Chapter 10. Internal Sorting)
排序又称分类,是计算机中最重要的操作,它是将一个数据元素(或记录)的任意序列排列成一个按关键字有序的序列。
若待排序列中存在两个或以上关键字相等的记录,设Ki=Kj (1≤i < j≤n),即排序前 Ri 在 Rj 前,若在排序后 Ri 仍在 Rj 前,则称排序是稳定的。
稳定的排序方法(stable sorting method)
排序(sorting)
不稳定的排序方法(unstable sorting method)
待排序列中存在两个或以上关键字相等的记录,设Ki=Kj (1≤i < j≤n),即排序前 Ri 在 Rj 前,若在排序后 Rj 却在 Ri前,则称排序是不稳定稳定的。
内部排序(internal sorting)
待排序列记录全部存放在计算机随机存储器中进行排序的过程称为内部排序。
外部排序(external sorting)
待排序列记录数量太大,不能全部存放在计算机随机存储器中,排序过程中需对计算机外存进行访问,这种排序过程称为外部排序。
1、比较操作:比较两个关键字值的大小的操作。
排序过程中的两种基本操作:
2、移动操作:将记录从一个位置移动到另一个位置的操作。
待排序列的三种存储结构:
1、顺序存储:存储在地址连续的一组存储单元中(以此为例)。
2、链式存储:存储在地址不连续的一组存储单元(链表)中。
3、地址存储:记录顺序存储,另设关键字和记录地址排序。
typedef struct {
keytype key;
. . . . . .
} elemtype;
typedef struct {
elemtype * elem;
int length;
} sqlist;
§ 插入排序
一、直接插入排序:
直接插入排序(straight insertion sort)是一种最简单的排序方法:将记录一个个插入到已排序好的有序表中,从而得到长度增加的新的有序表。
void straightinsertsort ( sqlist & R )
{
for ( i = 2 ; i <= ; i++ ) if ( [i].key < [i-1].key )
{
[ 0 ] = [ i ] ;
[ i ] = [ i-1 ] ;
for ( j=i-2 ; [0].key < [j].key ; j-- )
[ j+1] = [ j ];
[ j+1 ] = [ 0 ] ;
}
}
排序性能分析:
比较次数: 最好情况— n-1 最坏情况—(n+2)(n-1)/2
平均比较次数: (n+4)(n-1)/4
二、折半插入排序:
折半插入排序(binary insertion sort)与直接插入排序不同之处在于查找插入位置时不是用顺序查找,而是用折半查找。
可见,直接插入排序的时间复杂度为 O(n 2)。但在待排序列有序的的情况下,直接插入排序的时间复杂度下降为 O(n)。
移动次数: 最好情况— 0 最坏情况—(n+4)(n-1)/2
平均移动次数: (n+4)(n-1)/4
折半插入排序的移动次数与直接插入排序相同,只是比较次数少了,因此其时间复杂度也为 O(n 2)。
三、2-路插入排序:
2-路插入排序目的是为了减少排序过程中移动记录的次数,代价是需要 n 个记录的辅助空间 d :将 r[1] 赋值给 d[1],将 d 看成循环的,其它记录均与 d[1] 比较,比其小则在 d[1] 前插入,反之则在 d[1] 后插入。
2-路插入排序的移动次数大约为 n 2 / 2,因此其时间复杂度仍为 O(n 2)。
四、表插入排序:
表插入排序需附设一个指针域,通过改变指针的值来达到不移动记录而得到排序结果的目的。
表插入排序是用改变指针来代替移动记录操作,因此其时间复杂度还为 O(n 2)。
表插入排序的结果是形成了链表,因此查找时只能用顺序查找,为能使用折半查找,需对记录重新排序,但这不影响其时间复杂度。
五、希尔排序:
希尔排序(Shell’s method),又称为“缩小增量排序”(diminishing increment sort),是一种比较复杂的插入排序。
希尔排序的思想是:用一定的增量间隔将待排序列分成多个组,每组都采用简单插入排序;排序完一遍后,缩小增量间隔,再对新的分组采用简单插入排序;反复此过程,直至增量间隔为 1 ,即整个待排序列为