【数据结构与算法】——第八章：排序

 ============================ 【说明】 ===================================================
  大家好，本专栏是 数据结构与算法， 该科目是计算机类专业必修课之一，比较重要也比较基础，有想从事算法研究的同学，这些内容是专/本科、甚至硕士期间较为基础的内容，适用范围较广：大学专业课学习、考研复习等。
  通过自己的理解进行整理，希望大家积极交流、探讨，多给意见。后面也会给大家更新其他一些知识。若有侵权，联系删除！共同维护网络知识权利！

---

1、基本概念

1.1 什么是排序

   给定一个记录集合( r1,r2,…,rn)，其相应的关键码分别为(k1,k2,…,kn)，排序是将这些记录排成顺序为(rs1,rs2,…,rsn)的一个序列，使得相应的关键码满足ks1≤ks2≤…≤ksn(非降序或升序)或ks1≥ks2≥…≥ksn（非升序或降序）。

1.2 排序算法的稳定性

   若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：

      (1) 若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；
      (2) 不能保持一致的排序方法则称为不稳定的；

1.3 排序算法的分类

   (1) 内排序和外排序

   按照参加排序的数据元素（记录）是否全部放置在内存中可把排序分为内排序和外排序：

      内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。
      外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。

   (2) 单键排序和多键排序

  按照排序所依据的关键码的个数可以把排序分为单键排序和多键排序。

      单键排序：根据一个关键码进行的排序。
      多键排序：根据多个关键码进行的排序。

   (3) 基于比较和不基于比较

   按照排序的方法是否建立在关键码比较的基础上可以把排序分为：

    基于比较：主要是通过关键码之间的比较和记录的移动这两种操作来实现的排序。
    不基于比较：根据待排序数据的特点所采取的其它方法，通常是没有大量的关键码之间的比较和记录的移动操作的排序。

1.4 内排序的方法

  内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

  内排序有如下几大类:

  下面对各种排序算法做个详细介绍:

---

2、插入排序

2.1 直接插入排序

  算法思想：仅有一个记录的表总是有序的，因此，对于n个记录的表，可从第二个记录开始直到第n个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。

  步骤：
    (1) 从第一个元素开始，该元素可以认为已经被排序；
    (2) 取出下一个元素，在已经排序的元素序列中从后向前扫描；
    (3) 如果该元素（已排序）大于新元素，将该元素移到下一位置；
    (4) 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
    (5) 将新元素插入到该位置后；
    (6) 重复步骤2~5。

  算法分析：

    空间效率：仅用了一个辅助单元O(1)。
    时间效率：
      最好情况下：初始序列是顺序的
      最坏情况下：初始序列是逆序的
      平均情况下：初始序列是无序的
    稳定性：是一种稳定的排序方法。

---

2.2 直接插入排序

  算法思想：设在顺序表中有一 个对象序列 V[0], V[1], …, V[n-1]。其中, V[0], V[1], …, V[i-1] 是已经排好序的对象。在插入V[i] 时, 利用折半查找法寻找V[i] 的插入位置。

  步骤：
  折半插入排序与直接插入排序算法原理相同。只是，在向已排序的数据中插入数据时，采用来折半查找（二分查找）。先取已经排序的序列的中间元素，与待插入的数据进行比较，如果中间元素的值大于待插入的数据，那么待插入的数据属于数组的前半部分，否则属于后半部分。依次类推，不断缩小范围，确定要插入的位置。

    Step1: 顺序表中前j-1个记录有序，将第j个记录插入。令low=1；high=j-1；r[0]=r[j]；
    Step2: 若low>high，得到插入位置，转Step5;
    Step3: 若low≤high，则取有序子表的中点m=(low+high)/2；
    Step4: 若r[0].key<r[m].key，则插入位置在低半区，令high=m-1；否则插入位置在高半区，令low=m+1；转Step2;
    Step5: high+1即为待插入位置，从j-1到high+1的记录，逐个后移，r[high+1]=r[0]；放置待插入记录。

  案例：

  (1) 待排序数据：2，1，6，7，4
  取第一个元素作为有序表，剩余的元素作为无序表；其中有序表：2；无序表：1，6，7，4

  (2) 第一次比较，从无序表中取出第一个数 1，与中间值2比较，1<2，1插到2的前面，得到：有序表：1，2；无序表：6，7，4

  (3) 第二次比较，从无序表中取出第一个数 6，与中间值1比较，6>1，要放在1的后面，再与后半区（有序表：2）的中间值2比较，6>2，6插入到2的后面，得到： 有序表：1，2，6；无序表：7，4

  (4) 第三次比较，从无序表中取出第一个数 7，与中间值2比较，7>2，7放在2后面，再与后半区（有序表：6）的中间值6比较，7>6，7放在6后面，得到：有序表：1，2，6，7；无序表：4

  (5) 第四次比较，从无序表中取出第一个数 4，与中间值2比较，4>2，4放在2后面，再与后半区（有序表:6,7）的中间值6比较，4<6，4放在6前面，最终得到：1，2，4，6，7

  算法分析：

    时间复杂度：O($n^2$)。
    空间复杂度：O(1)。
    稳定性：是一种稳定的排序方法。

