文档介绍：数据结构
李云清杨庆红揭安全
高等学校精品课程
人民邮电出版社
(第2版)
数据结构
揭安全
江西省高等学校精品课程
E_mail: jieanquan@
江西师范大学计算机信息工程学院
交换排序
冒泡排序
快速排序
直接选择排序
堆排序
第十章内排序
插入排序
直接插入排序
二分插入排序
希尔排序
选择排序
归并排序
基数排序
排序是数据处理过程中经常使用的一种重要的运算,排序的方法有很多种,本章主要讨论内排序的各种算法,并对每个排序算法的时间和空间复杂性以及算法的稳定性等进行了讨论。
排序的基本概念
假设一个文件是由n个记录R1,R2,…,Rn组成,所谓排序就是以记录中某个(或几个)字段值不减(或不增)的次序将这n个记录重新排列,称该字段为排序码。能唯一标识一个记录的字段称为关键码,关键码可以作为排序码,但排序码不一定要是关键码。
按排序过程中使用到的存储介质来分,可以将排序分成两大类:内排序和外排序。
内排序是指在排序过程中所有数据均放在内存中处理,不需要使用外存的排序方法。而对于数据量很大的文件,在内存不足的情况下,则还需要使用外存,这种排序方法称为外排序。
排序码相同的记录,若经过排序后,这些记录仍保持原来的相对次序不变,称这个排序算法是稳定的。否则,称为不稳定的排序算法。
评价排序算法优劣的标准:
首先考虑算法执行所需的时间,这主要是用执行过程中的比较次数和移动次数来度量;
其次考虑算法执行所需要的附加空间。
当然,保证算法的正确性是不言而喻的,可读性等也是要考虑的因素。
/****************************************/
/*常见排序算法的头文件, */
/***************************************/
#define MAXSIZE 100 /*文件中记录个数的最大值*/
typedef int keytype; /*定义排序码类型为整数类型*/
typedef struct{
keytype key;
int other; /*此处还可以定义记录中除排序码外的其他域*/
}recordtype; /*记录类型的定义*/
typedef struct{
recordtype r[MAXSIZE+1];
int length; /*待排序文件中记录的个数*/
}table; /*待排序文件类型*/
void init(table *L) /*顺序表初始化函数*/
{ int i;
srand(time(NULL));
L->length=10;
for (i=1;i<=10;i++)
L->r[i].key= rand(i)%100;
}
void print(table L) /*顺序表输出函数*/
{ int i,k=0;
for (i=1;i<=;i++)
{printf("%4d",[i].key);
if (++k%10==0) printf("\n");
}
printf("\n");
}
/*顺序表文件输入函数*/
void input(table *L,char *f)
{int i;
FILE *fp;
fp=fopen(f,"r");
if (fp)
{
fscanf(fp,"%d",&L->length);
for (i=1;i<=L->length;i++)
fscanf(fp,"%d",&L->r[i].key);
}
else
L->length=0;
}
10
50 30 20 90 10 70 80 40 60 100
一个输入文件的例子