数据结构第八章

8 排序

8.1 基本概念和排序方法概述

8.1.1 排序的基本概念

• 排序：将一组杂乱无章的数据按照一定规律顺次排列起来，即，将无需数列排成一个有序序列（由小到大或由大到小）的运算。

  • 如果参加排序的数据结点包含多个数据域，那么排序往往是针对其中某个域而言
  • 排序方法的分类：
    • 按数据存储介质：内部排序和外部排序
      • 内部排序：数据量不大，数据在外存，无需内外存交换数据
      • 外部排序：数据量较大，数据在外存（文件排序）
        • 外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多
    • 按比价器个数：串行排序和并行排序
      • 串行排序：单处理机（同一时刻比较一对元素）
      • 并行排序：多处理机（同一时刻比较多对元素）
    • 按主要操作：比较排序和基数排序
      • 比较排序：用比较的方法
        • 插入排序、交换排序、选择排序、归并排序
      • 基数排序：不比较元素的大小，仅仅根据元素本身的取值确定其有序位置
    • 按辅助空间：原地排序和非原地排序
      • 原地排序：辅助空间用量为O(1)的排序方法（所占用的辅助存储空间与参与排序的数据量大小无关）
      • 非原地排序：辅助空间用量超过O(1)的排序方法
    • 按稳定性：稳定排序和非稳定排序
      • 稳定排序：能够使任何数值相等的元素，排序以后相对次序不变。
      • 非稳定排序：不是稳定排序的方法
    • 按自然性：自然排序和非自然排序
      • 自然排序：输入数据越有序，排序的速度越快的排序方法
      • 非自然排序：不是自然排序的方法

• 接下来的学习内容：

• 按排序依据原则：

  • 插入排序：直接插入排序、折半插入排序、希尔排序
  • 交换排序：冒泡排序、快速排序
  • 选择排序：简单选择排序、堆排序
  • 归并排序:：2-路归并排序
  • 基数排序

• 按排序所需工作量

  • 简单的排序方法：$ T(n)=O(n^2)$
  • 基数排序：$ T(n)=O(d.n)$
  • 先进的排序方法：$ T(n)=O(nlogn)$

• 存储结构——记录序列以顺序表存储

  #define MAXSIZE 20			//设记录不超过20个
  typedef int KeyType;		//设关键字为int型

  Typedef struct{
      KeyType key;					//关键字
      infoType otherinfo;				//其他数据项
  }RedType;

  Typedef struct{					//定义顺序表的结构
      RedType r[MAXSIZE +1];		//存储顺序表的向量
      							//r[0]一般作哨兵或缓冲区
      int length;					
  }SqList;

8.2 插入排序

• 基本思想：
  • 在有序序列中插入一个元素，保持序列有序，有序长度不断增加
• 插入排序的种类
  • 顺序法定位插入位置——直接插入排序
  • 二分法定位插入位置——二分插入排序
  • 缩小增量多遍插入排序——希尔排序

8.2.1 直接插入排序

• 直接插入排序——采用顺序查找法查找插入位置

  1. 复制插入元素

  2. 记录后移，查找插入位置

     for(j=i-1;j>=0&&x<a[j]；j--)
         a[j+1]=a[j];

  3. 插入到正确位置

• 直接插入排序，使用“哨兵”

  1. 复制为哨兵 L.r[0]=L.r[i];
  2. 记录后移，查找插入位置
  3. 插入到正确位置

void InserSort(SqList &L){
    int i,j;
    for(i=2;i<=L.length;++i){
        if(L.r[i].key<L.r[i-1].key){
            L.r[0]=L.r[i];
            for(j=i-1;L.r[0].key<L.r[j].key;--j){
                L.r[j+1]=L.r[j];
            }
        }
        L.r[j+1]=L.r[0];
    }
}

• 平均的情况：
  • 比较次数$\sum\limits^{n-1}_{i=1} \dfrac{i+1}{2}=\dfrac{1}{4}(n+2)(n-1) $
  • 移动次数$\sum\limits^{n-1}_{i=1} （\dfrac{i+1}{2}+1）=\dfrac{1}{4}(n+6)(n-1) $
• 时间复杂度结论
  • 原始数据越接近有序，排序速度越快
  • 最坏情况下（输入数据是逆有序的） $Tw(n)=O(n^2)$
  • 平均情况下，耗时差不多是最坏情况的一半 $Te(n)=O(n^2)$
  • 要提高查找速度
    • 减少元素的比较次数
    • 减少元素的移动次数

8.2.2 折半插入排序

