数据结构第八章-排序

发表于 | 更新于: | 分类于 |
字数统计: 41k | 阅读时长 ≈ 2:30

数据结构第八章 排序

计算机学科基础：数据结构第八章排序的学习笔记

1.排序的基本概念

  • 评价指标
    • 稳定性：关键字相同的元素经过排序后相对顺序是否会改变
    • 时间复杂度、空间复杂度
  • 分类
    • 内部排序：数据都存放在内存中
      • 一般内部排序算法在执行过程中都需要进行比较和移动两种操作（但是基数排序不基于比较）
    • 外部排序：数据无法全部同时存放在内存中

2.插入排序（✪）

  • 直接插入排序

    • 算法思想：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

    • 流程

      • pCjN6gJ.png

    • 代码实现

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      void InsertSort(int A[],int n){
          int i,j,temp;
          for(i=1;i<n;i++) //将各元素插入已排好序的序列中
              if(A[i]<A[i-1]){  //每次都比较该位置的前驱，看是否小于前驱
                  temp=A[i];  // temp暂存
                  for(j=i-1;j>=0&&A[j]>temp;--j)//检查前面排好序的元素
                      A[j+1]=A[j]; //所有大于temp的元素都向后挪位
                  A[j+1]=temp; //复制到插入位置
              }
      }

    • 直接插入排序的性能分析

      • 空间效率：空间复杂度为O(1)
      • 时间复杂度：主要来自对比关键字、移动元素，若有n个元素，则需要n-1趟处理
        • 最好时间复杂度为O(n)（全部顺序）
          • 最好的情况下做 n-1次关键字的比较，也就是执行n-1趟，每趟只比较一次，此时不需要移动元素
        • 最坏/平均时间复杂度为O($n^{2}$) (全部逆序)
          • 直接插入排序在最坏的情况下做 n(n-1)/2次关键字的比较，此时移动次数也达到最大
      • 稳定性：为稳定的排序算法
      • 适用性：直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

  • 折半插入排序

    • 算法思想：先用折半查找找到应该插入的位置，再移动元素

      • 当low>high时折半查找停止，应将[Iow,i-1]内的元素全部右移，并将A[0]复制到Iow所指位置

      • 当A[mid]==A[0]时，为了保证算法的“稳定性”，应继续在mid所指位置右边寻找插入位置

    • 流程

      • 如此时向前插入8位置的55，需要在1-7个位置之间进行折半查找
        • pCOdDEV.png
      • 此时通过折半查找，找到其应该插入的位置为5，则将6-7的元素统一后移一位，并在5位置插入55
        • pCOdc34.png

    • 代码表示

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      Void InsertSort(int A[],int n){
          int i,j,low,high,mid;
          for(i=2,i<=n;i++){ 	//依次将A[2]到A[n]插入前面的已排序序列
              A[0]=A[i]; 	//A[0]作为暂存位
              low=1;high=i-1; 	//设置折半查找的范围
              while(low<=high){	//折半查找
                  mid=(low+high)/2; //取中间点
                  if(A[mid]>A[0]) high=mid-1; //查找左半子表
                  else low=mid+1 //查找右半子表
                  	//注意：一直到Iow>high时才停止折半查找。当mid所指元素等于当前元素时，
      				//应继续令Iow=mid+1,以保证“稳定性”。最终应将当前元素插入到Iow所指位置(即high+1)
              }
              for(j=i-1;i>=high+1;--j)
                  A[j+1]=A[j];	//统一后移元素，空出插入位置
              A[high+1]=A[0];    	//插入操作
              } 
          }
      }

    • 折半插入排序的性能分析

      • 折半插入排序的比较次数与原始状态无关，仅取决于n

      • 折半插入排序仅减少了比较元素的次数，约为O($nlog_{2}{n}$)

      • 折半插入排序没有改变元素的移动次数，时间复杂度仍然是O($n^{2}$)，依赖于原始状态

  • 希尔排序（缩小增量排序）

    • 算法思想：先追求表中元素部分有序，再逐渐逼近全局有序

      • 设置增量为d的子表，把相隔某个增量的记录组成一个子表，对各个子表分别进行直接插入排序。
        之后进行增量的缩小再进行一次这样的排序，当整个表中的呈现基本有序时，再对全体记录进行一次直接插入排序
      • 图片
        • pCO0aT0.png

    • 流程

      • 第一趟排序之后
        • pCO0rpF.png
      • 第二趟排序之后
        • pCO07Xd.png
      • 第三趟排序之后
        • pCO0jtf.png

    • 代码表示

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      void ShellSort(int A[],int n){
          int d,i,j;
          //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
          for(d=n/2;d>=1;d=d/2) //步长变化
              for(i=d+1;i<=n;++i)
                  if(A[i]<A[i-d]){ //若前序较大，需将A[i]插入有序增量子表
                      A[0]=A[i];	//暂存在A[0]
                      for(j=i-d;j>0&&A[0]<A[j];j-=d)
                          A[j+d]=A[j]; //记录后移，查找插入的位置
                      A[j+d]=A[0]		//插入
                  }
      }

    • 希尔排序的性能分析

      • 空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)
      • 时间效率：当n在某个特定范围时，希尔排序的时间复杂度约为O($n^{1.3}$)，在最坏情况下希尔排序的时间复杂度为O($n^{2}$)
      • 稳定性：当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，希尔排序是一种不稳定的排序方法。
      • 适用性：希尔排序算法仅适用于线性表为顺序存储的情况。

