【数据结构】排序1——排序的概述分类、存储结构定义

---

排序概述

• 排序的定义：

将一组杂乱无章的数据按一定规律顺次排列起来。即将无序序列排成一个有序序列(由小到大或由大到小)的运算。
如果参加排序的数据结点包含多个数据域，那么排序往往是针对其中某个域而言。

• 排序方法的分类：

1、按数据存储介质：内部排序和外部排序
① 内部排序：数据量不大、数据在内存，无需内外存交换数据
② 外部排序：数据量较大、数据在外存(文件排序)
外部排序时，要将数据分批调入内存来排序，中间结
果还要及时放入外存，显然外部排序要复杂得多。

2、按比较器个数：串行排序和并行排序
① 串行排序：单处理机(同一时刻比较对元素)
② 并行排序：多处理机(同一时刻比较多对元素)

3、按主要操作：比较排序和基数排序
① 比较排序：用比较的方法，eg：插入排序、交换排序、选择排序、归并排序
② 基数排序：不比较元素的大小，仅仅根据元素本身的取值确定其有序

4、按辅助空间：原地排序和非原地排序
① 原地排序：辅助空间用量为O(1 )的排序方法。
(所占的辅助存储空间与参加排序的数据量大小无关)
② 非原地排序：辅助空间用量超过0(1)的排序方法。

5、按稳定性：稳定排序和非稳定排序
① 稳定排序：能够使任何数值柚等的元素，排序以后相对次序不变，如：直接插入排序法。
排序的稳定性只对结构类型数据排序有意义。
结构类型数据：数据中包含多个数据项。
② 非稳定性排序：不是稳定排序的方法，如：简单选择排序法。
排序方法是否稳定，并不能衡量一个排序算法的优劣。

6、按自然性：自然排序和非自然排序
① 自然排序：输入数据越有序，排序的速度越快的排序方法。
② 非自然排序：不是自然排序的方法，输入数据越有序，排序的速度越慢的排序方法。

• 排序的应用：

非常广泛
软件中直接应用
程序中间接应用
二分法查找
最短路径、最小生成树

存储结构——记录序列以顺序表存储

#define MAXSIZE 20//设记录不超过20个
typedef int KeyType;//设关键字为整型量（int型）

Typedef struct{//定义每个记录（数据元素）的结构
	KeyType key;//关键字
	InfoType otherinfo;//其它数据项
}RedType;

Typedef struct{//定义顺序表的结构
	RedType r[MAXSIZE+1];//存储顺序表的向量
	//r[0]一般作哨兵或缓冲区
	int length;//顺序表的长度
}SqList;
1
2
3
4
5
6
7
8
9
10
11
12
13

…

---