这遍文章主要介绍一些常见的排序算法，排序在我们开发中用到的几率可能不多，但是还是有必要知道的。
排序的分类
内排序:是在排序整个过程中,待排序的所有记录全部被放置在内存中;
外排序:由于排序的记录个数太多,不能同时放置在内存,整个排序过程需要在内外存 之间多次交换数据才能进行
下面的排序算法都是内排序。
在介绍排序算法时，先写一些排序会用到的基本函数和结构体
主要是交换和打印。
#define MAXSIZE 100
typedef struct {
//用于存储要排序的数组，r[0]用作哨兵或临时变量
int r[MAXSIZE+1];
//用于记录顺序表的长度
int length;
}Sqlist;
//2、排序常用交换函数实现
void swap(Sqlist *L,int i,int j){
int temp = L->r[i];
L->r[i] = L->r[j];
L->r[j] = temp;
}
//3、打印数组
void print(Sqlist L){
int i;
for (i = 1; i<L.length; i++) {
printf("%3d",L.r[i]);
}
printf("%3d",L.r[i]);
printf("\n");
}
首先介绍最常用的，冒泡排序算法，两两比较相邻的记录的关键字,如果 反序则交换,直到没有反序的记录为止
冒泡排序
下面的冒泡排序是我们随手就能写出来的，通过r[i]与r[j]的比较，进行交换，这样的实现效率是比较低的
//4、冒泡排序
void BubbleSort_1(Sqlist *L){
int i,j;
for(i = 1;i<L->length;i++){
for(j = i+1;j<=L->length;j++){
if(L->r[i]>L->r[j])
swap(L, i, j);
}
}
}
下面的的算法也属于冒泡，从尾部找最小的，每一次都从最后一个找最小的值，不断交换和比较。
//5、冒泡排序-对顺序表L作冒泡排序（正宗冒泡排序算法）
void BubbleSort_2(Sqlist *L){
int i,j;
for(i = 1;i<L->length;i++){
for(j = L->length-1;j>=1;j--){
//若前者大于后者，交换
if(L->r[j]>L->r[j+1])
swap(L,j,j+1);
}
}
}
下面是对冒泡进行了一些优化，主要思想就是利用一个值来判断一个范围内是否有序，有序就不再比较，直接跳过。
//6、冒泡排序-对顺序表L冒泡排序进行优化
void BubbleSort_3(Sqlist *L){
int i,j;
//flag标记
int flag = TRUE;
//i从[1,L->length) 遍历;
//如果flag为False退出循环. 表示已经出现过一次j从L->Length-1 到 i的过程,都没有交换的状态;
for (i = 1; i<L->length && flag; i++) {
//flag每次初始化为false
flag = FALSE;
for (j = L->length-1; j>=i; j--) {
if(L->r[j]>L->r[j+1]){
//交换值
swap(L, j, j+1);
//如果有任何数据的交换动作,则将flag改为true;
flag = TRUE;
}
}
}
}
选择排序
选择排序的思想就是设定一个最小值，找出是否还有比这个值还小的，有的话进行交换，最后判断最小值的下标是否和之前的一样，不一样则替换。
//7、选择排序--对顺序表L进行简单选择排序
void SelectSort(Sqlist *L){
int i,j,min;
for(i = 1;i<L->length;i++){
//将当前下标假设为最小值的下标
min = i;
//循环比较i之后的所有数据
for(j = i+1;j<=L->length;j++){
//如果有小于当前最小值的关键字,将此关键字的下标赋值给min
if(L->r[min]>L->r[j]){
min = j;
}
}
//如果min不等于i,说明找到了最小值,则交换2个位置下的关键字
if(i!=min)
swap(L,i,min);
}
}
直接插入排序
直接插入排序算法的核心思想就是将较小的数一个一个往后前移动，直到找到了不比它小的前一个位置进行赋值。其中利用了哨兵存储较小的一个值。
//8、直接插入排序算法--对顺序表L进行直接插入排序
void InsertSort(Sqlist *L){
int i,j;
//L->r[0] 哨兵 可以把temp改为L->r[0]
int temp=0;
//假设排序的序列集是{0,5,4,3,6,2};
//i从2开始的意思是我们假设5已经放好了. 后面的牌(4,3,6,2)是插入到它的左侧或者右侧
for (i = 2; i<L->length; i++) {
//需要将L->r[i]插入有序子表
if(L->r[i]<L->r[i-1]){
//设置哨兵
temp = L->r[i];
for(j = i-1;L->r[j]>temp;j--)
L->r[j+1] = L->r[j];
L->r[j+1] = temp;
}
}
}
希尔排序
希尔排序思想: 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排 序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰被分成 一组，算法便终止.
15898767780450.png
15898767853655.png
看上图，其实就是将整个序列分隔成几块，然后每块对应位置进行比较和交换。组成一个基本有序的序列，最后对序列进行直接插入，组成一个有序的序列
//9、希尔排序
void shellSort(Sqlist *L){
int i,j;
int increment = L->length;
//0,9,1,5,8,3,7,4,6,2
//① 当increment 为1时,表示希尔排序结束
do{
//增量序列
increment = increment/3+1;
//i的待插入序列数据[increment+1,length]
for(i = increment+1;i<=L->length;i++){
//如果r[i] 小于它的序列组元素则进行插入排序,例如3和9. 3比9小,所以需要将3与9的位置交换
if(L->r[i]<L->r[i-increment]){
//将需要插入的L->r[i]暂时存储在L->r[0].和插入排序的temp 是一个概念;
L->r[0] = L->r[i];
for(j = i-increment;j>0 && L->r[0]<L->r[j];j-=increment){
L->r[j+increment] = L->r[j];
}
//将L->r[0]插入到L->r[j+increment]的位置上;
L->r[j+increment] = L->r[0];
}
}
}while(increment>1);
}
堆排序
堆是具有下面性质的完全二叉树: 每个结点的值都大于或等于其左右孩子结点的值, 称为大顶堆;如图1; 或者每个结点的值都小于等于其左右孩子的结点的值,称为小顶堆, 如图2.
15898769698704.png
其中每个节点i的下标与其对应的子节点的下标为2i或2i+1。
堆排序(Heap Sort) 就是利用堆(假设我们选择大顶堆)进行排序的算法.它的基本思 想:
①将待排序的序列构成一个大顶堆,此时,整个序列的最大值就堆顶的根结点,将 它移走(其实就是将其与堆数组的末尾元素交换, 此时末尾元素就是最大值);
②然后将剩余的n-1个序列重新构成一个队,这样就会得到n个元素的次大值, 如此重复执行,就能得到一个有序序列了
从完全二叉树的性质来看，前半部分的节点都拥有子节点，因此可以先对前半部分的节点进行交换，最中间部分开始，找到最大的子节点作为父节点，逐步比较和替换。然后从序列第一个元素开始，与后面的元素比较和交换，再从新进行堆排序。
代码：
堆排序的实现分两个函数，第一个函数主要是实现父节点和子节点的比较和交换，第二个函数主要实现完整的堆排序。
//大顶堆调整函数;
/*
条件: 在L.r[s...m] 记录中除了下标s对应的关键字L.r[s]不符合大顶堆定义,其他均满足;
结果: 调整L.r[s]的关键字,使得L->r[s...m]这个范围内符合大顶堆定义.
*/
void HeapAdjust(Sqlist *L,int s,int m){
int temp,i;
//将L->r[s]存储到temp,方便后面交换
temp = L->r[s];
//j 为什么从2*s 开始进行循环,以及它的递增条件为什么是j*2
//因为这是颗完全二叉树,而s也是非叶子根结点. 所以它的左孩子一定是2*s,而右孩子则是2s+1;(二叉树性质5)
for(i = 2*s;i<=m;i*=2){
//判断j是否是最后一个结点, 并且找到左右孩子中最大的结点;
//如果左孩子小于右孩子,那么j++; 否则不自增1. 因为它本身就比右孩子大;
if(i<m && L->r[i]<L->r[i+1])
++i;
//比较当前的temp 是不是比较左右孩子大; 如果大则表示我们已经构建成大顶堆了;
if(temp>=L->r[i])
break;
//将L->[j] 的值赋值给非叶子根结点
L->r[s] = L->r[i];
//将s指向j; 因为此时L.r[4] = 60, L.r[8]=60. 那我们需要记录这8的索引信息.等退出循环时,能够把temp值30 覆盖到L.r[8] = 30. 这样才实现了30与60的交换;
s=i;
}
//将L->r[s] = temp. 其实就是把L.r[8] = L.r[4] 进行交换;
L->r[s] = temp;
}
void HeapSort(Sqlist *L){
int i;
//1.将现在待排序的序列构建成一个大顶堆;
//将L构建成一个大顶堆;
//i为什么是从length/2.因为在对大顶堆的调整其实是对非叶子的根结点调整.
for (i = L->length/2; i>0; i--) {
HeapAdjust(L, i, L->length);
}
//逐步将每个最大的值根结点与末尾元素进行交换,并且再调整成大顶堆
for(i = L->length;i>1;i--){
//将堆顶记录与当前未经排序子序列的最后一个记录进行交换;
swap(L, 1, i);
//将L->r[1...i-1]重新调整成大顶堆;
HeapAdjust(L, 1, i-1);
}
}
main函数和输出结果
#define N 9
int main(int argc, const char * argv[]) {
// insert code here...
printf("排序算法!");
int i;
int d[N] = {9,1,5,8,3,7,4,6,2};
Sqlist l0,l1,l2,l3,l4,l5,l6,l7,l8,l9,l10;
for (i = 0; i<N; i++) {
l0.r[i+1] = d[i];
}
l0.length = N;
l1=l2=l3=l4=l5=l6=l7=l8=l9=l10 = l0;
printf("排序前:\n");
print(l0);
printf("\n");
//1.初级冒泡排序
printf("初级冒泡排序:\n");
BubbleSort_1(&l0);
print(l0);
printf("\n");
//2.冒泡排序
printf("冒泡排序:\n");
BubbleSort_2(&l1);
print(l1);
printf("\n");
//3.冒泡排序优化
printf("冒泡排序(优化):\n");
BubbleSort_3(&l2);
print(l2);
printf("\n");
//4.选择排序
printf("选择排序:\n");
SelectSort(&l3);
print(l3);
printf("\n");
//5.直接插入排序
printf("直接插入排序:\n");
InsertSort(&l4);
print(l4);
printf("\n");
//6.希尔排序
printf("希尔排序:\n");
shellSort(&l5);
print(l5);
printf("\n");
//7.堆排序
//注意:执行对排序时更换一下数据源. 这里我为什么要这组数据,原因是为了与下标个位数字讲解时进行区分;因为在这个算法讲解过程,出现了很多下标的相关计算.
/* int d[N]={50,10,90,30,70,40,80,60,20}; */
printf("堆排序:\n");
HeapSort(&l6);
print(l6);
printf("\n");
return 0;
}
输出结果
排序算法!排序前:
排序前:
9 1 5 8 3 7 4 6 2
初级冒泡排序:
1 2 3 4 5 6 7 8 9
冒泡排序:
1 2 3 4 5 6 7 8 9
冒泡排序(优化):
1 2 3 4 5 6 7 8 9
选择排序:
1 2 3 4 5 6 7 8 9
直接插入排序:
1 3 4 5 6 7 8 9 2
希尔排序:
1 2 3 4 5 6 7 8 9
堆排序:
1 2 3 4 5 6 7 8 9
Program ended with exit code: 0
网友评论