所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
1．被排序对象--文件被排序的对象--文件由一组记录组成。记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键字(Key)。注意：在不易产生混淆时，将关键字项简称为关键字。
2．排序运算的依据--关键字用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。关键字的选取应根据问题的要求而定。在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录，则必须用准考证号作为关键字。若要按照考生的总分数排名次，则需用总分数作为关键字。
排序的稳定性当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。注意：排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。
排序方法的分类1．按是否涉及数据的内、外存交换分在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序(简称内排序)；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。注意：①内排序适用于记录个数不很多的小文件②外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。
2．按策略划分内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。
排序算法分析1．排序算法的基本操作大多数排序算法都有两个基本的操作：(1)比较两个关键字的大小；(2)改变指向记录的指针或移动记录本身。注意：第(2)种基本操作的实现依赖于待排序记录的存储方式。
2．待排文件的常用存储方式（1）以顺序表(或直接用向量)作为存储结构排序过程：对记录本身进行物理重排（即通过关键字之间的比较判定，将记录移到合适的位置）（2）以链表作为存储结构排序过程：无须移动记录，仅需修改指针。通常将这类排序称为链表(或链式)排序；（3）用顺序的方式存储待排序的记录，但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表)排序过程：只需对辅助表的表目进行物理重排（即只移动辅助表的表目，而不移动记录本身）。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。
3．排序算法性能评价（1）评价排序算法好坏的标准评价排序算法好坏的标准主要有两条：①执行时间和所需的辅助空间②算法本身的复杂程度（2）排序算法的空间复杂度若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。非就地排序一般要求的辅助空间为O(n)。（3）排序算法的时间开销大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。
文件的顺序存储结构表示[cpp]viewplaincopy
#definenl00//假设的文件长度，即待排序的记录数目
typedefintKeyType；//假设的关键字类型
typedefstruct{//记录类型
KeyTypekey；//关键字项
InfoTypeotherinfo；//其它数据项，类型InfoType依赖于具体应用而定义
}RecType；
typedefRecTypeSeqList[n+1]；//SeqList为顺序表类型，表中第0个单元一般用作哨兵
注意：若关键字类型没有比较算符，则可事先定义宏或函数来表示比较运算。关键字为字符串时，可定义宏#defineLT(a，b)(Stromp((a)，(b))0)。那么算法中ab可用LT(a，b)取代。若使用C++，则定义重载的算符更为方便。
插入排序(InsertionSort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。本节介绍第一种排序方法：直接插入排序。
直接插入排序基本思想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个记录，通常称增量法。插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置，须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。
一趟直接插入排序方法1．简单方法首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1≤k≤i-1)；然后将R[k．．i-1]中的记录均后移一个位置，腾出k位置上的空间插入R[i]。注意：若R[i]的关键字大于等于R[1．．i-1]中所有记录的关键字，则R[i]就是插入原位置。
2．改进的方法一种查找比较操作和记录移动操作交替地进行的方法。具体做法：将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i-1，i-2，…，1)的关键字进行比较：①若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置；②若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可完成一趟直接插入排序。
直接插入排序算法1．算法描述[cpp]viewplaincopy
voidlnsertSort(SeqListR)
{//对顺序表R中的记录R[1..n]按递增序进行插入排序
inti，j；
for(i=2;i=n；i++)//依次插入R[2]，…，R[n]
if(R[i].keyR[i-1].key){//若R[i].key大于等于有序区中所有的keys，则R[i]
//应在原有位置上
R[0]=R[i];j=i-1;//R[0]是哨兵，且是R[i]的副本
do{//从右向左在有序区R[1．．i-1]中查找R[i]的插入位置
R[j+1]=R[j]；//将关键字大于R[i].key的记录后移
j--；
}while(R[0].keyR[j].key)；//当R[i].key≥R[j].key时终止
R[j+1]=R[0]；//R[i]插入到正确的位置上
}//endif
}//InsertSort
2．哨兵的作用算法中引进的附加记录R[0]称监视哨或哨兵(Sentinel)。哨兵有两个作用：①进入查找(插入位置)循环之前，它保存了R[i]的副本，使不致于因记录后移而丢失R[i]的内容；②它的主要作用是：在查找循环中监视下标变量j是否越界。一旦越界(即j=0)，因为R[0].key和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件j=1)。注意：①实际上，一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。单链表中的头结点实际上是一个哨兵②引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。
给定输入实例的排序过程设待排序的文件有8个记录，其关键字分别为：49，38，65，97，76，13，27，49。为了区别两个相同的关键字49，后一个49的下方加了一下划线以示区别。其排序过程见
算法分析1．算法的时间性能分析对于具有n个记录的文件，要进行n-1趟排序。各种状态下的时间复杂度：┌─────────┬─────┬──────┬──────┐│初始文件状态│正序│反序│无序(平均)│├─────────┼─────┼──────┼──────┤│第i趟的关键│1│i+1│（i-2）/2││字比较次数││││├─────────┼─────┼──────┼──────┤│总关键字比较次数│n-1│(n+2)(n-1)/2│≈n2/4│├─────────┼─────┼──────┼──────┤│第i趟记录移动次数│0│i+2│（i-2）/2│├─────────┼─────┼──────┼──────┤│总的记录移动次数│0│(n-1)(n+4)/2│≈n2/4│├─────────┼─────┼──────┼──────┤│时间复杂度│0（n）│O（n2）│O（n2）│└─────────┴─────┴──────┴──────┘注意： 初始文件按关键字递增有序，简称正序。 初始文件按关键字递减有序，简称反序。
2．算法的空间复杂度分析算法所需的辅助空间是一个监视哨，辅助空间复杂度S(n)=O(1)。是一个就地排序。
3．直接插入排序的稳定性直接插入排序是稳定的排序方法。
石家庄治疗白癜风的医院北京比较好白癜风医院