一、基本概念和排序方法概论
1.什么是排序？
将一组杂乱无章的数据按一定规律顺次排列起来。
即，将无序序列排成一个有序序列（由小到大或由大到小）的运算。
注：如果参加排序的数据结点包含多个数据域，那么排序往往是针对其中某个域而言的。
2.排序的应用非常广泛
1）软件中直接应用（资源管理器：文件名称、修改日期、大小，方便查找，数据处理软件，淘宝）
2）程序中间接应用
二分查找、最短路径、最小生成树
…
3.排序方法的分类
1）按数据存储介质可分为：
内部排序：数据量不大，数据在内存，无需内外交换数据
外部排序：数据量大，数据在外存（分批）
2）按比较器个数：
串行排序：同一时刻比较一对元素
并行排序：同一时刻比较多对元素
3）按主要操作：
比较排序：用比较的方法（插入、交换、选择、归并）
基数排序：不比较元素的大小，仅仅根据元素本身的取值确定其有序位置。
4）按辅助空间：
原地排序：辅助空间用量为O(1)的排序方法，不需要额外的空间。
非原地排序：辅助空间用量超过O(1)的排序方法
5）按稳定性：
稳定排序：能够使任何数值相等的元素，排序以后相对次序不变。
非稳定排序：不是稳定排序的方法。
eg:
原始数据：49，97，76，13，27，49'
直接插入排序法结果：13，27，49，49'，76，97
简单选择排序法结果：13，27，49'，49，76，97
排序稳定的意义：
排序稳定性只对包含多个数据域的数据结点有意义。
eg:
n个学生信息（学号、姓名、语文、数学、英语、总分）
a.按数学成绩从高到低排序
b.按照总分从高到低排序
c.总分相同情况下，数学成绩高的排在前面
6）按自然性：自然排序和非自然排序