void BinsertSort(SqList &L)｛   						//对顺序表L做折半插入排序
for (i=2;i<=L.length;++i){
    L.r[O]=L.r[i];
	low=l;high=i-1;
	while(low<=high){
        m=(low+high)/2;
		if(L.r[O].key<L.r[mid].key) high=mid-1;		//插入点在前一子表
		else low=mid+1;								//插入点在后一子表
    }
    for (j=i一l;j>=high+l; --j) L.r[j+l]=L.r(j]; 	//记录后移
	L.r[high+l]=L.r[O]; 							//将r[O]即原r[i], 插入到正确位置
	}
}

• 算法特点：
  • 稳定排序
  • 应为要进行折半查找，所以只能用于顺序结构，不能用于链式结构
  • 适合初始记录无序，n较大时的情况
• 算法分析：
  • 时间复杂度为$O(n^2)$
  • 空间复杂度为$O(1)$

8.2.3 希尔排序

• 基本思想：

  • 先将整个待排记录序列分割成若干子序列，分别进行直接插入排序待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

• 算法特点：

  • 一次移动，移动位置较大，跳跃式地接近排序后的最终位置
  • 最后一次只需要少量移动
  • 增量序列必须是递减的，最后一个必须是1
  • 增量序列应该是互质的

• 算法举例：

  

• 算法代码：

  void shellsort(Sqlist &L,int dlta[],int t){
      for(k=0;k<t;++k)
          shellinsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序
  }

  void shellinert（SqList &L，int dk)
      for(i=dk+1;i<=L.length;++i)
          if(r[i].key<r[i-dk].key){
              r[0]=r[i];
              for(j=i-dk;j>0 &&（r[0].key<r[j].key);j=j-dk)
                  r[j+dk]=r[j];
              r[j+dk]=r[0]
          }

• 算法分析：

  • 时间复杂度是n和d的函数：
    • $O(N^{1.25})到O(1.6n^{1.25})——经验公式 $
    • 时间复杂度为$O(1)$
    • 是一种不稳定的排序方法

8.3 交换排序

8.3.1 冒泡排序

• 基本思想：每趟不断将记录两两比较，并按“前小后大”规则交换

void bubble_sort(SqList &L){
    int m,j,i; RedType x;
    for(m=1;m<=n-1;m++){
        for(j=1j=n-m;j++)
            if(L.r[j].key>L.r[j+1].key){
                x=L.r[j];
                L.r[j]=L.r[j+1];
                r[j+1]=x
            }
    }
}

• 改进的冒泡排序算法

  void bubble_sort(SqList &L){
      int m,j,i,flag=1; RedType x; 
      for(m=1;m<=n-1&&flag==1;m++){		//用flag作为是否有交换的标记
          flag=0；
          for(j=1j=n-m;j++)
              if(L.r[j].key>L.r[j+1].key){
             		flag=1 					//若发生交换，flag置为1
                  x=L.r[j];
                  L.r[j]=L.r[j+1];
                  r[j+1]=x
              }
      }
  }

• 冒泡排序算法评价

  • 冒泡排序最好时间复杂度是$O(n)$
  • 冒泡排序最坏时间复杂度为$(n^2)$
  • 冒泡排序平均时间复杂度为$O(n^2)$
  • 冒泡排序算法中增加一个辅助空间temp，辅助空间为$S(n)=O(1)$
  • 冒泡排序是稳定的

8.3.2 快速排序

• 基本思想

  • 任取一个元素为中心
  • 所有比他小的元素一律前放，比他大的后放，形成左右两个子表
  • 对各子表重新选择中心元素并依此规则调整
  • 知道每个子表的元素只剩一个

• 快速排序演示

  

• 算法图解：

  

• 排序算法：

  int partition(SqList &L,int low,int high){
      L.r[0]=L.r[low];									//用子表的第一个记录做枢轴记录
      pivotkey=L.r[low].key;								//枢轴记录关键字保存在pivotkey中
      while(low<high){									//从表的两端交替地向中间扫描
          while(low<high&&L.[high].key>=pivotkey)--high;
          L.r[low]=L.r[high];								//将比枢轴记录小的移动到低端
          while(low<high&&L.[low].key>=pivotkey)++low;
          L.r[high]=L.r[low];								//将比枢轴记录大的移动到高端
      }
      L.r[low]=L.r[0];									//枢轴记录到位
      return low;											//返回枢轴记录
  }
  void QSort(SqList &L,int low,int high){
      if(low<high){
          pivotloc=Partition(L,low,high);					//将L.r[low,high]一分为二。pivotloc是枢轴记录
          QSort(L,low,pivotloc-1);						//对左子表递归排序
          QSort(L,pivotloc+1,high);						//对右子表递归排序
      }
  }
  void QuickSort(SqList &L){
      QSort(L,1,L.length);								//对顺序表L做快速排序
  }

