《数据结构》大型作业报告书
专业:计算机科学与技术
班级：
姓名：
学号：
指导教师：
报告日期:2007-09-08
内部排序算法研究
一 内部排序算法研究的内容与要求
（1）设 n 个关键字均为整数(1≤n≤100000)
（2）设计 K 个内部排序算法(K≥5), 每个算法须记录执行所需的时间
（3）自动生成多组数据,每组数据含 n 个整数 (正序、逆序、随机分布)
（4）执行每个排序算法
（5）用图、表格数据分析说明在什么情况采用什么算法较好;
二 数据结构及其存储结构
以顺序表为存储结构
typedef struct
{
int key; /*关键字*/
int K[5]; /*关键字的数字组合*/
int next; /*下一个元素的位置*/
}RedType; 定义存储结构的数据元素。
typedef struct
{
RedType r[MAXSIZE+1]; /*数据元素数组*/
int length; /*数据元素的个数*/
}SqList; 定义指向存储结构的数据类型包括存储结构的数组和数据元素的个数 。
三 主要算法的设计思想
（一）简单排序
一 直接插入排序
设有 n 个记录，存放在数组 r 中，重新安排记录在数组中的存放顺序，使得按关键码有
序。即
r[1].key≤r[2].key≤……≤r[n].key
1、基本思想
假设待排序的记录存放在数组 R[1..n]中。初始时，R[1]自成 1 个有序区，无序区为
R[2..n]。从 i=2 起直至 i=n 为止，依次将 R[i]插入当前的有序区 R[1..i-1]中，生成含 n 个记
录的有序区。
2、第 i-1 趟直接插入排序：
通常将一个记录 R[i](i=2，3 …， ，n-1)插入到当前的有序区，使得插入后仍保证该区
间里的记录是按关键字有序的操作称第 i-1 趟直接插入排序。
排序过程的某一中间时刻，R 被划分成两个子区间 R[1．．i-1]（已排好序的有序区）
和 R[i．．n]（当前未排序的部分，可称无序区）。
直接插入排序的基本操作是将当前无序区的第 1 个记录 R[i]插人到有序区 R[1．．i-1]
中适当的位置上，使 R[1．．i]变为新的有序区。因为这种方法每次使有序区增加 1 个记
R[MAXSI
ZE+1]
length
R[1] r[2] r[3] r[4] r[5] ................................ . R[n]
录，通常称增量法。
插入排序与打扑克时整理手上的牌非常类似。摸来的第 1 张牌无须整理，此后每次从
桌上的牌(无序区)中摸最上面的 1 张并插入左手的牌(有序区)中正确的位置上。为了找到这
个正确的位置，须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。
【算法】
void InsertSort(S_TBL &p)
{ for(i=2；i<=p->length；i++)
if(p->elem[i].key < p->elem[i-1].key) /*小于时，需将 elem[i]插入有序表*/
{ p->elem[0].key=p->elem[i].key； /*为统一算法设置监测*/
for(j=i-1；p->elem[0].key < p->elem[j].key；j--)
p->elem[j+1].key=p->elem[j].key； /*记录后移*/
p->elem[j+1].key=p->elem[0].key； /*插入到正确位置*/
}
}
【程序实现】
void insertsort(SqList L)/*直接插入排序*/
{
int j,i;
for(i=2;i<=L.length;++i){
if(L.r[i].key<L.r[i-1].key){
L.r[0]=L.r[i];
for(j=i-1;L.r[0].key<L.r[j].key;--j)
L.r[j+1]=L.r[j];
L.r[j+1]=L.r[0];
}
}
}
二 折半插入排序
直接插入排序的基本操作是向有序表中插入一个记录，插入位置的确定通过对有序表中记
录按关键码逐个比较得到的。平均情况下总比较次数约为 n2/4。既然是在有序表中确定插
入位置，可以不断二分有序表来确定插入位置，即一次比较，通过待插入记录与有序表居
中的记录按关键码比较，将有序表一分为二，下次比较在其中一个有序子表中进行，将子
表又一分为二。这样继续下去，直到要比较的子表中只有一个记录时，比较一次便确定了
插入位置。
二分判定有序表插入位置方法：
① low=1；high=j-1；r[0]=r[j]； // 有序表长度为 j-1，第 j 个记录为待插入记录
//设置有序表区间，待插入记录送辅助单元
② 若 low>high ⑤，得到插入位置，转
③ low≤high，m=(low+high)/2； // 取表的中点，并将表一分为二，确定待插入区间*/
④ 若 r[0].key<r[m].key，high=m-1； //插入位置在低半区
否则，low=m+1； // 插入位置在高半区
②转
⑤ high+1 即为待插入位置，从 j-1 到 high+1 的记录，逐个后移，r[high+1]=r[0]；放置待插
入记录。
【算法】
void InsertSort(S_TBL *s)
{ /* 对顺序表 s 作折半插入排序 */
for(i=2；i<=s->length；i++)
{ s->elem[0]=s->elem[i]； /* 保存待插入元素 */
low=i；high=i-1； /* 设置初始区间 */
while(low<=high) /* 该循环语句完成确定插入位置 */
{ mid=(low+high)/2；
if(s->elem[0].key>s->elem[mid].key)
low=mid+1； /* 插入位置在高半区中 */
else high=mid-1； /* 插入位置在低半区中 */
}/* while */
for(j=i-1；j>=high+1；j--) /* high+1 为插入位置 */
s->elem[j+1]=s->elem[j]； /* 后移元素，留出插入空位 */
s->elem[high+1]=s->elem[0]； /* 将元素插入 */
}/* for */
}/* InsertSort */
【程序实现】
void binsertsort(SqList L)/*折半插入排序*/
{
int i,j,low,high,m;
for(i=2;i<=L.length;++i){
L.r[0]=L.r[i];
low=1;high=i-1;
while(low<=high){
m=(low+high)/2;
if(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];
}
}
【时间效率】
此方法和直接插入排序所需的辅助空间相同，从时间上比较，仅减少了关键字比较的次
数，记录的移动次数不变。所以，时间和空间复杂度都和直接插入排序相同。故时间复杂
评论1