3.交换排序（✪）

  • 冒泡排序

    • 算法思想：根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置
      • 从后往前（或从前往后）两两比较相邻元素的值，若为逆序(即A[i-1]>A[i])，则交换它们，直到序列比较完。
        称这样过程为“一趟”冒泡排序。
      • 下一趟冒泡时，前一趟确定的最小元素不再参与比较，
        每趟冒泡的结果是把序列中的最小元素（或最大元素）放到了序列的最终位置
      • 最多做n-1趟冒泡就能把所有元素排好序。
    • 流程
      • pCjBBU1.png
    • 代码实现
      • pCO6peH.png
    • 冒泡排序的性能分析
      • 空间复杂度：仅使用了常数个辅助单元，因而空间复杂度为O(1).
      • 时间复杂度
        • 当初始序列有序时，显然第一趟冒泡后flag依然为false（本趟没有元素交换）从而直接跳出循环，
          比较次数为n-1，移动次数为0，从而最好情况下的时间复杂度为O($n$)
        • 当初始序列为逆序时，需要进行n-1趟排序，第i趟排序要进行n-i次关键字的比较，
          而且每次比较后都必须移动元素3次来交换元素位置，此时
          • 比较次数：$\frac{n(n-1)}{2}$，移动次数：$\frac{3n(n-1)}{2}$
          • 最坏情况下的时间复杂度O($n^{2}$)
        • 平均时间复杂度为O($n^{2}$)
      • 稳定性：冒泡排序是一种稳定的排序方法
      • 适用于顺序表和链表
      • 快速排序一趟会确定一个元素最终的位置

  • 快速排序

    • 算法思想：分治法

      • 在待排序表L[1..n]中任取一个元素pivot作为枢轴(或基准，通常取首元素)
      • 通过一趟排序将待排序表划分为独立的两部分L[1……k-1]和L[k+1……n]，使得L[1……k-1]中的所有元素小于pivot，
        L[k+1……n]中的所有元素大于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”。
      • 然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

    • 代码实现（掌握）

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      //快速排序（表长为n，初始的low为表头0，high为表尾n-1）
      void QuickSort()(int A[],int low,int high){
          if(low<high){	//当low=high时，此时递归跳出
              int pivotpos=Partition(A,low,high); //进行一次分治划分
              QuickSort(A,low,pivotpos-1);	//划分左子表(上一次划分后返回的之前枢纽存放的最终位置的左边一位在划分左子表时作为"high"，low为当前递归工作栈的存放位置)
              QuickSort(A,Pivotpos+1,high);   //划分右子表(上一层划分后返回的之前枢纽存放的最终位置的右边一位在划分右子表时作为"low",high为当前递归工作栈的存放位置)
          }   
      }

      int Partition(int A[],int low,int high){
          int pivot=A[low];   //将当前表中的low作为枢纽
          while(low<high){	//当low=high时，说明此轮的枢纽已经搜索到了最终的位置，跳出此轮枢纽的循环
              while(low<high&&A[high]>=pivot)  //从后往前找到比枢纽更小的元素，将其移动到左边
                  --high;
              A[low]=A[high];   //在high位置上比枢纽小的元素移动到当前low的位置
              while(low<high&&A[low]<=pivot)   //从前往后找到比当前枢纽更大的元素，将其移动到右边
                  ++low;
              A[high]=A[low];	  //在low位置上比枢纽更大的元素移动到当前的high位置
          }
          A[low]=pivot;     //进行一次分治算法后，枢纽存放的最终位置
          return low;       //返回枢纽存放的最终位置
      }

    • 流程

      • 第一轮分治法时，递归工作栈中的low为0，high为7，此时将49作为枢纽，将high指针左移，找到比枢纽小的元素移动到low指针处，
        之后又将low指针右移，找到比枢纽大的元素移动到high指针处。
      • 互相进行以上操作，直到low=high时，此时就找到了枢纽元素的最终位置。并返回当前的枢纽指针位置，进行左子表的新一轮递归操作。
        • 初始情况
          • pCO5Bh4.png
        • 第一趟递归操作
          • pCjsLrD.png
      • 第二轮分治法时，递归工作栈中的low为0，high为之前的枢纽位置3减1为2，此时选择27为枢纽进行操作
        • pCO5XE8.png
      • 到了处理右子表时，递归的工作栈中low为之前的枢纽3加1为4，high为7，此时选择76为枢纽进行操作
        • pCOIm8J.png

    • 快速排序的性能分析

      • 算法表现主要取决于递归深度若每次“划分”越均匀，则递归深度越低。“划分”越不均匀，递归深度越深
      • 空间复杂度：最好空间复杂度：O($log_{2}n$)，最坏空间复杂度：O($n$)

      • 时间复杂度：

        • 最好时间复杂度：O($nlog_{2}n$)，每次选的枢轴元素都能将序列划分成均匀的两部分
        • 最坏时间复杂度：O($n^{2}$​)，若序列原本就有序或逆序，则时空复杂度最高，可优化，尽量选择
          可以把数据中分的枢轴元素。

      • 快速排序是所有内部排序算法中平均性能最优的算法

      • 快速排序是一种不稳定的排序

    • 例题

      • 判断快速排序时速度最快和最慢的情况
        • 此时需要判断以枢纽为中心的两边所划分的元素个数是否平均，
          小于枢纽的元素的个数和大于枢纽的元素的个数的比例越不平均，所耗时越多
        • 速度最慢显然是D选项，均为有序排序时，速度最快时看大于和小于枢纽的数的比例，
          A，C选项的比例1:1；B选项为5:1，
          再从AC选项里面选择进行一趟快速排序（A：9,5,7,21,25,23,30；B:5,9,17,21,25,23,30）
          此时A的左右子表都满足与新枢纽的比例为1:1，但是B的左右子表关于新枢纽的比例均为2:0，选A
          • pCOHtTP.png
      • 判断不可能是快速排序第2趟排序的结果的序列，利用快速排序一趟会确定一个元素最终的位置，
        此时写出有序序列与选项作比较，此时只需要选项中有两个在相应位置上契合的元素即可
        • pCOOeje.png
      • 除了需要满足上面的条件，还需要满足此时有一个符合的元素位于边界
        • pCOOo8K.png

