数据结构（九）——排序

排序

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

排序的稳定性

假设ki=kj(1≤i≤n, 1≤j≤n, i≠j），且在排序前的序列中ri领先于rj（即i<j）。如果排序后ri仍领先于rj，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中rj领先ri，则称所用的排序方法是不稳定
的

内排序与外排序

根据在排序过程中待排序的记录是否全部被放置在内存中，排序分为：内排序和外排序。

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

对于内排序来说，排序算法的性能主要是受3个方面影响：

1. 时间性能

   高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。

2. 辅助空间

   辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间。

3. 算法的复杂性

   注意这里指的是算法本身的复杂度，而不是指算法的时间复杂度。

排序的方法

1. 冒泡排序

冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

2. 选择排序

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

3. 插入排序

直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

4. 希尔排序

希尔排序（ShellSort）先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序

5. 堆排序

堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。

6. 归并排序

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

7. 快速排序

快速排序（Quick Sort）的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

排序方法具体实现 https://www.jianshu.com/p/aa437deec1a1