theme: channing-cyan highlight: vs

携手创作，共同成长！这是我参与「掘金日新计划 · 8 月更文挑战」的第11天，点击查看活动详情 >>

【数据结构】经典八大排序（算法+动图+代码详解）

前言

我们在学习数据结构或者算法的过程中不可避免地需要用到排序，所谓排序就是将记录按照一定的次序排列起来。 而在数据结构中主要介绍了，八种常见排序，本次就让我们一起来学习吧。

提示：以下是本篇文章正文内容，下面讲解可供参考

八大排序算法的实现

1、插入排序（直接插入排序、希尔排序）

核心思想： 将待排序的序列分成有序区和无序区两部分，将无序区中一记录在有序区内排序插入，使得有序区长+1.

（1）直接插入排序：

思想： 先循环找到无序区中待插入的记录，并置于“哨兵位”，然后将有序区中最后一位逐一与其比较，若大则后移让位，若小则不动，直到确定插入位置并插入。

动图演示：

参考代码：

void InsertSort(RcdType &L) {//对顺序表进行直接插入排序 
int i,j;
for (i=1;i<L.length;++i) {
if (L.rcd[i].key>L.rcd[i+1].key) {
//循环找到无序区中待插入的记录L.rcd[i+1]
//将其存放在“哨兵位” 
L.rcd[0] = L.rcd[i+1];
j = i+1;
while (L.rcd[j-1].key>L.rcd[0].key) {
L.rcd[j] = L.rcd[j-1];
j--;
} 
L.rcd[j] = L.rcd[0];//插入 
}
} 
} 

（2）希尔排序：

希尔排序是对直接插入排序的一种改良，但也是一种不稳定的排序算法。 思想： 将待排序序列看成是一个等差数列，按一定的公差从中选出若干个子数列，并对各子数列进行直接插入排序，依次减少公差，重复以上操作，直至公差为1. 动图演示：

参考代码：

一趟希尔排序：

//对顺序表做一次希尔排序，增量为d(可理解为公差） 
void ShellInsert(RcdSqList &L,int d) {
int i,j;
for (i=1;i<L.length-d;++i) {
if (L.rcd[i].key>L.rcd[i+d].key) {
//循环找到无序区中待插入的记录L.rcd[i+d]
//将其存放在“哨兵位” 
L.rcd[0] = L.rcd[i+d];
j = i+d;
while (L.rcd[j-d].key>L.rcd[0].key) {
L.rcd[j] = L.rcd[j-d];
j--;
} 
L.rcd[j] = L.rcd[0];//插入 
}
}  
} 

由此可见，一趟希尔排序的代码和直接插入排序的代码高度相似。其实，直接插入排序可以看成是增量为1的希尔排序。

希尔排序：

void ShellSort(RcdSqList &L,int d[],int t) {
//按照增量序列d[0...t-1]对顺序表L做希尔排序
int k;
for (k=0;k<t;k++) {
ShellInsert(L,d[k]);//一趟增量为d[k]的插入排序 
}
} 

2、选择排序(简单选择排序、堆排序)

思想： 选择排序是指在无序区中选出关键字最小的记录，置于有序区的最后，直到全部记录有序。

（1）简单选择排序：

动图演示：

参考代码：

void select_sort(int a[],int n) {       //传入数组的要排序的元素个
int i,j,min,t;
for(i=0;i<n-1;i++) { 
min=i;      //min:当前最小值下标
for(j=i+1;j<n;j++) {       //扫描余下的部分
if(a[min]>a[j])        //若有其它元素更小，就记录其下标
min=j;
if(min!=i) {       //保若最小值不在排序区首位，就换到首位
t=a[min]; a[min]=a[i]; a[i]=t;
}
}
} 
}

（2）堆排序：

核心思想： 将待排序序列构造成一个大顶堆（或者小顶堆），此时，整个序列的最大值（最小值）就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值（最小值）。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值（次大值）。如此反复执行，便能得到一个有序序列了。

大顶堆进行升序，小顶堆进行降序

动图演示： 堆的筛选： 首先需要明确：堆的筛选操作是针对与只有根节点不符合堆特性的，其子树都符合堆特性。子树的堆长度和堆大小都符合。换句话说就是：该数除了根节点的大小不合适之外，其他全满足堆的要求，所以我们只需要对根节点的大小进行调整即可。再根据优先级，并不需要左右子树都参与调整。

可以说堆的筛选是树演变成堆的最后一步。

3、交换排序（冒泡排序、快速排序）

两两比较（可相邻或否），逆序交换

（1）冒泡排序

思想：相邻两两比较，逆序交换

但是在这里要注意的是需要比较的趟数和次数。 n个记录需要比较n-1趟，就好比两个数只需要比较1一趟；第i趟只需要比较n-i次（每一趟之后的比较次数都会减一） 动图演示： 参考代码：

