|
|
|
|
|
排序：假设含n个记录的文件内容为{R1,R2,…,Rn}，其相应的关键字分别为{K1,K2，…,Kn}。经过排序确定一种排列：Ri1,Ri2,…,Rin，使得它们的关键字满足关系Ki1≤Ki2≤…≤Kin（或Ki1≥Ki2≥…≥Kin），这样的运算称为排序。
|
|
|
|
内部排序：指待排序记录全部存放在内存中排序的过程。
|
|
|
|
外部排序：指待排序记录的数量很大，以至内存不能容纳全部记录，在排序过程中尚需对外存进行访问的过程。
|
|
|
|
|
|
|
|
（1）直接插入排序。在插入第i个记录时，R1,R2,…,Ri-1已经排好序，这时将关键字ki依次与关键字ki-1,ki-2,…，k1进行比较，从而找到应该插入的位置，然后将ki插入，插入位置及其后的记录依次向后移动。
|
|
|
|
（2）冒泡排序。首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换两个记录的值，然后比较第二个记录和第三个记录的关键字，以此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称为第一趟冒泡排序，其结果是关键字最大的记录被安置到第n个记录的位置上，然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是关键字次大的记录被安置到第n-1个记录的位置上，当进行完第n-1趟时，所有记录有序排列。
|
|
|
|
（3）简单选择排序。通过n-1次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换，当i等于n时所有记录有序排列。
|
|
|
|
|
|
希尔排序又称为缩小增量排序，是对直接插入排序方法的改进。
|
|
|
|
希尔排序的基本思想是：先将整个待排记录序列分割成若干个子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。具体做法是：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，将所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d2<d1，重复上述分组和排序工作，以此类推，直至所取的增量di=1(di<di-1<…<d21)，即所有记录放在同一组进行直接插入排序为止。
|
|
|
|
|
|
快速排序的基本思想是：通过一趟排序将待排的记录分割为独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序。
|
|
|
|
具体做法是：附设两个指针low和high，它们的初值分别指向文件的第一个记录和最后一个记录。设枢轴记录的关键字为Pivotkey，则首先从high所指位置起向前搜索，找到第一个关键字小于Pivotkey的记录并与枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于Pivotkey的记录并与枢轴记录相互交换，重复这两步直至low=high为止。
|
|
|
|
在所有同数量级(O(nlog2n))的排序方法中，快速排序被认为是平均性能最好的一种，但是，若初始记录序列按关键字有序或基本有序时，快速排序将退化为冒泡排序，此时算法的时间复杂度为O(n2)。
|
|
|
|
|
|
对于n个元素的关键字序列K1,K2,…,Kn，当且仅当所有关键字都满足下列性质时称其为堆，即
|
|
|
|
|
|
若堆顶为最小元素，则称为小根堆；若堆顶为最大元素，则称为大根堆。
|
|
|
|
堆排序的基本思想是：对一组待排序记录的关键字，首先把它们按堆的定义排成一个堆序列，从而输出堆顶的最小关键字（对于小根堆而言），然后将剩余的关键字再调整成新堆，便得到次小的关键字，如此反复进行，直到全部关键字排成有序序列为止。
|
|
|
|
对于记录数较少的文件来说，堆排序的优越性并不明显，但对大量的记录来说堆排序是很有效的。堆排序的整个算法时间是由建立堆和不断调整堆这两部分时间代价构成的，堆排序算法的时间复杂度为O(nlog2n)。此外，堆排序只需要一个记录大小的辅助空间。但是堆排序是一种不稳定的排序方法。
|
|
|
|
|
|
归并是将两个或两个以上的有序文件合并成为一个新的有序文件。
|
|
|
|
归并排序是把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件，然后进行两两归并，如此重复，直至最后形成一个包含n个记录的有序文件为止。这种反复将两个有序文件归并成一个有序文件的排序方法称为两路归并排序。
|
|
|
|
|
|
基数排序的思想是：设立r个队列，队列的编号分别为0,1,2,…,r-1。首先按最低有效位的值，把n个关键字分配到这r个队列中；然后从小到大将各队列中关键字再依次收集起来；接着按次低有效位的值把刚收集起来的关键字再分配到r个队列中。重复上述收集过程，直至最高有效位，这样得到了一个从小到大有序的关键字序列。为了减少记录移动的次数，队列可以采用链式存储分配，称为链队列。每个链队列设有两个指针，分别指向队头和队尾。
|
|
|
|
对于n个记录，执行一次分配和收集的时间为O(n+r)，如果关键字有d位，则要执行d遍，所以总的运算时间为O(d(n+r))。基数排序适用于链式分配的记录的排序，是一种稳定的排序方法。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
选择排序方法时需要考虑的因素有：①待排序的记录个数n；②记录本身的大小；③关键字的分布情况；④对排序稳定性的要求；⑤语言工具的条件、辅助空间的大小。依据这些因素，可以得到以下几点结论。
|
|
|
|
.若待排序的记录数目n较小时，可采用插入排序和选择排序。
|
|
|
|
.若待排序记录按关键字基本有序，则宜采用直接插入排序或冒泡排序。
|
|
|
|
.当n很大且关键字的位数较少时，采用链式基数排序较好。
|
|
|
|
.若n较大，则应采用时间复杂度为O(nlog2n)的排序方法，如快速排序、堆排序或归并排序。
|
|
|
|
|
|
常用的外部排序法是归并排序。这种方法一般分为两个阶段：在第一阶段，把文件中的记录分段读入内存，利用某种内部排序方法对这段记录进行排序并输出到外存的另一个文件中，在新文件中形成许多有序的记录段，称为归并段；在第二阶段，对第一阶段形成的归并段用某种归并方法进行一趟趟的归并，使文件的有序段逐渐加长，直到将整个文件归并为一个有序段时为止。
|
|
|
