|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n个元素的序列{k1, k2, …, kn｝当且仅当满足以下的关系式时才称之为堆： 或 ，并相应地称为小顶堆或大顶堆。
|
|
|
|
|
|
判断堆的办法是把序列看成一棵完全二叉树，若树中所有非终端节点的值均不大于（或不小于）其左右孩子的节点的值，则该序列为堆。
|
|
|
|
|
|
堆的典型应用是堆排序。堆排序首先要根据待排序记录的关键字建立初始堆，其方法是：将待排序的关键字按层序遍历方式分放到一棵完全二叉树的各个节点中，显然所有i>［n/2］的节点ki都没有子节点，以这样的ki为根的子树已经是堆，因此初始堆可从完全二叉树的第（i=［n/2］）个节点开始，通过调整，逐步使以k[n/2]， k［n/2]-1, …, k2, k1为根的子树满足堆的定义。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
对于n个元素的关键字序列K1,K2,…,Kn，当且仅当所有关键字都满足下列性质时称其为堆，即
|
|
|
|
|
|
若堆顶为最小元素，则称为小根堆；若堆顶为最大元素，则称为大根堆。
|
|
|
|
堆排序的基本思想是：对一组待排序记录的关键字，首先把它们按堆的定义排成一个堆序列，从而输出堆顶的最小关键字（对于小根堆而言），然后将剩余的关键字再调整成新堆，便得到次小的关键字，如此反复进行，直到全部关键字排成有序序列为止。
|
|
|
|
对于记录数较少的文件来说，堆排序的优越性并不明显，但对大量的记录来说堆排序是很有效的。堆排序的整个算法时间是由建立堆和不断调整堆这两部分时间代价构成的，堆排序算法的时间复杂度为O(nlog2n)。此外，堆排序只需要一个记录大小的辅助空间。但是堆排序是一种不稳定的排序方法。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
归并是将两个或两个以上的有序文件合并成为一个新的有序文件。
|
|
|
|
归并排序是把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件，然后进行两两归并，如此重复，直至最后形成一个包含n个记录的有序文件为止。这种反复将两个有序文件归并成一个有序文件的排序方法称为两路归并排序。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
快速排序的基本思想是：通过一趟排序将待排的记录分割为独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序。
|
|
|
|
具体做法是：附设两个指针low和high，它们的初值分别指向文件的第一个记录和最后一个记录。设枢轴记录的关键字为Pivotkey，则首先从high所指位置起向前搜索，找到第一个关键字小于Pivotkey的记录并与枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于Pivotkey的记录并与枢轴记录相互交换，重复这两步直至low=high为止。
|
|
|
|
在所有同数量级(O(nlog2n))的排序方法中，快速排序被认为是平均性能最好的一种，但是，若初始记录序列按关键字有序或基本有序时，快速排序将退化为冒泡排序，此时算法的时间复杂度为O(n2)。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n个记录进行简单选择排序的基本方法是：通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录进行交换，当i等于n时所有记录有序排列。
|
|
|
|
|
|
|
简单选择排序法在最好情况下（待排序列已按关键码有序）不需要移动元素，因此n个元素排序时的总移动次数为0次。在最坏情况下（元素已经逆序排列），每趟排序移动记录的次数都为3次（两个数组元素交换值），共进行n-1趟排序，总移动次数为3（n-1）。无论在哪种情况下，元素的总比较次数为 。
|
|
|
|
由此，简单选择排序是一种不稳定的排序方法，其时间复杂度为O（n2）。排序过程中仅需要一个元素的辅助空间用于数组元素值的交换，空间复杂度为O（1）。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n个记录进行冒泡排序的方法是：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换两个记录的值，然后比较第二个记录和第三个记录的关键字，以此类推，直至第n-1个记录和第n个记录的关键字比较完为止。上述过程称作一趟冒泡排序，其结果是关键字最大的记录被交换到第n个位置。然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是关键字次大的记录被交换到第n-1个位置。当进行完第n-1趟时，所有记录有序排列。
|
|
|
|
|
|
|
冒泡排序法在最好情况下（待排序列已按关键码有序）只需作1趟排序，元素的比较次数为n-1且不需要交换元素，因此总比较次数为n-1次，总交换次数为0次。在最坏情况下（元素已经逆序排列），进行第i趟排序时，最大的i-1个元素已经排好序，其余的n-（i-1）个元素需要进行n-i次比较和n-i次交换，因此总比较次数为 ，总交换次数为 。
|
|
|
|
由此，冒泡排序是一种稳定的排序方法，其时间复杂度为O（n2）。排序过程中仅需要一个元素的辅助空间用于元素的交换，空间复杂度为O（1）。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
假设含n个记录的文件内容为｛R1，R2，…，Rn｝，其相应的关键字为｛k1，k2，…，kn｝。经过排序确定一种排列｛Rj1，Rj2，…，Rjn｝，使得它们的关键字满足如下递增（或递减）关系：kj1≤kj2≤…≤kjn（或kj1≥kj2≥…≥kjn）。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
若设R[1...n]为待排序的n个记录，R[1...i-1]已按照主关键字由小到大排序，且任意x∈R[1...i-1]，y∈R[i...n]满足x.key≤y.key，则选择排序的主要思路如下。
|
|
|
|
（1）反复从R[i...n]中选出关键字最小的结点R[k]。
|
|
|
|
（2）若i≠k，则将R[i]与R[k]交换，使得R[1...i]有序且保持原来的性质。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
可见，选择排序不管原先序列是否有序，其排序需要比较的次数均为n(n-1)/2；同时，由于相等的两个元素，位置相对在前的可能被交换到后面，故该选择排序是不稳定的。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
直接插入排序是一种简单的排序方法，具体做法是：在插入第i个记录时，R1，R2，…，Ri-1己经排好序，这时将记录Ri的关键字ki依次与关键字ki-1，ki-2，…，k1进行比较，从而找到Ri应该插入的位置，插入位置及其后的记录依次向后移动。
|
|
|
|
|
|
|
直接插入排序法在最好情况下（待排序列已按关键码有序），每趟排序只需作1次比较且不需要移动元素，因此n个元素排序时的总比较次数为n-1次，总移动次数为0次。在最坏情况下（元素已经逆序排列），进行第i趟排序时，待插入的记录需要同前面的i个记录都进行1次比较，因此，总比较次数为 。排序过程中，第i趟排序时移动记录的次数为i+1（包括移进、移出temp），总移动次数为 。
|
|
|
|
由此，直接插入排序是一种稳定的排序方法，其时间复杂度为O（n2）。排序过程中仅需要一个元素的辅助空间，空间复杂度为O（1）。
|
|
|
|
|
|
|
|
|
|
|
|
|