4.选择排序（✪）

  • 简单选择排序

    • 算法思想：每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列
      每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可使得整个排序表有序。

    • 代码实现

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      void SelectSort(int A[],int n){
          for(int i=0;i<n-1;i++){		//一共进行n-1趟	
              int min=i;     //记录最小元素的位置
              for(int j=i+1;j<n;j++){  //在A[i……n-1]中选择最小的元素
                  if(A[j]<A[min])		//如果存在更小的元素，则更新最小元素的位置
                      min=j;
              }
              if(min!=i)
                  swap(A[i],A[min]);   //交换位置，此时该趟中最小的元素到了i位置
          }
      }

      void swap(int &a,int &b){
          int temp=a;
          a=b;
          b=temp;
      }

    • 简单选择排序性能分析

      • 空间复杂度：O(1)
      • 时间复杂度：O($n^{2}$)
      • 无论有序、逆序、还是乱序，一定需要n-1趟处理
      • 元素间比较的次数与序列的初始状态无关，始终是$n(n-1)/2$次，因此时间复杂度始终是O($n^{2}$)
      • 简单选择排序是一种不稳定的排序算法
      • 适用于顺序表和链表

  • 堆排序

    • 堆（堆是用来排序的，他的查找效率很低）

      • 从二叉树的任意结点出发到根的路径上所经过的所有结点序列按其关键字有序，则此二叉树是根

      • 大根堆与小根堆

        • 若${n}$个关键字序列${L[1 \ldots n]}$满足下面某一条性质, 则称为堆（Heap）

          • 若满足:${\mathrm{L}(\mathrm{i}) \geqslant \mathrm{L}(2 \mathrm{i})}$且${\mathrm{L}(\mathrm{i}) \geqslant \mathrm{L}(2 \mathrm{i}+1) (1 \leq i \leq n / 2)—}$大根堆（大顶堆）
          • 若满足:${\mathrm{L}(\mathrm{i}) \leqslant \mathrm{L}(2 \mathrm{i})}$且${\mathrm{L}(\mathrm{i}) \leqslant \mathrm{L}(2 \mathrm{i}+1) (1 \leq i \leq n / 2) —}$小根堆（小顶堆）

        • 图片

          • pCXeqsJ.png

    • 流程

      • 建立大根堆
        • 可以将堆看做是一个完全二叉树，大根堆就是根结点的关键字大于左右孩子结点，
          此时可以对于一个给定的初始的序列建立大根堆，之后方便进行选择排序
        • 把所有非终端结点都检查一遍，是否满足大根堆的要求，
          如果不满足，则进行调整，在顺序存储的完全二叉树中, 非终端结点编号 $\mathbf{i} \leq\lfloor n / 2\rfloor$
        • 从编号为$\lfloor n / 2\rfloor$的分支结点开始从后往前检查，检查当前结点是否满足根≥左、右，
          若不满足，将当前结点与更大的一个孩子互换
        • 之后依次这样处理前面序号的非终端结点，
          若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整(小元素不断“下坠”)
        • 图片（注：初始序列为：（53,17,78,9,45,65,87,32），初始对$\lfloor n / 2\rfloor$位置开始检查，从后往前检查）
          • pCjcjZF.png
      • 进行堆排序
        • 在建立大根堆完成之后，每一趟将堆顶关键字与待排序序列中的最后一个元素交换（将堆顶元素加入有序子序列）
        • 并将待排序元素序列再次调整为大根堆(小元素不断“下坠”)
        • 在经过n-1趟之后得到基于“大根堆”的堆排序的“递增序列”
        • 图片
          • 此时已建立好堆排序，此时将堆顶元素87与最后一个元素9进行互换，87输出到最后位
            • pCX1S74.png
          • 互换之后，此时9在完全二叉树中破坏了大堆根，此时应该进行调整，使最小的元素坠入底端，9与78互换
            • pCX1ZnO.png
          • 互换之后，还需要使其与下一层更大的65进行互换
            • pCX113t.png
            • 此时互换后，重新形成了一个大根堆，如果继续进行下一趟排序的话，
              此时已经变成有序序列的第8号元素所在的关键字87不参与排序，此时的len减一为7。78将输出，与7位置上的53互换
              • pCX18jf.png

    • 代码实现（了解）

      • 建立大根堆

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        //建立大根堆
        void BuildMaxHeap(int A[],int len){
            for(int i=len/2;i>0;i--){	//从后向前调整所有的非终端结点
                HeadAdjust(A,i,len);
            }
        }
        //将以K为根的子树调整为大根堆
        void HeadAdjust(int A[],int k,int len){
            A[0]=A[k];   //A[0]暂存子树的根结点
            for(int i=2*k;i<len;i*=2){ //沿关键字较大的根结点的子节点向下筛选，若超出原数组长度，则跳出循环
                if(i<len&&A[i]<A[i+1])	//此时取关键字更大的其中子节点
                    i++;
                if(A[0]>=A[i])
                    break;		//此时根结点的值较大，则停止筛选
                else{
                    A[K]=A[i];  //将被筛选中的结点调整到双亲结点上
                    k=i;	//修改k值，以便继续向下筛选
                }
            }
            A[k]=A[0];    //筛选完成后，被筛选的节点放入最终的位置
        }

      • 实现根排序

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        void BuildMaxHeap(int A[],int len)	//建立大根堆
            
        void HeadAdjust(int A[],int k,int len)//将以k为根的子树调整大根堆
            
        void HeapSort(int A[],int len){		//堆排序的完整逻辑
            BuildMaxHeap(A,len);	//初始建堆
            for(int i=len;i>1;i--){		//n-1趟的交换和建堆过程
                swap(A[i],A[1]);	//堆顶元素和堆底元素进行互换
                HeadAdjust(A,1,i-1);	//把剩余的待排序元素整理成堆
            }
        }

    • 堆的插入

      • 对于小根堆，新元素放到表尾，与父节点对比，若新元素比父节点更小，则将二者互换。
        新元素就这样一路“上升”，直到无法继续上升为止
      • 删除时，被删除的元素用堆底元素替代，然后让该元素不断“下坠”，直到无法下坠为止
      • 向具有n个结点的堆中插入一个新元素的时间复杂度为O($log_{2}n$)，删除一个元素的时间复杂度为O($log_{2}n$)
      • 例题
        • 按照插入的方法，逐个插入即可，此时选B
          • pCXhNlR.png
          • pCXhU61.png

    • 堆排序的性能分析

      • 空间效率: 仅使用了常数个辅助单元, 所以空间复杂度为${O(1)}$
      • 时间效率: 建堆时间为${O(n)}$, 之后有${n-1}$次向下调整操作, 每次调整的时间复杂度为${O(h)}$,
        故在最好、最坏和平均情况下, 堆排序的时间复杂度为${O\left(n \log _{2} n\right)}$
      • 堆排序是一种不稳定的排序方法

