排序

概念

假设含有n个记录的序列为{r1，r2，……，rn}，其相应的关键字分别为{k1，k2，……，kn}，需确定1，2，……，n的一种排列p1，p2，……，pn，使其相应的关键字满足kp1≤kp2≤……≤kpn（非递减或非递增）关系，即使得序列成为一个按关键字有序的序列{rp1，rp2，……，rpn}，这样的操作就称为排序。

内排序与外排序

内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行

内排序：插入排序、交换排序、选择排序和归并排序

冒泡排序

两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止

简单选择排序

简单选择排序法（Simple Selection Sort）就是通过n－i次关键字间的比较，从n－i＋1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录交换之

直接插入排序

将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表

希尔排序

基本有序：就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间

这其实就是希尔排序的精华所在，它将关键字较小的记录，不是一步一步地往前挪动，而是跳跃式地往前移

每次都进行的是间断的跳跃式变换，而不是相邻的

堆排序

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆（例如图9-7-2左图所示）；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了

归并排序

归并排序（Merging Sort）就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到⌈n/2⌉（⌈x⌉表示不小于x的最小整数）个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。

快速排序

通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的