内部排序

概述

1.排序：将文件或表中的记录，通过某种方法整理成按 关键字大小次序排列的处理过程。 假定n个记录的文件为 (R1,R2,…,Rn) 对应的关键字为 (K1,K2,…,Kn) 则排序是确定如下一个排列 p1,p2,…,pn 使得: Kp1≤Kp2≤…≤ Kpn 从而得到一个有序文件或表中的记录 (Rp1,Rp2,…Rpn)

2.什么是排序的稳定性 假设在待排序的文件中，存在两个具有相同关键字的记 录R(i)与R(j),其中R(i)位于R(j)之前。在用某种排序法排序 之后,R(i)仍位于R(j)之前，则称这种排序方法是稳定的；否 则，称这种排序方法是不稳定的。

3.内部排序和外部排序

• 内部排序(内排序)—-在计算机内存中进行的排序
• 外部排序(外排序)—-借助计算机外存进行的排序

插入排序

直接插入排序

首先,将初始文件中的记录r[1]看作有序子文件； 第1遍：将r[2]插入前面有序子文件中，得到3个记录的有序子文件。 第2遍：将r[3]插入前面有序子文件中，得到3个记录的有序子文件。 以此类推，依次插入r[4],…,r[n],最后得到n个记录的递增有序文件。

直接插入排序算法（对数组r[1..n]中的n个记录作插入排序）
void InsertSort(RecType r[],int n）
{
    int i,j；
    for (i=2；i<=n；i++) { 
        r[0]=r[i]； //待插记录r[i]存入监视哨中 
        j=i-1； //已排序的范围1 － i-1 
        //从r[i-1]开始向左扫描
        while(r[0].key
        { 
            r[j+1]=r[j]； //记录后移 
            j--； //继续向左扫描
        } 
        r[j+1]=r[0]； //插入记录r[0],即原r[i] 
    } 
}

• (1)最好情况，原n个记录递增有序： 比较关键字n-1次 移动记录2(n-1)次,(将数据复制到r[0]后又复制回来）
• (2)最坏情况，原n个记录递减有序： 比较关键字的次数: 2+3+…+n =(n-1)(n+2)/2 = O(n2) 移动记录的次数(个数): 3+4+…+(n+1) =(n-1)(n+4)/2 次 = O(n2)

• (4) 只需少量中间变量作为辅助空间。
• (5) 算法是稳定的

  折半插入排序

  减少了记录的比较次数平均值，记录的移动次数不变

  void BInsertSort(RecType r[],int n） { 
      int i,j； 
      for (i=2；i<=n；i++) { 
          r[0]=r[i]； //待插记录r[i]存入监视哨中 
          low = 1 ； high = i - 1； 
          while ( low <= high ) { 
              m = ( low + high ) / 2 ; 
              if ( r[0].key<r[m].key) high = m - 1； //插入位置可能在high之后 
              else low = m+1； //插入位置可能在low之前 
          } //结束时表示插入在high和low之间
          for (j = i – 1; j >= high + 1;- -j ) r[j+1] = r[j]； 
          r[high + 1] = r[0];
      } 
  }

  shell排序

  shell排序是由P.L.Shell于1959年提出的一种对插入 排序的改进算法。其算法思想是将待排序的数据分成 若干组： 将待排序的数据，简单处理时,可首先看成n/2组， 即间隔为n/2的数据元素在同一组中，每一组使用前面 的插入排序算法，实现数据的大跨度前移。再将待排序的数据看成n/4组，即间隔为n/4的数据元 素在同一组中，每一组使用前面的插入排序算法。余以类 推。 当比较间隔缩小到0时，整个排序过程结束。 由于每比较一趟，就将比较间隔缩小一半。间隔也称 为增量， shell算法又称为缩小增量排序算法。算法分析与 增量的选取有关。具体实现见专栏另一篇https://juejin.cn/post/7037473904159359006

2路插入排序

• Ø n个辅助空间
• Ø 首位key作为基础，大的插在后面，小的插在尾部
  

表插入排序

即使用链表的存储结构对数据进行插入排序。在对记录按照其关键字进行排序的过程中，不需要移动记录的存储位置，只需要更改结点间指针的指向。

链表的存储结构用代码表示为：

#define SIZE 100
typedef struct {
    int rc;//记录项
    int next;//指针项，由于在数组中，所以只需要记录下一个结点所在数组位置的下标即可。
}SLNode;
typedef struct {
    SLNode r[SIZE];//存储记录的链表
    int length;//记录当前链表长度
}SLinkListType;

在使用数组结构表示的链表中，设定数组下标为 0 的结点作为链表的表头结点，并令其关键字取最大整数。则表插入排序的具体实现过程是：首先将链表中数组下标为 1 的结点和表头结点构成一个循环链表，然后将后序的所有结点按照其存储的关键字的大小，依次插入到循环链表中。

例如，将无序表{49，38，76，13，27}用表插入排序的方式进行排序，其过程为：
\

• 首先使存储 49 的结点与表头结点构成一个初始的循环链表，完成对链表的初始化，如下表所示：

\  

• 然后将以 38 为关键字的记录插入到循环链表中（只需要更改其链表的 next 指针即可），插入后的链表为：

\  

• 再将以 76 为关键字的结点插入到循环链表中，插入后的链表为:

\  

• 再将以 13 为关键字的结点插入到循环链表中，插入后的链表为：

\  

• 最后将以 27 为关键字的结点插入到循环链表中，插入后的链表为：

\  

• 最终形成的循环链表为：

\  

从表插入排序的实现过程上分析，与直接插入排序相比只是避免了移动记录的过程（修改各记录结点中的指针域即可），而插入过程中同其它关键字的比较次数并没有改变，所以表插入排序算法的时间复杂度仍是O(n2)。

交换排序

冒泡排序

基本思想: 设待排序的文件为r[1..n] 第1趟(遍)：从r[1]开始,依次比较两个相邻记录的关键字 r[i].key和r[i+1].key,若r[i].key>r[i+1].key，则交换记录 r[i]和r[i+1]的位置；否则,不交换。(i=1,2,…n-1) ==》第1趟之后，关键字中最大的记录移到了r[n]的位置上。
第2趟：从r[1]开始,依次比较两个相邻记录的关键字 r[i].key和r[i+1].key,若r[i].key>r[i+1].key，则交换记录 r[i]和r[i+1]的位置；否则,不交换。 (i=1,2,…n-2) 第2趟之后,前n-1个关键字中最大的记录移到了r[n-1]的位 置上。 …… 作完n-1趟,或者不需再交换记录时为止

例如，对无序表{49，38，65，97，76，13，27，49}进行升序排序的具体实现过程

如图 1 所示是对无序表的第一次起泡排序，最终将无序表中的最大值 97 找到并存储在表的最后一个位置。具体实现过程为：

1. 首先 49 和 38 比较，由于 38<49，所以两者交换位置，即从（1）到（2）的转变；
2. 然后继续下标为 1 的同下标为 2 的进行比较，由于 49<65，所以不移动位置，（3）中 65 同 97 比较得知，两者也不需要移动位置；
3. 直至（4），97 同 76 进行比较，76<97，两者交换位置，如（5）所示；
4. 同样 97>13（5）、97>27（6）、97>49（7），所以经过一次冒泡排序，最终在无序表中找到一个最大值 97，第一次冒泡结束；

由于 97 已经判断为最大值，所以第二次冒泡排序时就需要找出除 97 之外的无序表中的最大值，比较过程和第一次完全相同。

算法分析:

• Ø最好情况: 待排序的文件已是有序文件，只需要进行1趟 排序,共计比较关键字的次数为 n－1 不交换记录。
• Ø最坏情况: 要经过n-1趟排序，所需总的比较关键字的次 数为 (n-1)+(n-2)+…+1＝n(n-1)/2 交换记录的次数最多为 (n-1)+(n-2)+…+1＝n(n-1)/2 移动记录次数最多为 3n(n-1)/2 。
• Ø只需要少量中间变量作为辅助空间。
• Ø算法是稳定的。

快速排序

基本思想：首先在r[1..n]中，确定一个r[i]，经过比较 和移动，将r[i]放到”中间”某个位置上，使得： ur[i]左边所有记录的关键字小于等于r[i].key， ur[i]右边所有记录的关键字大于等于r[i].key。 ü 以r[i]为界,将文件划分为左、右两个子文件。 用同样的方法分别对这两个子文件进行划分, 得到4个 更小的子文件。继续进行下去,使得每个子文件只有一个记 录为止,便得到原文件的有序文件。

例. 给定文件(20,05,37,08,63,12,59,15,44,08)，选用第1 个元素20进行划分:

算法分析

• Ø就平均速度而言，快速排序是已知内部排序方法中最 好的一种排序方法,其时间复杂度为O(nlog(n))。

• Ø但是，在最坏情况下（有序或基本有序时，此时每次 划分都出现一端为空的形式），快速排序所需的比较次 数和冒泡排序的比较次数相同,其时间复杂度为O(n2)。

• Ø快速排序需要一个栈作辅助空间，用来实现递归处理 左、右子文件。在最坏情况下,递归深度为n，因此所需 栈的空间大小为O(n)数量级。

• Ø 快速排序是不稳定的

  选择排序

  算法思想:设待排序的文件为(r[1],r[2],…,r[n]),关键字为 (r[1].key,r[2].key,…,r[n].key), 第1趟(遍)：在(r[1],r[2],…,r[n])中,选出关键字最小 的记录r[min].key，若min<>1,则交换r[1]和r[min]； 　　　需要进行n-1次比较。 　 第2趟(遍)：在n-1个记录(r[2],…,r[n])中,选出关键字 最小的记录r[min].key，若min<>2,则交换r[2]和r[min]； 　　　需要进行n-2次比较。 …… 　第n-1趟(遍)：在最后的2个记录记录(r[n-1],r[n])中,选 出关键字最小的记录r[min].key，若min<>n-1,则交换r[n-1] 和min]；需要进行1次比较。
  例如对无序表{56，12，80，91，20}采用简单选择排序算法进行排序，具体过程为：

• 第一次遍历时，从下标为 1 的位置即 56 开始，找出关键字值最小的记录 12，同下标为 0 的关键字 56 交换位置：

• 第二次遍历时，从下标为 2 的位置即 56 开始，找出最小值 20，同下标为 2 的关键字 56 互换位置：

• 第三次遍历时，从下标为 3 的位置即 80 开始，找出最小值 56，同下标为 3 的关键字 80 互换位置：

• 第四次遍历时，从下标为 4 的位置即 91 开始，找出最小是 80，同下标为 4 的关键字 91 互换位置：

• 到此简单选择排序算法完成，无序表变为有序表。

void selection_sort(vector<int>& nums, int n)
{
    for (int i = 0;i < n-1;i++)
    {
        int temp_min = i;
        for (int j = i + 1;j < n;j++)//从i后面开始不断更新最小值的小标
        {
            if (nums[temp_min] > nums[j]) {
                temp_min = j;
            }
        }
        swap(nums[temp_min], nums[i]);//将最小值与nums[i]交换
    }
}

算法分析：

• (1)比较次数，在任何情况下,均为 n-1 ∑ (n－i)＝(n-1)+(n-2)+…+1 i=1 ＝ n(n-1)/2 ＝O(n 2)
• (2)交换记录的次数 在最好情况下,原n个记录递增有序： 不移动记录。 在最坏情况下,每次都要交换数据（不是递减有序） 共交换记录n-1对,移动记录数3(n-1)次。 故,时间复杂度为O(n 2)。
• (3)只需少量中间变量作为辅助空间。
• (4)算法是不稳定的。

堆排序

在学习堆排序之前，首先需要了解堆的含义：在含有 n 个元素的序列中，如果序列中的元素满足下面其中一种关系时，此序列可以称之为堆。
\

• ki ≤ k2i 且 ki ≤ k2i+1（在 n 个记录的范围内，第 i 个关键字的值小于第 2i 个关键字，同时也小于第 2i+1 个关键字）
• ki ≥ k2i 且 ki ≥ k2i+1（在 n 个记录的范围内，第 i 个关键字的值大于第 2i 个关键字，同时也大于第 2i+1 个关键字）

对于堆的定义也可以使用完全二叉树来解释，因为在完全二叉树中第 i 个结点的左孩子恰好是第 2i 个结点，右孩子恰好是 2i+1 个结点。如果该序列可以被称为堆，则使用该序列构建的完全二叉树中，每个根结点的值都必须不小于（或者不大于）左右孩子结点的值。

以无序表{49，38，65，97，76，13，27，49}来讲，其对应的堆用完全二叉树来表示为：

图 3 无序表对应的堆

提示：堆用完全二叉树表示时，其表示方法不唯一，但是可以确定的是树的根结点要么是无序表中的最小值，要么是最大值。

通过将无序表转化为堆，可以直接找到表中最大值或者最小值，然后将其提取出来，令剩余的记录再重建一个堆，取出次大值或者次小值，如此反复执行就可以得到一个有序序列，此过程为堆排序。

堆排序过程的代码实现需要解决两个问题：

1. 如何将得到的无序序列转化为一个堆？
2. 在输出堆顶元素之后（完全二叉树的树根结点），如何调整剩余元素构建一个新的堆？

首先先解决第 2 个问题。图 3 所示为一个完全二叉树，若去除堆顶元素，即删除二叉树的树根结点，此时用二叉树中最后一个结点 97 代替，如下图所示：\

此时由于结点 97 比左右孩子结点的值都大，破坏了堆的结构，所以需要进行调整：首先以 堆顶元素 97 同左右子树比较，同值最小的结点交换位置，即 27 和 97 交换位置：

\  

由于替代之后破坏了根结点右子树的堆结构，所以需要进行和上述一样的调整，即令 97 同 49 进行交换位置：

\  

通过上述的调整，之前被破坏的堆结构又重新建立。从根结点到叶子结点的整个调整的过程，被称为“筛选”。

解决第一个问题使用的就是不断筛选的过程，如下图所示，无序表{49，38，65，97，76，13，27，49}初步建立的完全二叉树，如下图所示：

\  

在对上图做筛选工作时，规律是从底层结点开始，一直筛选到根结点。对于具有 n 个结点的完全二叉树，筛选工作开始的结点为第 ⌊n/2⌋个结点（此结点后序都是叶子结点，无需筛选）。

所以，对于有 9 个结点的完全二叉树，筛选工作从第 4 个结点 97 开始，由于 97 > 49 ,所以需要相互交换，交换后如下图所示：

\  

然后再筛选第 3 个结点 65 ，由于 65 比左右孩子结点都大，则选择一个最小的同 65 进行交换，交换后的结果为：

\  

然后筛选第 2 个结点，由于其符合要求，所以不用筛选；最后筛选根结点 49 ，同 13 进行交换，交换后的结果为：

\  

交换后，发现破坏了其右子树堆的结构，所以还需要调整，最终调整后的结果为：

归并排序

其排序的实现思想是先将所有的记录完全分开，然后两两合并，在合并的过程中将其排好序，最终能够得到一个完整的有序表。

例如对于含有 n 个记录的无序表，首先默认表中每个记录各为一个有序表（只不过表的长度都为 1），然后进行两两合并，使 n 个有序表变为 ⌈n/2⌉ 个长度为 2 或者 1 的有序表（例如 4 个小有序表合并为 2 个大的有序表），通过不断地进行两两合并，直到得到一个长度为 n 的有序表为止。这种归并排序方法称为：2-路归并排序。

例如对无序表{49，38，65，97，76，13，27}进行 2-路归并排序的过程如图 1 所示：
\

图 1 归并排序过程

归并过程中，每次得到的新的子表本身有序，所以最终得到的为有序表。