5.归并排序和基数排序（✪）

  • 归并排序（可以作为外部排序）

    • 算法思想

      • 把两个或多个已经有序的序列合并成一个新的有序表
      • m路归并，每选出一个元素需要对比关键字m-1次
      • 将两个各有N个元素的有序表合并成一个有序表，最少的比较次数是N次（一个表中的最小元素大于另一个表的最大元素时），
        最多的比较次数是2N-1次（两个表中的元素依次间隔地比较时）
      • 图片
        • pCjPZh4.png

    • 流程（在内部排序中一般选择二路归并）

      • pCjPucR.png

    • 例题

      • 第一趟为2个一组，第二趟为4个一组，每组内部排序即可，选B
        • pCjeUmj.png

    • 代码实现（了解）

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      int *B=(int *)malloc(n*sizeof(int)); //定义辅助数组B

      //归并算法
      Void Merge(int A[],int low,int mid,int high){
          int i,j,k;
          for(k=low;k<=high;k++)
              B[k]=A[k]; 	//将A中所有元素复制到辅助元素B中
          for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
              if(B[i]<=B[j]) //此时有等于号的原因是使两个元素相等时，优先使用靠前的那一个（稳定性）
                  A[k]=B[i++];   //将较小的复制到A的位置，之后前半部分的指针位加一
              else
                  A[K]=B[j++];	//将较大的复制到A的位置，之后后半部分的指针位加一
          }
          while(i<=mid) 
              A[k++]=B[i++]; //若第一个辅助表没有检测完，则直接复制到原表的尾部
          while(j<=hige)
               A[k++]=B[j++]; //若第二个辅助表没有检测完，则直接复制到原表的尾部
          
      }
      //递归的归并算法
      void MergeSort(int A[],int low,int high){
          if(low<high){
              int mid=(low+high)/2; //从序列的中间划分出子序列
              MergeSort(A,low,mid);	//对左半部分归并排序
              MergeSort(A,mid+1,high); //对右半部分归并排序
              Merge(A,low,high);	//整体归并
          }
      }

    • 归并排序的性能分析

      • 空间复杂度${=O(n)}$, 来自于辅助数组${\mathbf{B}}$
      • ${\mathrm{n}}$个元素进行2路归并排序, 归并趟数${=\left\lceil\log _{2} n\right\rceil}$，每路归并时间复杂度为${O(n)}$, 则算法的时间复杂度为${O\left(n \log _{2} n\right)}$
      • 归并排序是一种稳定的排序算法

  • 基数排序

    • 算法思想
      • 基数排序不是基于比较的排序算法，是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法，
        通常基于链式存储实现
      • 最高位优先法（MSD）：按关键字位权重递减（先看最高位）；最低位优先法（LSD）：按关键字位权重递增（先看个位）
      • 采用最低位优先法进行基数排序的流程
        • 将整个关键字拆分为d位(或“组”)
        • 按照各个关键字位权重递增的次序(如：个、十、百)，做d趟“分配”和“收集”，
          若当前处理的关键字位可能取得r个值，则需要建立r个队列
        • 分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应队列。一趟分配耗时O(n)
        • 收集：把各个队列中的结点依次出队并链接。一趟收集耗时O(r)
    • 流程
      • 最低位优先法，分为三元组（个、十、百）
        • pCjAgoV.png
      • 进行第一趟的分配，将个位满足相应关键字位的元素入队（先进先出）
        • pCjAOJO.png
      • 进行第一趟收集，使这些元素依次出队
        • pCjE9eI.png
      • 进行第二趟分配与第三趟分配，最终得到相应的结果
    • 基数排序的性能分析
      • 基数排序擅长解决的问题
        • 数据元素的关键字可以方便地拆分为d组，且d较小
        • 每组关键字的取值范围不大，即”较小
        • 数据元素个数n较大
      • 基数排序只能对int型进行排序，无法对float型以及double型进行排序
      • 空间复杂度：取决于分组队列的情况，r个队列，空间复杂度为O(r)
      • 时间复杂度：基数排序需要进行d趟分配和收集，一趟分配需要O(n)，一趟收集需要O(r)，时间复杂度为O($d(n+r)$），
        它与序列的初始状态无关。
      • 基数排序是一种稳定的排序

6.各种内部排序算法的比较及应用（✪）

  • 各种内部算法的比较
    • 时间复杂度分析
      • 平均时间复杂度为O($n^{2}$)：直接插入排序、折半插入排序、简单选择排序、冒泡排序
        • 直接插入排序、冒泡排序最好情况下的时间复杂度为：O($n$)（在基本有序的情况下）
        • 简单选择排序与序列的初始状态无关
      • 平均时间复杂度为O($nlog_2n$)：快速排序、堆排序、归并排序
        • 快速排序的最坏时间复杂度为：O($n^{2}$)（在基本有序的情况下）
        • 堆排序和归并排序的在最好、最坏和平均情况下, 堆排序的时间复杂度为：${O\left(n \log _{2} n\right)}$
      • 希尔排序作为插入排序的拓展，对较大规模的数据都可以达到很高的效率，但目前未得出其精确的渐近时间
      • 基数排序的时间复杂度取决于划分的组数d、组内的队列数r、元素数量n，时间复杂度为：O($d(n+r)$)
    • 空间复杂度分析
      • 空间复杂度为O($1$)：插入排序（直接插入、折半插入、希尔排序）、冒泡排序、选择排序（简单选择排序、堆排序）
        仅需要借助常数个辅助空间
      • 空间复杂度为O($log_2{n}$)：快速排序需要借助一个递归工作栈
        • 快速排序在最坏情况下的空间复杂度可能达到O($n$)
      • 空间复杂度为O($n$)：归并排序
    • 稳定性分析
      • 稳定的排序算法：直接插入排序、折半插入排序、冒泡排序、归并排序、基数排序
        • 平均时间复杂度为O($nlog_2n$)的排序只有归并排序
      • 不稳定的排序算法：希尔排序、快速排序、选择排序（简单选择排序、堆排序）
    • 过程特征分析
      • 排序趟数与序列的原始状态的关系
        • 趟数与原始序列状态无关：插入类、选择类的排序、基数排序
          • 直接插入排序(每次固定插入一个元素)、简单选择排序(每次都选出一个最大/最小的元素) 均为n-1趟排序
          • 基数排序：每趟都要进行分配和收集，排序趟数固定为d
        • 趟数与原始序列状态有关：交换类的排序(冒泡排序、快速排序)
          • 冒泡排序如果为顺序，只需要进行一趟排序（本趟无元素交换）；若为逆序需要进行n-1趟排序
          • 快速排序若每趟的枢纽元素都能平均的划分两个子序列则需要的趟数最少，若原始序列有序，则需要的趟数最多
      • 比较次数与序列的原始状态的关系
        • 比较次数与序列的原始状态无关：折半插入排序、选择类的排序(简单选择排序、堆排序)
          • 折半插入排序的比较次数仅取决于表中的元素个数n
          • 简单选择排序的关键字比较次数恒为：n(n−1)/2次
        • 比较次数与序列的原始状态有关：直接插入排序、希尔排序、冒泡排序、快速排序
          • 直接插入排序最好只做n-1次关键字比较（顺序时），最坏做n(n−1)/2次关键字比较（逆序时）
          • 冒泡排序顺序时比较次数为n-1次，逆序时比较次数为n(n−1)/2次
      • 移动次数与序列的原始状态的关系
        • 元素的移动次数与序列的原始状态无关：基数排序
        • 元素的移动次数与序列的原始状态有关：直接插入排序、折半排序、冒泡排序、快速排序、简单选择排序
          • 直接插入排序在顺序的情况下，不需要移动元素；若逆序需要移动大量元素
          • 冒泡排序有序时不需要移动元素；若逆序时需要移动3n(n-1)/2次
          • 快速排序若每趟的枢纽元素都能平均的划分两个子序列则需要的移动的次数少，
            若原始序列有序，则需要移动的次数最多
          • 简单选择排序在有序的情况下不需要移动元素
      • 每趟排序结束后都至少能确定一个元素的最终位置的排序算法：冒泡排序、快速排序、简单选择排序、堆排序
  • 内部排序算法的应用
    • 基于关键字个数n选择排序算法
      • 若n较小，可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多，
        因而当记录本身信息量较大时，用简单选择排序较好。
      • 若n较大，则应采用时间复杂度为O($nlog_2{n}$)的排序方法：快速排序、堆排序或归并排序。
        快速排序被认为是目前基于比较的内部排序方法中最好的方法
      • 当待排序的关键字随机分布时，快速排序的平均时间最短。
        堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况，这两种排序都是不稳定的。
      • 若n很大，记录的关键字位数较少且可以分解时，采用基数排序较好。
    • 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
    • 若要求排序稳定且时间复杂度为O($log_2{n}$)，则可选用归并排序。
      • 但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。
        先利用直接插入排序求得较长的有序子文件，然后两两归并。直接插入排序是稳定的，因此改进后的归并排序仍是稳定的。
    • 在基于比较的排序方法中，每次比较两个关键字的大小之后，仅出现两种可能的转移，
      因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要O($nlog_2{n}$)的时间。
    • 当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构。
      • 但是希尔排序和堆排序利用顺序存储的随机访问特性，如果将其换为链式存储结构其时间复杂度将增加

7.外部排序（✪）

  • 外部排序的基本概念与方法

    • 外部排序的基本概念
      • 外部排序：数据元素太多，无法一次全部读入内存进行排序。
      • 因此，需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，
        在排序过程中需要多次进行内存和外存之间的交换。这种排序方法就称为外部排序。
    • 外部排序的方法
      • 外部排序通常采用归并排序法。它包括两个阶段：
        • 根据内存缓冲区大小，将外存上的文件分成若干长度为L的子文件，依次读入内存并利用内部排序方法对它们进行排序
          并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串
        • 对这些归并段在内存中进行逐趟归并，使归并段（有序子文件）逐渐由小到大，直至得到整个有序文件为止。
      • 使用“归并排序”的方法，最少只需在内存中分配3块大小的缓冲区即可对任意一个大文件进行排序
      • 在内存中，归并后的对象顺序存放在输出缓冲区中，若缓冲区的对象存满，则将其顺序写到输出归并段中并清空缓冲区
      • 若某个输入缓冲区中的对象在移动到输出缓冲区之后为空，则从其对应的输入归并段中再读取下一块，继续参加归并
    • 外部排序进行归并的流程
      • 内存读取外存的子文件进行内部排序，将排序好的有序子文件依次返回外层，这些有序子文件又称为归并段
        • pCjLMSf.png
      • 经过16次读和16次写之后，由于经过了内存中的内部排序，此时在外存中形成了初始归并段
        • pCjO8gK.png
        • 此时对这8个初始归并段在内存中进行第一趟归并，需要读16次，写16次
          • pCjXKsS.png
        • 在进行了第一趟归并之后，形成了4个新的归并段，之后需要对这4个归并段在内存中进行进一步的归并（第二趟归并）
          • pCjXCrD.png
        • 此时对这4个归并段在内存中进行归并操作，依旧需要读16次，写16次，最后会形成一个新的2个归并段，
          此时再进行一次归并即可得到最终的有序序列
          • pCjX6Rx.png

    • 外部排序的优化

      • 在外部排序中实现两两归并时，由于不可能将两个有序段及归并结果同时存放在内存中，
        因此需要不停地将数据读出、写入磁盘，这会消耗大量的时间
        • pCjLzng.png
      • 多路平衡归并
        • ${\mathrm{k}}$路平衡归并的概念
          • 最多只能有${\mathrm{k}}$个段归并为一个
          • 每一趟归并中, 若有${\mathrm{m}}$个归并段参与归并, 则经过这一趟处理得到${\lceil\mathrm{m} / \mathrm{k}\rceil}$个新的归并段
          • 图片
            • 4路平衡归并
              • pCvSMUe.png
            • 4路归并
              • pCvSGvt.png
        • 可以用多路归并的方法进行优化，采用4路归并时，只需要两趟归并，总读写次数为=32*2+32=96
          • pCjjmk9.png
        • 在做m路平衡归并排序的过程中，为实现输入/内部归并/输出的并行处理，需要设置2m个输入缓冲区和2个输出缓冲区
          以便在执行内部归并时，能同时进行输入输出操作。若仅设置m个输入缓冲区，则仅能进行串行操作，无法并行处理。

    • 对于优化归并趟数(读写次数)的分析

      • 对r个初始归并段，做k路归并，则归并树可用K叉树来表示
      • 若树高为h，则归并趟数$=\mathbf{h}-\mathbf{1}=\left\lceil\log _{k} r\right\rceil $
        • 推导：${\mathrm{k}}$叉树第${\mathrm{h}}$层最多有${k^{h-1}}$个结点，则${r \leq k^{h-1},(\mathrm{h}-1)}$最小${=\left\lceil\log _{k} r\right\rceil}$
        • 由此，k越大，r越小，则归并趟数越少，读写次数越少
      • 可以增加输入缓冲区的数量来提高$K$（归并路数），即实现多路归并，但是会产生一些负面影响
        • k路归并时，需要开辟k个输入缓冲区，内存开销增加。
        • 每挑选一个关键字需要对比关键字(k-1)次，内部归并所需时间增加（可以设置败者树来解决此问题）
      • 可以减少初始归并段数量$r$来减少归并趟数，
        生成初始归并段的“内存工作区”越大，初始归并段越长，此时初始归并段的数量越少
        • 若共${\mathbf{N}}$个记录, 内存工作区可以容纳${\mathrm{L}}$个记录, 则初始归并段数量 $\mathrm{r}=\lceil N / L\rceil$
        • 可用“置换-选择排序”进一步减少初始归并段数量

  • 败者树

    • 败者树可以在多路归并时减少每挑选一个关键字时的比较次数，提高内部归并的时间
    • 对于k路归并，第一次构建败者树时，需要对比关键字k-1次
      • pCvp6Wd.png
    • 有了败者树, 选出最小元素, 对于每一次比较只需对比关键字${\left\lceil\log _{2} k\right\rceil}$次
      • pCv9pY4.png
    • 例题
      • pCvX4EQ.png

  • 置换-选择排序（生成初始归并段的优化方法）

    • 使用置换-选择排序，可以让每个初始归并段的长度超越内存工作区大小的限制
    • 在内存工作区中传入待排序文件的关键字，内存工作区满了之后，选择其中最小的输出，
      此时设置MINIMAX记录输出关键字的信息，下一个输出的关键字必须大于MINIMAX，否则无法输出
      • pCv90cn.png
    • 三个关键字都小于MINIMAX时，均无法输出，此时第一个归并段构建完成，可以构建下一个新的归并段
      • pCv94j1.png
    • 最后将构建出数量r较少的初始归并段
      • pCv9X3d.png

  • 最佳归并树

    • 归并过程中的磁盘I/O次数=归并树的WPL*2

      • pCvP5TK.png

    • 最佳归并树指此时的I/O时间最小的树，可以由构造哈夫曼树的方法来构造

      • 此时将归并段看做树的带权结点选取最小的组合来构造
      • 2路归并的最佳归并树
        • pCviEmq.png
      • 多路归并的最佳归并树
        • pCvXWDS.png

    • k叉归并的最佳归并树一定是严格k叉树，即树中只有度为k、度为0的结点

    • 对于k叉归并，若初始归并段的数量无法构成严格的k叉归并树，则需要补充几个长度为0的“虚段”，再进行k叉哈夫曼树的构造

      • pCvXBAH.png

    • 如何判断初始归并段的数量无法构成严格k叉归并树以及需要添加虚段的数量

      • pCvX3N9.png
-------------本文结束-------------