---

2.3 希尔排序

  算法思想：先将整个待排记录分割成若干个子序列，在子序列中分别进行直接插入排序，待整个序列基本有序的时候，再对全体序列进行一次直接插入排序。

  步骤：

    Step1: 选择一个步长序列t1，t2，…，tk，其中 ti>tj，tk=1；

    Step2: 按步长序列个数k，对序列进行k趟排序；

    Step3: 每趟排序，根据对应的步长ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅步长因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

  案例：

  算法分析：

    时间复杂度：由于希尔排序是依赖于增量的选取，它的时间复杂度是在O(nlog₂n)-O($n^2$)之间。
    空间复杂度：在希尔排序的过程中只需要一个辅助空间用于暂存当前待插入的记录，因此，希尔排序的空间复杂度为O(1)。
    稳定性：希尔排序方法是一种不稳定的排序方法。

---

3、交换排序

3.1 冒泡排序

  算法思想：对n个记录的表，第一趟冒泡得到一个关键码最大的记录r[n]，第二趟冒泡对n-1个记录的表，再得到一个关键码最大的记录r[n-1]，如此重复，直到n个记录按关键码有序的表。

  步骤：

    (1) 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
    (2) 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
    (3) 针对所有的元素重复以上的步骤，除了最后一个；
    (4) 重复步骤1~3，直到排序完成。

  一趟冒泡方法：

    Step1: i=1； //设置从第一个记录开始进行两两比较
    Step2: 若i≥j，一趟冒泡结束。
    Step3: 比较r[i].key与r[i+1].key，若 r[i].key≤r[i+1].key，不交换，转Step5;
    Step4: 当r[i].key>r[i+1].key时， r[0]=r[i]；r[i]=r[i+1]；r[i+1]=r[0]； // 将r[i]与r[i+1]交换
    Step5: i=i+1；对下两个记录进行两两比较，转Step2;

  算法分析：

    空间复杂度：冒泡排序的空间复杂度为O(1)。
    时间复杂度：总共要进行n-1趟冒泡，对j个记录的表进行一趟冒泡需要j-1次关键码比较。 冒泡排序的时间复杂度为O($n^2$)。
    稳定性：冒泡排序是一种稳定的排序方法。

---

3.2 快速排序

  算法思想：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列R[s…t]将分割成两部分：R[s..i-1]和R[i+1..t]，且R[j].key≤ R[i].key ≤ R[j].key (s≤j≤i-1) 枢轴 (i+1≤j≤t)。

  步骤：

    Step1: 如果待排子序列中元素的个数大于1，则以L.r[low]作为枢轴，进行一次划分；否则排序结束。
    Step2: 对枢轴左半子序列重复Step1;
    Step3: 对枢轴右半子序列重复Step1;

  案例：

  算法分析：
    空间复杂度：快速排序是递归的，递归调用层次数与其二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)；在最坏情况下，为O(n)。
    时间复杂度：最好情况下为O(nlog2n) ，最坏情况，快速排序蜕化为冒泡排序。
    稳定性：快速排序是一个不稳定的排序方法。

---

4、选择排序

4.1 简单选择排序

  算法思想：第一趟，从n个记录中找出关键码最小的记录与第一个记录交换；第二趟，从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换；如此，第i趟，则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i个记录交换，直到整个序列按关键码有序。

  步骤：

    Step1: 从L.key[i]~ 从L.key[length]记录中选择一个关键字值最小的记录，将其下标保存至min中；
    Step2: 若L.key[i]≥L.key[min];则交换这两个记录;否则转Step3;
    Step3: i=i+1,若i≤L.length，则转Step1;否则排序结束。

  算法分析：

    时间复杂度：从算法中可看出，简单选择排序移动记录的次数较少，但关键码的比较次数依然是，算法的时间复杂度仍是O($n^2$)。
    空间复杂度：简单选择排序算法只需要一个辅助空间来作为交换记录用的暂存单元。因此，它的空间复杂度O(1)。
    稳定性：简单选择排序是一种不稳定的排序方法。

---

