3

数据结构

 2 years ago
source link: https://xie.infoq.cn/article/d9fed4fe29a5ed375d3362c30
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

  • 回顾：之前的【图解数据结构】排序全面总结(上)对插入类和交换类排序作了比较详细的总结，要求对于直接插入、折半插入排序、冒泡排序要求熟练掌握

  • 学习目标：本章内容要求熟练掌握简单选择排序算法，了解树形选择排序、堆选择排序、归并排序、基数排序的特点、时空复杂度、算法流程。

二、选择类排序

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

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 个指针域

五、总结归纳


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK