其它数据项记录类型为记录类型的数组将无序子序列中的个记录“插入”到有序序列中，从而以达到扩大有序区的长度的目的。趟排序完成个记录的插入。每趟都将无序区中的第个记录按其关键字值的大小插入到有序区中的适当位臵，直到无序区中的全部记录都插完为止。趟直接插入排序的基本思想在对记录序列的排序过程中，区段中的记录已按关键字非递减的顺序排列，将插入到有序序列中，使区段中的记录按关键字非递减顺序排列。插入排序方法有序序列无序序列趟直接插入排序的基本思想有序序列无序序列直接插入排序基于顺序查找不同的具体实现方法导致不同的算法希尔排序基于逐趟缩小增量由此实现趟插入排序的步骤为在中查找的插入位臵，即确定使得将中的记录后移个位臵将插入到的位臵。为了避免在查找过程中判别循环变量是否出界，设臵为监视哨，并方便在查找的同时进行“记录后移”，如动画演示所示。例，初始状态第遍第遍第遍第遍第遍第遍第遍监视哨直接插入排序算法实现利用“顺序查找”实现“在中查找的插入位臵”算法的实现要点从起向前进行顺序查找，监视哨设臵在对于在查找过程中找到的哪些关键字不小于的记录，并在查找的同时实现记录向后移动从起向前进行顺序查找，监视哨设臵在设臵“哨兵”循环结束表明的插入位臵为从后往前找插入位臵对于在查找过程中找到的哪些关键字不小于的记录，并在查找的同时实现记录向后移动上述循环结束后可以直接进行“插入”插入位臵令实现整个序列的排序。记录后移插入到正确位臵监视哨的作用进入查找循环之前，它保存了的副本，使得不致于因为记录的后移而丢失中的内容在循环或循环中监视下标变量是否越界，避免循环内部每次都要检测是否越界。直接插入排序的时间复杂度分析从上述排序过程可见，排序中的两个基本操作是关键字间的比较和记录的移动。因此排序的时间性能取决于排序过程中这两个操作的次数。从直接插入排序的算法可见，这两个操作的次数取决于待排记录序列的状态。当待排记录处于“正序”即记录按关键字递增排列的情况时，所需进行的关键字比较和记录移动的次数最少。每趟排序比较次，即和比较记录移动次反之，当待排记录处于“逆序”即记录按关键字递减排列的情况时，所需进行的关键字比较和记录移动的次数最多。每趟进行次比较每趟移动次数每趟除了上面的两次初始最小者交换,最小者交换,最小者交换,第趟结果第二趟结果结果最小者无交换最小者无交换各趟排序后的结果第三趟结果第四趟结果第五趟结果第趟时选择排序的过程赋初值为,只要,就把赋给，每次循环结束如果找到最小的关键字，则将赋值给，然后判断和是否相等，不等则将和交换即可双层循环指示当前序列中最小者第趟选择排序结果直接选择排序的算法描述进行趟选择排序!交换和在当前无序区中选择关键字最小的记录直接选择排序的关键字比较次数与对象的初始排列无关。第趟选择具有最小关键字对象所需的比较次数总是次，因此，总的关键字比较次数为由于每趟选择后可能要进行两个记录的交换，而每次交换都要进行次记录的移动，因此最大移动次数为,最少移动次数为。时间复杂度为。直接选择排序是种不稳定的排序方法时间性能分析交换排序起泡排序快速排序时间分析交换排序交换排序的基本思想两两比较待排序对象的关键字，如果发生逆序即排列顺序与排序后的次序正好相反，则交换之，直到所有对象都排好序为止。常用的有起泡排序和快速排序。第趟对所有记录纵向序列从下到上每相邻两个记录的关键字进行比较，如果这两个记录的关键字不符合排序要求，则进行交换，这样趟做完，将关键字最小者放在最上方的位臵上第趟对剩下的个待排序记录重复上述过程，又将个关键字放于最终位臵上方第个位臵。反复进行次，可将个关键字对应的记录放至最终位臵，剩下的即为关键字最大的记录，它放在最下方的位臵上。因此，排序至多需要趟排序。如果趟排序中没有记录交换，则说明排序可以提早结束，为此，算法设计时可以定义个变量，根据它的值判断需不需要提前结束循环。起泡排序的基本思想将关键字按纵向排列，然后自下而上地对每两个相邻的关键字进行比较，如果逆序,则交换两个记录。起泡排序例下标初始序列第趟第趟第趟第趟第趟第趟第趟待排序的个记录的排序码序列为，使用冒泡下沉排序算法进行的排序过程如下图所示时间性能分析最好的情况关键字在记录序列中递增有序只需进行趟起泡“比较”的次数最坏的情况关键字在记录序列中逆序有序需进行趟起泡“比较”的次数“移动”的次数“移动”的次数起泡排序需要个附加变量以实现记录值的对换。或者用起泡排序是个稳定的排序方法。冒泡排序使用说明该算法是专门针对已部分排序的数据进行排序的种排序方法。如果在你的数据清单中只有两个数据是乱序的话，用这种算法就是最快的排序算法。如果你的数据清单中的数据是随机排列的，那么这种方法可能就成了最慢的算法了。例如初始序列是。则只需趟冒泡即可实现排序。但是对于。则需要扫描趟才能完成排序。原因扫描方向的单性导致了两种情况的不对称性。快速排序快速排序则是任意选定个关键字介于“中间”的记录通过趟排序使剩余记录分成两个子序列分别继续排序，通常称该记录为“基准或枢轴”。趟排序也称为次划分。假设趟快速排序之后基准记录的位臵为，则得到的无序记录子序列中记录的关键字均小于基准记录的关键字，得到的无序记录子序列中记录的关键字均大于基准记录的关键字，由此这两个子序列可分别进行快速排序。快速排序首先对无序的记录序列进行“次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无序的记录序列无序记录子序列无序子序列基准次划分分别进行快速排序趟快速排序次划分目标找个记录，以它的关键字作为“基准”，凡其关键字小于基准的记录均移动至该记录之前，反之，凡关键字大于基准的记录均移动至该记录之后。致使趟排序之后，记录的无序序列将分割成两部分和，且基准。了解排序的定义和各种排序方法的特点。熟悉各种方法的排序过程及其依据的原则。掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较和移动次数”分析排序算法的平均情况和最坏情况的时间性能，熟悉各种算法的适用场合。理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。本章学习要求第章排序排序的基本概念插入排序选择排序交换排序归并排序概述排序的定义二内部排序和外部排序三内部排序方法的分类什么是排序排序整理文件中的记录，将组杂乱无章的数据排列成个按关键字有序的序列。排序是计算机内经常进行的种操作，其目的是将组“无序”的记录序列调整为“有序”的记录序列。例如将下列关键字序列,调整为,般情况下，假设含个记录的序列为，其相应的关键字序列为，这些关键字相互之间可以进行比较，即在它们之间存在着这样个关系按此固有关系将上式记录序列重新排列为，的操作称作排序。数据表待排序数据对象的有限集合。关键字通常数据对象有多个属性域，即多个数据成员组成，其中有个属性域可用来区分对象，作为排序依据。该域即为关键字。每个数据表用哪个属性域作为关键字，要视具体的应用需要而定。即使是同个表，在解决不同问题的场合也可能取不同的域做关键字。主关键字如果在数据表中各个对象的关键字互不相同，这种关键字即主关键字。按照主关键字进行排序，排序的结果是唯的。次关键字数据表中有些对象的关键字可能相同，这种关键字称为次关键字。按照次关键字进行排序，排序的结果可能不唯。即若待排序的序列中存在两个或两个以上关键字相等的记录，则排序所得到的结果不唯。排序算法的稳定性如果在对象序列中有两个对象和，它们的关键字，且在排序之前，对象排在前面。如果在排序之后，对象仍在对象的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。二内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。排序的时间开销排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。各节给出算法运行时间代价的大略估算般都按平均情况进行估算。对于那些受对象关键字序列初始排列状态及对象个数影响较大的，需要按最好情况和最坏情况进行估算。衡量排序方法的标准排序时所需要的平均比较次数排序时所需要的平均移动次数排序时所需要的平均辅助存储空间三内部排序的方法内部排序的过程是个逐步扩大记录的有序序列长度的过程。大多数排序方法在排序过程中将出现如图所示“有序”和“无序”两个区域。经过趟排序有序序列区无序序列区有序序列区无序序列区其中有序区内的记录已按关键字递增有序排列，而无序区内为待排记录。通常称“使有序区中记录数目增加个或几个”的操作过程为“趟排序”。按何种策略扩大有序区域将导致不同的排序方法。内部排序方法大致可分下列几种类型插入类交换类选择类归并类待排序的记录序列可以用顺序表表示，也可以用链表表示。本章讨论的排序算法律以顺序表数组为操作对象。待排记录的数据类型定义如下待排顺序表最大长度关键字项其它数据项记录类型为记录类型的数组将无序子序列中的个记录“插入”到有序序列中，从而以达到扩大有序区的长度的目的。趟排序完成个记录的插入。每趟都将无序区中的第个记录按其关键字值的大小插入到有序区中的适当位臵，直到无序区中的全部记录都插完为止。趟直接插入排序的基本思想在对记录序列的排序过程中，区段中的记录已按关键字非递减的顺序排列，将插入到有序序列中，使区段中的记录按关键字非递减顺序排列。插入排序方法有序序列无序序列趟直接插入排序的基本思想有序序列无序序列直接插入排序基于顺序查找不同的具体实现方法导致不同的算法希尔排序基于逐趟缩小增量由此实现趟插入排序的步骤为在中查找的插入位臵，即确定使得将中的记录后移个位臵将插入到的位臵。为了避免在查找过程中判别循环变量是否出界，设臵为监视哨，并方