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

金鞍玉勒寻芳客，未信我庐别有春。这篇文章主要讲述图解数据结构排序全面总结(上)相关的知识，希望能为你提供帮助。
一、前言学习目标

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

二、基本概念 1.定义
将一组无序的数据元素调整为有序的数据元素，有序分为从小到大，从大到小两种。
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)

2.折半插入排序

文章图片

算法讲解：

动态图演示没搞到，只能用上面这张图片了，将就看一下
折半插入和二分查找思想差不多，对于一个有序的数组，将一个数字插入之后任然有序
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)

3.希尔排序
动态演示：

文章图片

算法讲解：

对于希尔排序来说取增量 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)

四、交换类排序 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)

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)

五、总结比较


排序算法	平均时间复杂度	空间复杂度	稳定性	特点
直接插入	O(n*n)	O(1)	稳定	简单、效率一般
折半插入	O(n*n)	O(1)	稳定	一般、效率一般
希尔	O(n*logn)	O(1)	不稳定	使用增量排序后可能和原序列一致，无用功
冒泡	O(n*n)	O(1)	稳定	双指针，比较一次，减少一个需要比较的元素
快速	O(nlogn)	O(logn)	不稳定	较复杂，但高效，进阶的双指针和交换算法