【图解数据结构】排序全面总结 (下)

作者：知心宝贝

2022 年 3 月 24 日
本文字数：2085 字
阅读完需：约 7 分钟

一、前言

回顾：之前的【图解数据结构】排序全面总结(上)对插入类和交换类排序作了比较详细的总结，要求对于直接插入、折半插入排序、冒泡排序要求熟练掌握
学习目标：本章内容要求熟练掌握简单选择排序算法，了解树形选择排序、堆选择排序、归并排序、基数排序的特点、时空复杂度、算法流程。

二、选择类排序

定义：每次从待排序的无序序列中，选择一个最大或最小的数字，放到前面，数据元素为空时排序结束

1.简单选择排序

动态演示：

算法讲解：

从第 1 个数字开始依次向后寻找比这个数小的下标，最后交换元素
从第 2 个数字开始依次向后寻找比这个数小的下标，最后交换元素
总共重复上述操作 n-1 次，排序完成

代码：

void SelectSort(RecordType r[], int length)/*对记录数组r做简单选择排序，length为数组的长度*/{  int i,j,k,n=length;          RecordType x;      for ( i=1 ; i<= n-1; ++i)    {    k=i;    for (j=i+1 ; j<= n ; ++j)       if (r[j].key < r[k].key ) k=j;    if ( k!=i)      {          x= r[i];   r[i]= r[k];   r[k]=x;    }  }  }

复制代码

特点：

不稳定排序
时间复杂度 O(n*n), 空间复杂度 O(1)

2.树形选择排序

静态演示：

算法讲解：

最下面一行 21 25 49 25 16 08 63 是给定需要从小到大排序的数字
相邻的两个选出一个最小的向上移一层，只有一个的补一个值无穷大的数
倒数第二层再次两两组合，直到最顶端
此时，最顶端 08 就是值最小的数，输出 08，把所有 08 至为无穷大
再次选出一个最小值，以此类推

特点：

算法不作要求
稳定排序, 增加额外的存储空间
时间复杂度 O（nlogn）,空间复杂度 O(n-1)

3.堆选择排序

动态演示：

算法讲解：

根结点值最大的叫大顶堆，根结点值最小的叫小顶堆，上图就是一个构造大顶堆的图
从最后一层开始，如果孩子结点的值比父亲结点大，那么就交换位置
一层层向上推，直到根结点值最大

建立初始堆：

void crt_heap(RecordType r[], int length )/*对记录数组r建堆，length为数组的长度*/{  int i,n;        n= length;  for ( i=n/2; i >= 1; --i) /* 自第[n/2]个记录开始进行筛选建堆 */     sift(r,i,n);}

复制代码

调整堆：

void  sift(RecordType  r[],  int k, int m)/* 假设ｒ[k..m]是以ｒ[k]为根的完全二叉树，且分别以ｒ[2k]和ｒ[2k+1]为根的左、右子树为大根堆，调整r[k]，使整个序列r[k..m]满足堆的性质 */{  RecordType t;  int i,j;  int x;  int finished;  t= r[k];          /* 暂存"根"记录r[k] */        x=r[k].key;  i=k;  j=2*i;  finished=FALSE;  while( j<=m && !finished  )     {              if (j<m  && r[j].key< r[j+1].key )  j=j+1;   /* 若存在右子树，                                                     且右子树 根的关键字大，则沿右分支"筛选" */         if ( x>= r[j].key)  finished=TRUE;            /*  筛选完毕  */          else          {   r[i] = r[j];  i=j;  j=2*i;  }    /* 继续筛选 */     }    r[i] =t;          /* r[k]填入到恰当的位置 */ }

复制代码

堆排序：

void  HeapSort(RecordType  r[],int length)/* 对r[1..n]进行堆排序，执行本算法后，r中记录按关键字由大到小有序排列 */ {  int i,n;  RecordType b;  crt_heap(r, length);  n= length;  for (  i=n ; i>= 2; --i)   {    b=r[1];     /* 将堆顶记录和堆中的最后一个记录互换 */     r[1]= r[i];    r[i]=b;     sift(r,1,i-1);  /* 进行调整，使r[1..i-1]变成堆 */   }} /* HeapSort */

复制代码

特点：

堆选择是树形的改进，空间占用较小
不稳定排序，适合 n 值较大的排序
时间复杂度 O(n*logn)，空间复杂度 O(1)

三、归并排序

法一：

将整体数字一分为二，逐层细分
细分完成后，每一块进行排序，直到整体有序

法二：

将一串序列，相邻的两个归并到一起排序，再次把相邻两个有序的归并块再次排序，直到最后有序（优先推荐这种算法）

代码：

void MergeSort ( RecordType  r[], int n) /* 对记录数组r[1..n]做归并排序 */ {  MSort ( r, 1, n, r);}void   MSort(RecordType  r1[],  int  low,  int  high,  RecordType  r3[])/* r1[low..high]经过排序后放在r3[low..high]中，r2[low..high]为辅助空间 */ {  int mid;   RecordType  r2[20];  if (low==high)   r3[low]=r1[low];  else  {    mid=(low+high)/2;        MSort(r1,low, mid, r2);        MSort(r1,mid+1,high, r2);        Merge (r2,low,mid,high, r3);     }} /*   MSort  */

复制代码

特点：

稳定排序
时间复杂度 O(nlogn)，空间复杂度 O(n)
附加空间比较大，很少用于内部排序，主要是外部排序

四、分配类排序

1.多关键字排序

高位优先：按照花色大小分成四类，在每一类中按照面值进行排序
低位优先： 按照面值大小分成 13 类，将相同面值的不同花色进行排序

2.链式基数排序

算法讲解：

对于上面的 9 个三位数，第一步我们按照个位数从小到大排序
接着第一步的结果，按照十位数从小到达排序
最后借助第二步的结果，按照百位数从小到大排序
同样的，对于 4 位 5 位方法一样

特点：

时间复杂度 O(d*n)，d 是关键字数，n 是记录数
稳定的排序
空间复杂度=2 个队列指针+n 个指针域

五、总结归纳

发布于: 2022 年 03 月 24 日阅读数: 44

原文链接:【http://xie.infoq.cn/article/d9fed4fe29a5ed375d3362c30】。文章转载请联系作者。

知心宝贝

关注

公众号：穿越计算机的迷雾 2022.03.07 加入

生于尘埃溺于人海死于理想高台

评论 (1 条评论)

发布

知心宝贝

冲冲冲

2022 年 03 月 24 日 17:16

 0 回复

没有更多了

创作场景

【图解数据结构】排序全面总结 (下)

一、前言

二、选择类排序

1.简单选择排序

2.树形选择排序

3.堆选择排序

三、归并排序

四、分配类排序

1.多关键字排序

2.链式基数排序

五、总结归纳

知心宝贝

评论 (1 条评论)