定义:
将一组杂乱无章的数据按一定规律顺次排列起来
目的:
便于查找
内部排序:
若待排序都在内存中,则称为内部排序
外部排序:
若待排序记录一部分在内存,一部分在外存,则称为外部排序。
注意:外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入外存,显然外部排序要复杂得多。
排序算法的好坏如何衡量?
时间效率—–排序速度(比较次数与移动次数)
空间效率—–占内存辅助空间的大小
稳定性——A和B的关键字相等,排序后A、B的先后次序保持不变,则称为这种排序算法是稳定的。
排序算法分类
(1)依据原则来分类
插入排序
交换排序
选择排序
归并排序
基数排序
(2)按所需的工作量分类
简单的排序方法,其时间复杂度为O(n*n)
先进的排序方法,其时间复杂度为O(nlog2n);
基数排序,其时间复杂度为O(d*n)
待排序记录的存储方式
#define MAXSIZE 20 //设记录不超过20个
typedef int KeyType; //设关键字为整数型
Typedef struct{ //定义每个记录(数据元素)的结构
KeyType Key; //关键字
InfoType otherinfo; //其他数据项
}RedType;
Typedef struct{ //定义顺序表的结构
RedType r【MAXSIZE+1】; //存储顺序表的向量
int length; //顺序表的长度
}SqList;