• 快速排序算法分析：

  • 时间复杂度

    • 平均计算时间是$O(nlog_2n)$
    • 实验表明快速排序是我们所讨论的所有内排序方法中最好的一个。

  • 空间复杂度

    • 快速排序不是原地排序
    • 平均情况下：需要$O(logn)$的栈空间
    • 最坏情况下：栈空间可达$O(n)$

  • 快速排序不适于队原本有序或基本有序的记录序列进行排序

8.4 选择排序

8.4.1 简单选择排序

• 基本思想：

  • 在待排序的数据中选出最大(小)的元素放在其最终的位置。

  

• 算法代码

  void SelectSort(SqList &K){
      for(i=1;i<L.length;++i){
          k=i;
          for(j=i+1;j<=L.length;j++)
              if(L.r[j].key<L.r[k].key)k=j;		//记录最小值位置
          if(k!=i){
              x=L.r[i];
              L.r[i]=L.r[k];
              L.r[k]=x;
          }
      }
  }

• 算法分析

  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(1)$

• 简单选择排序是不稳定排序

8.2.2 堆排序

• 若有n个元素${a_1,a_2,……,a_n}$满足
  $$
  \left{
  \begin{array}{l}
  a_i<=a_{2i}\
  a_i<=a_{2i+1}\
  \end{array}
  \right.
  \quad\text{或者}\quad
  \begin{cases}
  a_i>=a_{2i}\
  a_i>=a_{2i+1}\
  \end{cases}
  $$

  • 则分别称该序列为小根堆和大根堆。

  • 从堆 定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于(大于)它的孩子结点

• 若在输出堆顶的最小值 (最大值) 后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值 (次大值) …如此反复，便能得到一个有序序列，这个过程称之为堆排序。

• 堆的调整

  • 小根堆
    1. 输出堆顶元素之后，以堆中最后一个元素替代之
    2. .然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换，
    3. 重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选“

• 算法描述

  void HeapAdjust(elem R[],int s, int m){
      rc=R[s];
      for(j=2*S;J<=M;J*=2){//沿key较大的孩子结点向下筛选
          if(j<m&&R[j]<R[j+1])++j;//j为key较大的记录的下标
          if(rc>=R[j])break;
          R[s]=R[j];
          s=j;//rc应插入在位置s上
      }
      R[s]=rc;//插入
  }

• 堆的建立

  • 单结点的二又树是堆;

  • 在完全二叉树中所有以叶子结点 (序号i > n/2) 为根的子树是堆这样，我们只需依次将以序号为$n/2，n/2-1，…,1$的结点为根的子树均调整为堆即可。

    从最后一个非叶子结点开始，以此向前调整

    1. 调整从第$n/2$个元素开始，将以该元素为根的二叉树调整为堆
    2. 将以序号为$n/2 - 1$的结点为根的二叉树调整为堆
    3. 再将以序号为$n/2 - 2$的结点为根的二又树调整为堆
    4. 再将以序号为$n/2 - 3$的结点为根的二又树调整为堆

  • 通过以上分析可知：

    • 若对一个无序序列建堆，然后输出根；重复该过程就可以由一个无序序列输出有序序列。
    • 实质上，堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的

• 堆排序算法

  void HeapSort（elem R[]){			//对R[1]到R[n]进行堆排序
      int i;
      for(i=n/2;i>=1;i--)
          HeapAdjust(R,i,n);			//建立初始堆
      for(i=n;i>1;i--){				//进行n-1趟排序
          Swap(R[1],R[i]);			//根与最后一个元素交换
          HeapAdjust(R,1,i-1);		//对R[1]到R[i-1]重新建堆
      }
  }

• 算法分析

  • 初始化堆所需时间不超过O(n)
  • 堆排序在最坏情况下，其时间复杂度也为$O(nlog_2 n)$，这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列，都不会使堆排序处于"最好”或"最坏“的状态。

8.5 归并排序

• 基本思想：

  • 将两个或两个以上的有序子序列“归并”为一个有序序列
  • 在内部排序中，通常采用的是2-路归并排序。

• 排序示例：

  

  • 整个归并排序仅需[$log_2 n $]趟

• 算法分析：

  • 时间效率：$O(nlog_2n)$
  • 空间效率：$O(n)$、
    • 因为需要一个与原始序列同样大小的辅助序列。这正是此算法的缺点
  • 具有稳定性

8.6 基数排序

• 基本思想：

  • 分配+收集
  • 也叫桶排序或箱排序: 设置若干个箱子，将关键字为k的记录放入第k个箱子，然后在按序号将非空的连接。

• 算法示例：

  

  • 将这组数据第一趟按照个位排，然后收集回来
  • 接下来按照十位来排，接下来收集回来
  • 最后按照百位来排，收集回来时，我们可以发现已经有序了

• 算法分析

  • 时间效率：O(k*(n+m))
    • k：关键字个数
    • m：关键字取值范围位m个值

  总结：