10_新第十章内部排序试卷.ppt

概述
插入排序
直接插入排序
希尔排序
交换排序
起泡排序
快速排序
第十章内部排序
归并排序
选择排序
简单选择排序
堆排序
基本术语
将一个数据元素(记录)的任意序列,重新排列成一个按关键字有序的序列。
- 排序
- 稳定性
内部排序/外部排序
基本操作
- 约定
●概述
关键字相同的记录在排序过程中是否保持前后次序不变。
排序过程全在内存中进行
(1)比较关键字的大小;(2)移动记录。
#define MAXSIZE 20
typedef int KeyType;
typedef struct{
KeyType key;
InfoType otherinfo;
}RedType;
typedef struct{
RedType r[MAXSIZE+1];
int length;
}SqList;
插入排序
直接插入排序
●直接插入排序
●基本思想:每次将一个记录插入到已排好序的有序表中,直到记录全部插入为止。
例1:已知待排序的记录的初始排列如下
R(49), R(38), R(65), R(97), R(76) ,R(13), R(27), R(49*)
R(49)
R(38) R(49)
R(38) R(49) R(65)
R(38) R(49) R(65) R(97)
R(38) R(49) R(65) R(76) R(97)
R(13) R(38) R(49) R(65) R(76) R(97)
R(13) R(27) R(38) R(49) R(65) R(76) R(97)
R(13) R(27) R(38) R(49) R(49*) R(65) R(76) R(97)
插入排序
算法
●直接插入排序
●算法
void InsertSort(SqList &L) {
for(i=2;i<=;++i)
if LT([i].key, [i-1].key){
[0]=[i];
for( j=i-1; LT([0].key, [j].key);--j)
[j+1]=[j];
[j+1]=[0];
}
}
例子
R(49)
[0] [1] [2] [3] [4] [5] [6] [7] [8]
R(49) R(38) R(65) R(97) R(76) R(13) R(27) R(49*)
2
3
4
5
6
7
8
R(49) R(38) R(65) R(97) R(76) R(13) R(27) R(49*)
R(38)
R(49)
R(38) R(49) R(65) R(97) R(76) R(13) R(27) R(49*)
R(65)
R(49)
R(38) R(49) R(65) R(97) R(76) R(13) R(27) R(49*)
R(97)
R(49)
R(38) R(49) R(65) R(76) R(97) R(13) R(27) R(49*)
R(76)
R(49)
R(13) R(38) R(49) R(65) R(76) R(97) R(27) R(49*)
R(13)
R(49)
R(13) R(27) R(38) R(49) R(65) R(76) R(97) R(49*)
R(27)
R(49)
R(13) R(27) R(38) R(49) R(49*) R(65) R(76) R(97)
R(49*)
R(49) R(49) R(65) R(97) R(76) R(13) R(27) R(49*)
R(38)
R(38) R(49) R(65) R(97) R(76) R(13) R(27) R(49*)
R(38)
i
稳定的排序方法
插入排序
算法效率
●直接插入排序
void InsertSort(SqList &L) {
for(i=2;i<=;++i)
if LT([i].key, [i-1].key){
[0]=[i];
for( j=i-1; LT([0], [j].key);--j)
[j+1]=[j];
[j+1]=[0];
} }
●算法效率
插入排序
希尔排序
●希尔排序
●基本思想:先将待排序记录序列分割成若干子序列分别进行