4.2 树形选择排序

  步骤：

    Step1:从最底层叶子结点开始，按层一一进行兄弟间的比赛，关键字值较大者上升为子树根结点，直到树的顶层为止；
    Step2:将树的根结点输出，把底层叶子中值相同的结点值改为0；如果输出的结点总数小于初始时树的叶子结点总数，则重复Step1;否则结束排序。

  案例：

  首先对n个记录的关键字两两进行比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录。整个过程可用一个含有n个叶结点的二叉树表示；
  选出最小记录后，将树中的该最小记录修改为∞，然后从该叶子结点所在子树开始，修改到达树根的路径上的结点；

  算法分析

    时间复杂度：除了最大关键字之外，每选择一个次大的关键字只需要进行log2n次比较，因此，它的时间复杂度为O(nlogn)。
    空间复杂度：需要附加n个辅助空间用来保存排序的结果，还要n-1个辅助空间作为排序过程中使用。因此，它的空间复杂度O(n)。
    稳定性：树形选择排序是一种不稳定的排序方法。这是因为在比较的过程中是跳跃式进行的。

---

4.3 堆排序

  定义：

  第一种定义方式：
    设有n个元素的序列 {k1，k2，…，kn}，当且仅当满足下述关系之一时，称之为堆。

  第二种定义方式：
    堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆或小顶堆）；或者每个结点的值都大于或等于其左右孩子结点的值（称为大根堆或大顶堆）。

  算法思想：设有n个元素，将其按关键码排序。首先将这n个元素按关键码建成堆，将堆顶元素输出，得到n个元素中关键码最小(或最大)的元素。然后，再对剩下的n-1个元素建成堆，输出堆顶元素，得到n个元素中关键码次小(或次大)的元素。如此反复，便得到一个按关键码有序的序列。称这个过程为堆排序。

  堆排序需解决的两个问题：

    1.怎样建堆：如何将n个元素的序列按关键码建成堆；
    2. 怎样调整：输出堆顶元素后，怎样调整剩余n-1个元素，使其按关键码成为一个新堆。

  建堆方法：

    (1) 先把待排序序列构造成一棵完全二叉树;
    (2) 然后从下往上,自右而左进行筛选,最终得到堆。

  步骤：

    Step1: i=1,对顺序表L[1…L.lengh-i+1]中的建大顶堆；
    Step2: 将堆顶元素和L[L.lengh-i+1]交换；
    Step3: i=i+1,若i<L.lengh,则将L[1…L.lengh-i+1]调整；使之成为新的大顶堆；转Step2;否则排序结束。

  算法分析：

    时间复杂度：在建好堆后，排序过程中的筛选次数不超过 O(nlog2n)，而建堆时的比较次数不超过4n次，因此堆排序最坏情况下，时间复杂度也为O(nlog2n)。
    空间复杂度：堆排序中，只需要一个用来交换的暂存单元，因此它的空间复杂度为O(1)。
    算法的稳定性：由于记录的比较和交换是跳跃式进行的，因此，堆排序是一种不稳定的排序方法。

---

4.4 二路归并排序

  算法思想：归并排序的基本思想是基于将两个或两个以上的有序子序列 “归并” 为一个有序序列。

  步骤：

    Step1: 设置两个子表的起始下标及辅助数组的起始下标：i=u；j=v；k=u；
    Step2: 若i>v 或 j>t，则比较选取结束转Step4；
    Step3: 选取r[i]和r[j]中关键码较小的存入辅助数组rf。如果 r[i].key<r[j].key，则rf[k]=r[i]； i++； k++；否则，rf[k]=r[j]； j++； k++。 转Step2;
    Step4: 将尚未处理完的子表中元素存入rf：
    Step5: 合并结束。

  递归算法操作步骤：

    Step1: 将待排序的记录序列分为两个相等的子序列，分别将这两个子序列进行排序；
    Step2: 调用一次归并算法Merge，将这两个有序子序列合并成一个含有全部记录的有序序列。

  案例：

  算法分析：

    时间复杂度：归并过程对应由叶向根生成一棵二叉树的过程，所以归并趟数约等于二叉树的高度-1，即log2n，每趟归并需移动记录n次，故时间复杂度为O(nlog2n)。
    空间复杂度：需要一个与表等长的辅助元素数组空间，所以空间复杂度为O(n)。
    稳定性：由一次归并算法中的if语句可知，二路归并算法是一种稳定的算法。

---

5、基数排序

  基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。

5.1 链式基数排序

  基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

  案例：

  算法分析：

    时间效率：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix)) 。
    空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。
    稳定性：在基数排序的过程中，并没有交换记录的前后位置，因此该排序方法是一种稳定的排序方法。

---

6、各种内部排序方法的比较