金鞍玉勒寻芳客,未信我庐别有春。这篇文章主要讲述图解数据结构排序全面总结(上)相关的知识,希望能为你提供帮助。
一、前言
学习目标
- 理解排序基本概念以及稳定性,时空复杂度以及适用场景
- 熟练掌握直接插入排序、折半插入排序、冒泡排序这三种常见的排序算法
- 了解希尔排序、快速排序的执行过程以及算法
将一组无序的数据元素调整为有序的数据元素,有序分为从小到大,从大到小两种。
2.排序方法的稳定性
0123456789
54"10"11228107612
解读: 如上个表格这样的一个无序数组,想要将它按照从小到大排序。上图下标2和6对应的数字都是10,排序后假如带引号的" 10" 最后还在不带引号的10前面,那这种排序方法就是稳定的,否则排序方法不稳定。
3.内部和外部排序
- 内部排序: 整个排序过程在内存中
- 外部排序: 排序的数过大,内存和外部存储器之间需要进行多次数据交换
1.直接插入排序
动态演示:
文章图片
算法讲解:
- 上面的动态图可以很好的表达直接插入的过程,只是动态图有点长
- 首先将0作为监视哨,用一个指针从前往后找后面的数字比前面数字小的,找到了放到0
- 指针开始向前移动,如果指向的值比监视哨里的值大,数字向后移
- 如果指向的值比监视哨里的值小,那把监视哨里的值存入这个元素之后
- 后面的排序数字,以此类推
void InsSort(RecordTyper[],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)
文章图片
算法讲解:
- 动态图演示没搞到,只能用上面这张图片了,将就看一下
- 折半插入和二分查找思想差不多,对于一个有序的数组,将一个数字插入之后任然有序
- k代表要插入的值low=1, high=length , mid=(low+high)+1
- mid对应的值如果比k大, high=low-1,否则 low=mid+1
- 当low > high ,low后面就是k插入的位置
void BinSort (RecordTyper[],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;
elselow=mid+1;
for ( j=i-1 ;
j>
= low;
--j )r[j+1]= r[j];
/*记录依次向后移动 */
r[low]=x;
/* 插入记录 */ /*BinSort*/
特点:
- 稳定排序
- 时间复杂度O(n*n), 空间复杂度O(1)
动态演示:
文章图片
算法讲解:
- 对于希尔排序来说取增量 d (d一般为奇数,并且逐次递减)
- 上图第一次排序d等于5,将第一个作为起始点,下标+5取下一个值,一直到最后,将去到的值从小到达排序,然后将第二个作为起始点,3 4 5依次作为起始点排序
- 第二次是d等于3
- 第三次是d等于1
voidShellInsert(RecordType r[], int length,intdelta)
/*对记录数组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)
动态演示:
文章图片
算法讲解:
- 设立两个指针,i,j
- 每一次排序都会把最大的一个数放到后面,依次类推,假设执行2次以后,那么最后2个数就不需要比较了
- 执行n-1次排序,结果完成
voidBubbleSort(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)
动态演示:
文章图片
算法讲解:
- 快速排序讲起来稍微有点复杂,其实就是划分区域
- 建立两个指针low high 分别指向第一个和第二个元素,把第一个元素的值赋给x变量
- high向前移动,假如high指向的值小于x,则high指向的值与x互换
- low向后移动,假如low指向的值大于x,则low指向的值与x互换
- 重复3 4两步,知道high==low,第一次结束
- 将low指向第二个元素,把第二个元素的值赋给x变量
- 重复操作,知道元素有序
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)
排序算法 | 平均时间复杂度 | 空间复杂度 | 稳定性 | 特点 |
直接插入 | O(n*n) | O(1) | 稳定 | 简单、效率一般 |
折半插入 | O(n*n) | O(1) | 稳定 | 一般、效率一般 |
希尔 | O(n*logn) | O(1) | 不稳定 | 使用增量排序后可能和原序列一致,无用功 |
冒泡 | O(n*n) | O(1) | 稳定 | 双指针,比较一次,减少一个需要比较的元素 |
快速 | O(nlogn) | O(logn) | 不稳定 | 较复杂,但高效,进阶的双指针和交换算法 |
推荐阅读
- LNMP平台拆分 #yyds干货盘点#
- LNMP平台搭建与应用 #yyds干货盘点#
- Security安全认证 | Spring Boot如何集成Security实现安全认证
- Centos系统部署nginx1.18.0
- Nginx最常用的七种模块配置 #yyds干货盘点#
- 高频面试java高级进阶之锁?与CAS详解#yyds干货盘点#
- Database Sharding 架构深度解析指南
- Nginx基本概述 #yyds干货盘点#
- MySQL和Redis的数据一致性问题