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

作者：知心宝贝

2022 年 3 月 23 日
本文字数：2736 字
阅读完需：约 9 分钟

一、前言

学习目标

理解排序基本概念以及稳定性，时空复杂度以及适用场景
熟练掌握直接插入排序、折半插入排序、冒泡排序这三种常见的排序算法
了解希尔排序、快速排序的执行过程以及算法

二、基本概念

1.定义

将一组无序的数据元素调整为有序的数据元素，有序分为从小到大，从大到小两种。

2.排序方法的稳定性

 0  1   2    3   4   5   6   7  8  9  5  4  "10"  11  22  8  10  76  1  2

复制代码

解读： 如上个表格这样的一个无序数组，想要将它按照从小到大排序。上图下标 2 和 6 对应的数字都是 10，排序后假如带引号的"10"最后还在不带引号的 10 前面，那这种排序方法就是稳定的，否则排序方法不稳定。

3.内部和外部排序

内部排序： 整个排序过程在内存中
外部排序： 排序的数过大，内存和外部存储器之间需要进行多次数据交换

三、插入类排序

插入类：在一个有序序列插入一个新的记录，使之仍然有序

1.直接插入排序

动态演示：

算法讲解：

上面的动态图可以很好的表达直接插入的过程，只是动态图有点长
首先将 0 作为监视哨，用一个指针从前往后找后面的数字比前面数字小的，找到了放到 0
指针开始向前移动，如果指向的值比监视哨里的值大，数字向后移
如果指向的值比监视哨里的值小，那把监视哨里的值存入这个元素之后
后面的排序数字，以此类推

代码：

void InsSort(RecordType  r[],  int length)/* 对记录数组r做直接插入排序，length为数组中待排序记录的数目*/{   int i,j;  for (i=2;  i<=length;  i++)   {    r[0]=r[i];      /*将待插入记录存放到监视哨r[0]中*/    j=i-1;               while (r[0].key< r[j].key )     /* 寻找插入位置 */    {      r[j+1]= r[j];       j=j-1;    }    r[j+1]=r[0];  /*将待插入记录插入到已排序的序列中*/  }} /*  InsSort  */

复制代码

特点：

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

2.折半插入排序

算法讲解：

动态图演示没搞到，只能用上面这张图片了，将就看一下
折半插入和二分查找思想差不多，对于一个有序的数组，将一个数字插入之后任然有序
k 代表要插入的值 low=1, high=length , mid=(low+high)+1
mid 对应的值如果比 k 大， high=low-1,否则 low=mid+1
当 low >high ，low 后面就是 k 插入的位置

代码：

void BinSort (RecordType  r[],  int length)/*对记录数组r进行折半插入排序，length为数组的长度*/{  int i,j;    RecordType x;      int low,high,mid;  for (i=2; i<=length ; ++i )   {    x= r[i];  low=1;  high=i-1;    while (low<=high )                  /* 确定插入位置*/     {      mid=(low+high) / 2;      if ( x.key< r[mid].key) high=mid-1;      else   low=mid+1;    }    for ( j=i-1 ; j>= low; --j )   r[j+1]= r[j];    /*  记录依次向后移动 */     r[low]=x;   /* 插入记录 */   }}/*BinSort*/

复制代码

特点：

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

3.希尔排序

动态演示：

算法讲解：

对于希尔排序来说取增量 d (d 一般为奇数，并且逐次递减)
上图第一次排序 d 等于 5，将第一个作为起始点，下标+5 取下一个值，一直到最后，将去到的值从小到达排序，然后将第二个作为起始点，3 4 5 依次作为起始点排序
第二次是 d 等于 3
第三次是 d 等于 1

代码：

void  ShellInsert(RecordType r[], int length,  int  delta)/*对记录数组r做一趟希尔插入排序，length为数组的长度,delta 为增量*/{  int i,j;  for(i=1+delta;i<= length; i++)     /* 1+delta为第一个子序列的第二个元素的下标 */    if(r[i].key < r[i-delta].key)    {      r[0]= r[i];          /*  备份r[i]  (不做监视哨) */      for(j=i-delta; j>0 &&r[0].key < r[j].key; j-=delta)        r[j+delta]= r[j];        r[j+delta]= r[0];    }}/*ShellInsert*/

