C语言基于顺序表实现的各种排序（笔记2）

2024-07-08 14:00| 来源: 网络整理| 查看: 265

基于顺序表实现的各种排序

之前五一放假之前写过一篇博客（基于c语言实现的顺序表），这篇博客将会在上一篇的基础上继续实现各种排序

当然下面也会简单介绍一下上一篇的主要函数，不看上一篇也能理解这一篇的各种排序

下面附上上一篇的链接https://blog.csdn.net/weixin_45848751/article/details/105855293

基于顺序表实现的各种排序

上一篇的主要函数

数据交换函数

随打乱函数

排序

冒泡排序的优化

选择排序

插入排序

快速排序

全部函数的调用

最后

上一篇的主要函数

这里只用到了顺序表的创建，数据插入和打印顺序表

struct array//顺序表属性结构体，通过顺序表属性访问顺序表 { short* date;//指向顺序表的指针 short length;//顺序表的有效长度 short size;//顺序表得内存大小 }; //创建顺序表 array *creat_array(); //插入数据 //函数里面得参数分别代表，顺序表属性，要插入得数据，要插入的位置， void insert_date(array* temp,short date,short n); //打印顺序表到屏幕 void print_array(array* temp); 数据交换函数

因为排序涉及到了很多次数据交换，所以这里要自定义一个数据交换函数swrp(short *a,short* b)

//交换数据 void swrp(short* a, short *b) { //这里是用位运算交换的数据，也可以定义一个中间变量来进行数据交换 *a = *a^*b; *b = *a^*b; *a = *a^*b; } 随打乱函数

因为要用到多种排序，所以这里自定义了一个随机打乱顺序的函数randValue（array* temp）

void rand_order(array* temp) { short i,j;//需要随机交换的元素下标 i=rand()%temp->length;//随机产生要进行数据交换的元素下标 i=rand()%temp->length;//随机产生要进行数据交换的元素的另一个下标 for(short k=0;ilength;) { if(i!=j)//需要两个下标不是同一个数的时候，才进行交换 { swrp(&temp->date[i],&temp->date[j]); k++; } i=rand()%temp->length;//再次随机产生，需要交换的元素下表 j=rand()%temp->length;//再次随机产生，需要交换的元素下表 } } 排序冒泡排序的优化

冒泡排序是最简单的一种排序，基本思想就是嵌套循环将相邻的两个数据进行比较，一轮内循环之后最大的数沉底，在进行另一轮比较，

可能在第一轮内循环顺序表中的数据就已经是有序的，但是这样剩余的循环还是要进行比较，效率低

下面讨论一种冒泡排序的优化

关于冒泡排序的优化思想就是设置一个 ”监视兵“ ，监视兵的作用就是监视顺序表中的元素是否已经有序，如果有序就不会在进行循环比较

//冒泡排序 void bubble_sort(array* temp) { short flag;//监视兵，‘1’代表顺序表处于无序状态，‘0’代表顺序表处于有序状态 for(short i=0;ilength-1;++i) { flag=0;//开始假设顺序表是有序的 for(short j=i+1;jlength;++j) { if(temp->date[i]>temp->date[j])//满足交换条件 { swrp(&temp->date[i],&temp->date[j]);//交换数据 flag=1;//此时顺序表的状态为无序状态 } } if(flag==0) break; //如果一次内循环之后flag监视兵还是有序状态说明在第i-1元素之后所有的元素都是有序的，而第i个元素前面的数据也是已经排好序的了，所以整个顺序表都是有序的，可以跳出循环了 } }

选择排序

选择排序就是通过一轮循环找出最小的那个数，并且将这个数和还未排好序的元素中的第一个元素进行交换

每一次外循环都会找出一个当前最小值进行交换

选择排序的特点就是交换数据次数少

void select(array* temp) { short min;//min代表的是最小元素的下标 for(short i=0;ilength-1;++i) { //假设最开始的时候下标为i的元素最小 min_=i; for(short j=i+1;temp->length;++i) { if(temp->date[min]>temp->date[j]) min=j; } //内循环结束时，min代表的是此时最小元素的下标 if(i!=min) swrp(&temp->date[i],temp->[min]); } }

插入排序

插入排序，类似于现实生后中打扑克一样，将摸到的下一张扑克牌插入到已经拍好序的扑克中，而具体实现就是将刚摸到的拍先于最大的那个进行比较如果大于最大的，就直接排在最后面，如果小于最大的，就接着向前进行比较，前一个数比它小，后一个数比他大的那个位置，进行插入

也就是说这样的排序方法是从后向前进行依次比较

//插入排序 void insert_sort(array*temp) { short i, j, k; for (i = 1; i < temp->length; ++i)//当i=1的时候就代表，此时手中已经有一张排好序的扑克牌了 { short p = temp->date[i];//定义一个临时变量p来保存要插入的数据 for (j = i-1; j>-1; --j)将i与i前面的数据进行比较 { if (temp->date[j] > temp->date[i])//如果前面的数有比下标为i的元素还大的，就进入if语句 { for (k = j; temp->date[k] > p; --k)//从下标为j的元素开始向后赋值，，也就是数据向后移动，每一个数据移动到他的下一位，为要插入的数据p腾出空间 temp->date[k + 1] = temp->date[k]; temp->date[k+1] = p;//再将p赋值给要插入的位置上 } else break;//为了减少不必要的比较，设置了跳出内循环 } 快速排序

快速排序的效率很高，远远高于前三种排序方法，基本思想就是设置基准值，在基准值的左边都是小于基准值的，基准值的右面都是大于基准值的，

运用递归函数进行分治，分成一个又一个的局部数组，在进行排序

while循环上面的那一段注释是我自己的理解，可以参考，但是本人语言组织能力实在太差，能看懂就看，看不懂就直接研究代码

//快速排序//传递参数分别代表顺序标属性，（局部）顺序表最左边的下标，（局部）顺序表最右边的下标 void quick_sort(array* temp,short left,short right) { if (left >= right)//如果分成的局部顺序表中就只剩下一个元素了，就返回 return; else { short i = left; short j = right; short key = temp->date[left];//假设下表为left的元素就是基准值 //这个while循环的作用就是让i左边的数都小于基准值，i右面的数都大于基准值， // //最后跳出循环的条件是i==j，这个循环判断的条件就说明了，这个循环结束之后应该将 // //整个数组都遍历了一遍，也就是说，这个数组“关于基准值有序”，， // // //也可以理解为这个循环的作用就是将假设的基准值放在它自己应该在的位置上面 // //因为刚开始令基准值等于temp->data[0]说明这次排序是根据第一个值来排序的，但是这个基准值刚开始并不在它自己应该在的位置上面，所以这个循环就是将那个基准值放在它自己应该在的位置上，而在将基准值放在它自己应该在的位置上的过程中，还伴随着另一件事的发生，就是基准值在寻找他自己的位置的时候，它会先将自己赋值给哨兵，也就是站出来看这个数组，以一个局外人的身份来寻找自己的位置，这个过程中，它会从两边找不满足条件的数据，从最右面开始找到第一个比自己还要小的数就将这个数放在自己现在所在的位置，从最左边开始找到第一个比自己大的数据放到上一步在右面找到的那个比自己还要小得那个位置上面，然后再将它自己放在刚才找到的那个从左边找到的第一个大于自己的位置上，这样就完成了第一次交换，如果此时i=key)//从右面找到小于基准值的数， j--; temp->date[i] = temp->date[j];//将右面这个小于基准值的数移动到左边i得位置上 while (i < j&&temp->date[i] date[j] = temp->date[i];将左边这个大于基准值的数移动到右面j的位置上 temp->date[i] = key; } quick_sort(temp, left, i-1);//左面 quick_sort(temp, i + 1, right);//右面 } } 全部函数的调用

下面的程序是将顺序表的创建插入以及顺序表的各种排序函数都

#include #include #include #define SIZE 5 #define Array_Size 10 //顺序表的增删查改 struct array { short* date; short length; short size_array; }; //创 array* creat_array() { array* temp; temp = (array*)malloc(sizeof(array)); if (temp == NULL) { printf("申请内存失败！！！\n"); exit(0); } temp->date = (short*)malloc(sizeof(short)*Array_Size); temp->length = 0; temp->size_array = Array_Size; return temp; } //增 void insert(array* temp, short data, short n)//属性，数据，位置 { if (ntemp->length + 1)//插入位置不合法 { printf("插入位置不合法！！！\n"); return; } else//插入位置合法 { if (temp->length > 0)//判断是否是第一次插入 { if (temp->length >= temp->size_array) { temp->date = (short*)realloc(temp->date, sizeof(short)*(SIZE + temp->size_array)); temp->size_array += SIZE; } for (short i = temp->length; i >= n; --i)//注意这里i的含义，，，i是下标还是位置//i在这里代表的是位置，所以i=temp->length就是比下表多一，，//而要将一个数据插入到第n个位置上去，，就是将下标为n-1的数据也要向后赋值 temp->date[i] = temp->date[i - 1]; temp->date[n - 1] = data; temp->length++; } else { temp->length++; temp->date[0] = data; } } } //显 void print_array(array*temp) { if (temp == NULL) { printf("顺序表已经被销毁！！！\n"); return; } if (temp->date != NULL) { printf("此时顺序表里面的数据为："); for (short i = 0; i < temp->length; ++i) { printf("%d ", temp->date[i]); } printf("\n\n"); } } //快速排序 void quick_sort(array* temp,short left,short right) { if (left >= right) return; else { short i = left; short j = right; short key = temp->date[left]; while (i < j) //这个while循环的作用就是让i左边的数都小于基准值，i右面的数都大于基准值， //最后跳出循环的条件是i==j，这个循环判断的条件就说明了，这个循环结束之后应该将 //整个数组都遍历了一遍，也就是说，这个数组“关于基准值有序”，， //也可以理解为这个循环的作用就是将假设的基准值放在它自己应该在的位置上面 //因为刚开始令基准值等于temp->data[0]说明这次排序是根据第一个值来排序的，但是这个基准值刚开始并不在它自己应该在的位置上面，所以这个循环就是将那个基准值放在它自己应该在的位置上，而在将基准值放在它自己应该在的位置上的过程中，还伴随着另一件事的发生，就是基准值在寻找他自己的位置的时候，它会先将自己赋值给哨兵，也就是站出来看这个数组，以一个局外人的身份来寻找自己的位置，这个过程中，它会从两边找不满足条件的数据，从最右面开始找到第一个比自己还要小的数就将这个数放在自己现在所在的位置，从最左边开始找到第一个比自己大的数据放到上一步在右面找到的那个比自己还要小得那个位置上面，然后再将它自己放在刚才找到的那个从左边找到的第一个大于自己的位置上，这样就完成了第一次交换，如果此时i=key)//右面 j--; temp->date[i] = temp->date[j]; while (i < j&&temp->date[i] date[j] = temp->date[i]; temp->date[i] = key; } quick_sort(temp, left, i-1); quick_sort(temp, i + 1, right); } } //插入排序 void insert_sort(array*temp) { short i, j, k; for (i = 1; i < temp->length; ++i) { short p = temp->date[i]; for (j = i-1; j>-1; --j) { if (temp->date[j] > temp->date[i]) { for (k = j; temp->date[k] > p; --k) temp->date[k + 1] = temp->date[k]; temp->date[k+1] = p; } } } printf("插入排序："); } //随机打乱 void rand_order(array*temp) { short i = rand() % temp->length; short j = rand() % temp->length; for (short k= 0; k < 10;) { if (i != j) { temp->date[i] = temp->date[i] ^ temp->date[j]; temp->date[j] = temp->date[i] ^ temp->date[j]; temp->date[i] = temp->date[i] ^ temp->date[j]; ++k; } i = rand() % temp->length; j = rand() % temp->length; } printf("随机打乱顺序之后，"); } //交换数据 void swrp(short* a, short *b) { *a = *a^*b; *b = *a^*b; *a = *a^*b; } //冒泡排序 void bubble_sort(array*temp) { for (short i = 0; i < temp->length; ++i) { for (short j = i + 1; j < temp->length; ++j) { if (temp->date[j] < temp->date[i]) swrp(&temp->date[i], &temp->date[j]); } } printf("冒泡排序："); } //选择排序 void select_sort(array*temp) { short min,num; for (short i = 0; i < temp->length-1; ++i) { min = i; for (short j = i; j < temp->length; ++j) { if (temp->date[j] < temp->date[min]) { min = j; } } if (i!=min) swrp(&temp->date[i], &temp->date[min]); } printf("选择排序："); } int main() { array* Array_move; srand((unsigned)time(NULL)); Array_move=creat_array(); insert(Array_move, 0, 1); for (short i = 1; ilength-1); print_array(Array_move); rand_order(Array_move); print_array(Array_move); insert_sort(Array_move); print_array(Array_move); free(Array_move->date); free(Array_move); Array_move = NULL; system("pause"); return 0; }

实现效果就像这样

最后

五一小长假之后，我们就要进行c语言结课考试了，陌生人，能祝我考个好成绩吗？

希望我们一起进步，

天天学习，天天成长。

加油！！！

【本文地址】

公司简介

联系我们

C语言 基于顺序表实现的各种排序（笔记2）

C语言基于顺序表实现的各种排序（笔记2）