void bubble_sort(int a[], int n) {       //传入数组的要排序的元素个数
int i, j, t;
for (j=0; j<n-1; j++) {       //n个元素比较n-1轮
for (i= 0; i<n-1-j;i++) {  //比较相邻的两个数
if(a[i]>a[i+1]) {          //若大小顺序不符，就交换
t=a[i];  a[i]=a[i+1]; a[i+1]=t;
}
}
} 
}

（2）快速排序

动图演示：

参考代码：

对记录的顺序表L进行快速排序：

void QuickSort(RcdSqList &L) {//对记录的顺序表L进行快速排序 
QSort(L.rcd,1,L.length);
} 

对记录序列rcd[s...t]进行快速排序：

void QSort (RcdType rcd[],int s,int t) {
//对记录序列rcd[s...t]进行快速排序
int pivotloc ;
if (s<t) {//长度大于一
 pivotloc = Partition(rcd,s,t);
 QSort(rcd,s,pivotloc-1);z
 QSort(rcd,pivotloc+1,t) ;
} 
} 

划分算法：

int Partition (RcdType rcd[],int low,int high) {
//对子序列rcd[low...high]进行一次划分，并返回枢轴应当所处的位置
//使得在枢轴之前的关键字均不大于它的关键字，
//枢轴之后的关键字均不小于它的关键字
rcd[0] = rcd[low];
while (low < high) {
//low和high从待排序序列的两端交替地向中间移动
while (low < high && rcd[high].key >= rcd[0].key) {
--high;
} 
rcd[low] = rcd[high];//将比枢轴关键字小的关键字移到低端 
while (low < high && rcd[low].key <= rcd[0].key) {
++low;
} 
rcd[high] = rcd[low];//将比枢轴关键字大的关键字移到高端 
} 
}

4、归并排序

核心思想： 将待排序序列等比例划分成几个子序列，重复以上步骤，直至子序列长度为1，逐层将各子序列有序合并组成有序序列。

2-路归并：

void Merge(RcdType SR[],RcdType TR[],int i,int m,int n) {
//将相邻的有序区间SR[i..m]和SR[m+1...n]归并为有序的TR[i..n] 
int k,j;
for (j = m+1,k=1;i<=m && j<=n;++k) {
//SR中的记录按关键字从小到大复制到TR中
if (SR[i].key<=SR[j].key) {
//此处注意，若<=改为<,则归并排序不稳定 
TR[k] = SR[i++] ;
} 
else {
TR[k] = SR[j++] ; 
}
}
while (i<=m) {//将剩余的SR[i..m]复制到TR 
TR[k++] = SR[i++];
}
while (j<=n) {//将剩余的SR[j..n]复制到TR
TR[k++] = SR[j++];
}
}

void MSort(RcdType R1[],RcdType R2[],int i,int s,int t) {
//对R1[s..t]进行归并排序，若i%2==1，则排序后的记录存入R2[s...t],
//否则存入R1[s..t]
int m;
if (s == t) {//此时子序列长度为 1 
if (1 == i%2) {
//排序过程是交替使用R1和R2的，而最后要回到R1
//所以才会有这个要求 
R2[s] = R1[s];
}
} 
else {
m = (s+t)/2;//拆分 
MSort(R1,R2,i+1,s,m);
MSort(R1,R2,i+1,m+1,t);
if (1 == i%2) {
Merge(R1,R2,s,m,t);//归并 
}
else {
Merge(R2,R1,s,m,t);
}
}
}

void MergeSort(RcdSqList &L) {
//对顺序表L进行2-路归并排序
RcdType *R;
//申请辅助空间 
R = (RcdType*)malloc((L.lenght+1)*sizeof(RcdType)); 
//对L.rcd[1..L.lenght]归并排序 
MSort(L.rcd,R,0,1,L.lenght); 
free(R); 
} 

//一趟基数排序
void Radixpass(KeysRcdType rcd[],KeysRcdType rcd[],int n,int i,int count[],int pos[],int radix) {
//对数组rcd中记录关键字的第i位计数，计算得到起始位置数组pos[]
 //并按照pos[]数组将rcd中记录复制到数组rcd1中
 int k,j;
 for (k=1;k<=n;k++) {
 count[rcd[k].keys[i]]++;//对各种取值计数 
 } 
 pos[0] = 1;
 for (j=1;j<radix;++j) {
 pos[j] = count[j-1] + pos[j-1];//求起始位置 
 } 
 for (k=1;k<=n;k++) {//收集
 j = rad[k].keys[i]; 
 rcd1[pos[j]++] = rcd[k];//复制记录，对应起始位置+1 
 } 
}