复制代码

特点：

不稳定排序
增量序列的 d 取值无除 1 之外的公因子，最后一个增量值必须为 1
时间复杂度 O(n*logn) 空间复杂度 O(1)

四、交换类排序

1.冒泡排序

动态演示：

算法讲解：

设立两个指针，i，j
每一次排序都会把最大的一个数放到后面，依次类推，假设执行 2 次以后，那么最后 2 个数就不需要比较了
执行 n-1 次排序，结果完成

代码：

void  BubbleSort(RecordType r[], int length )/*对记录数组r做冒泡排序，length为数组的长度*/{  int n,i,j; nt change; RecordType x; n=length;  change=TRUE;    for ( i=1 ; i<= n-1 && change ;++i )     {  change=FALSE;        for ( j=1 ; j<= n-i ; ++j)           if (r[j].key > r[j+1].key )            {            x= r[j];            r[j]= r[j+1];            r[j+1]= x;            change=TRUE;          }     }} /*  BubbleSort

复制代码

特点：

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

2.快速排序

动态演示：

算法讲解：

快速排序讲起来稍微有点复杂，其实就是划分区域
建立两个指针 low high 分别指向第一个和第二个元素，把第一个元素的值赋给 x 变量
high 向前移动，假如 high 指向的值小于 x，则 high 指向的值与 x 互换
low 向后移动，假如 low 指向的值大于 x，则 low 指向的值与 x 互换
重复 3 4 两步，知道 high==low，第一次结束
将 low 指向第二个元素，把第二个元素的值赋给 x 变量
重复操作，知道元素有序

1.递归算法

void QKSort(RecordType r[],int low, int high )/*对记录数组r[low..high]用快速排序算法进行排序*/{  int pos;  if(low<high)  {    pos=QKPass(r, low, high);  /*调用一趟快速排序，将枢轴元素为界划分两个子表*/    QKSort(r, low, pos-1);     /*对左部子表快速排序*/    QKSort(r, pos+1, high); /*对右部子表快速排序*/      }}

复制代码

2.非递归算法：

int QKPass(RecordType r[],int left,int right)/*对记录数组r 中的r[left]至r[right]部分进行一趟排序，并得到基准的位置，使得排序后的结果满足其之后（前）的记录的关键字均不小于（大于）于基准记录*/{   RecordType x;  int low,high;  x= r[left];             /* 选择基准记录*/   low=left;    high=right;  while ( low<high )  {    while (low< high && r[high].key>=x.key )   /* high从右到左找小于x.key的记录 */      high--;    if ( low <high ) {r[low]= r[high];  low++;}  /* 找到小于x.key的记录，则进行交换*/    while (low<high && r[low].key<x.key  )   /* low从左到右找大于x.key的记录 */      low++;     if (  low<high  ){ r[high]= r[low]; high--; } /* 找到大于x.key的记录，则交换*/  }  r[low]=x;                     /*将基准记录保存到low=high的位置*/  return low;                     /*返回基准记录的位置*/} /* QKPass */

复制代码

特点：

不稳定排序，但在内部排序中公认效率最好的一种
时间复杂度 O(nlogn) 空间复杂度 O(logn)

五、总结比较

发布于: 2022 年 03 月 23 日阅读数: 63

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

知心宝贝

关注

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

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

评论 (1 条评论)

发布

知心宝贝

冲冲冲

2022 年 03 月 23 日 08:41

 0 回复

没有更多了

创作场景

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

一、前言

学习目标

二、基本概念

1.定义

2.排序方法的稳定性

3.内部和外部排序

三、插入类排序

1.直接插入排序

2.折半插入排序

3.希尔排序

四、交换类排序

1.冒泡排序

2.快速排序

五、总结比较

知心宝贝

评论 (1 条评论)