石佛营网站建设,wordpress 取消侧边栏,个人或主题网站建设实验报告,做外贸进国外网站相关代码gitee自取#xff1a;
C语言学习日记: 加油努力 (gitee.com)
接上期#xff1a;
【数据结构初阶】八、非线性表里的二叉树#xff08;二叉树的实现 -- C语言链式结构#xff09;-CSDN博客 排序 排序的概念 所谓排序#xff0c;就是使一串记录#xff0c;按照…
相关代码gitee自取
C语言学习日记: 加油努力 (gitee.com) 接上期
【数据结构初阶】八、非线性表里的二叉树二叉树的实现 -- C语言链式结构-CSDN博客 排序 排序的概念 所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减排列起来的操作 稳定性 假定在待排序的记录序列中存在多个具有相同关键字的记录 若经过排序这些记录的相对次序保持不变 即在原序列中 r [ i ] r [ j ] , 且 r [ i ] 在 r [ j ] 之前 而在排序后的序列中r [ i ] 仍在 r [ j ] 之前 则称这种排序算法是稳定的否则称为不稳定的 内部排序 数据元素全部放在内存中的排序 外部排序 数据元素太多不能同时放在内存中 根据排序过程的要求不能在内外存之间移动数据的排序 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 常见排序算法的实现 详细解释在图片的注释中代码分文件放下一标题处 一、插入排序 插入排序 -- 直接插入排序 直接插入排序是一种简单的插入排序法 该算法基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中 直到所有的记录插入完为止得到一个新的有序序列想象我们玩扑克牌时给扑克牌大小排序就用了插入排序的思想 实现思路 当插入第 i(i1) 个元素时前面的 array[0]array[1]…array[i-1] 已经排好序 此时用 array[i] 的排序码与 array[i-1]array[i-2]… 的排序码顺序进行比较找到插入位置后就将 array[i] 插入原来位置上的元素顺序后移覆盖 直接插入排序的特性总结 元素越接近有序直接插入排序算法的时间效率越高 -- 最高可达O(N) 该算法时间复杂度O(N^2) -- 最坏的情况下(逆序) 该算法空间复杂度O(1) 该算法稳定性稳定 --------------------------------------------------------------------------------------------- InsertSort函数 -- 直接插入排序实现函数 使用for循环进行循环插入排序 再设置 “前元素” 和 “后元素” for循环中 使用while循环为“后元素”寻找合适位置找到后再将 “后元素” 插入 之后再次进行for循环让下个“后元素”插入合适位置 图示 该函数执行逻辑图 对应函数测试 --------------------------------------------------------------------------------------------- 插入排序 -- 希尔排序缩小增量排序 希尔排序又称缩小增量法。 该算法基本思想 先选定一个整数gap值把待排序文件中所有记录分成gap个组 所有距离为gap的记录分在同一组内并对每一组内的记录进行直接插入排序 然后换个整数gap值再取gap组重复上述分组和排序的工作 当 gap1 时所有记录在同一组内时已经排好序了 希尔排序的特性总结 希尔排序是对直接插入排序的优化 当 gap1 时都是在进行预排序目的是让数组更接近于有序当 gap1 时数组已经接近有序的了这样再进行直接插入排序就会很快 这样整体而言可以达到优化的效果 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算 因此在一些书中给出的希尔排序的时间复杂度也不固定该函数大概的时间复杂度为O(N^1.3) 该算法稳定性不稳定 --------------------------------------------------------------------------------------------- ShellSort函数 -- 希尔排序实现函数 核心实现操作还是直接插入排序 但是在对所有值进行直接插入排序前先进行多次预排序操作 预排序也是用直接插入排序完成让数组达到尽量有序的状态 定义gap值变量使用while循环控制多次预排序 当gap1时就相当于直接插入排序 while循环中内嵌for循环完成“当前gap组”的预排序 再内嵌for循环完成“当前gap组”其中一组的预排序 通过直接插入排序的方式实现 最后再内嵌while循环配合完成直接插入排序 图示 该函数执行逻辑图 对应函数测试 二、选择排序 基本思想 每一趟排序从待排序的数组元素中分别选择出最小和最大的一个元素再分别存放在数组的起始位置和尾部位置直到全部待排序的数组元素排序完成 选择排序 -- 直接选择排序 该算法基本思想 在元素集合 array[i] -- array[n-1] 中选择获取当前最小值元素和当前最大值元素将当前最小值元素交换后放到当前数组的起始位置将当前最大值元素交换后放到当前数组的尾部位置 在剩余的 array[i1] -- array[n-2] 集合中重复上述操作直到集合剩余1个元素 直接选择排序的特性总结 直接选择排序比较好理解但是效率不高实际很少使用 该算法时间复杂度O(N^2) 该算法空间复杂度O(1) 该算法稳定性不稳定 --------------------------------------------------------------------------------------------- SelectSort函数 -- 直接选择排序实现函数 定义 数组开始(初始)位置下标begin 和 数组尾部(结束)位置下标end 变量 使用while循环控制多趟直接选择排序 在while循环中完成一趟直接选择排序定义 存放当前最小值下标mini 和 存放当前最大值下标maxi 变量内嵌for循环遍历一次当前数组找到当前最大值和当前最小值 while循环中for循环外 将找到的当前数组最小值放入数组起始左边位置当前数组最大值放入数组尾部右边位置,完成两值的排序后调整 begin 和 end 变量缩小数组范围准备下趟直接选择排序 图示 该函数执行逻辑图 对应函数测试 --------------------------------------------------------------------------------------------- 选择排序 -- 堆排序 堆是一种完全二叉树 可以使用堆中的向下调整操作对普通数组进行排序升序或降序 堆排序往期博客中已有详细描述 【数据结构初阶】七、非线性表里的二叉树堆的实现 -- C语言顺序结构-CSDN博客 包含堆排序的 实现函数、图示、对应函数执行逻辑图、函数测试、原代码 三、交换排序 基本思想 所谓交换就是根据序列中两个记录键值的比较结果来交换这两个记录在序列中的位置 交换排序的特点 将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动 交换排序 -- 冒泡排序 该算法基本思想 数组中的元素1和元素2进行比较如果元素1大于元素2则交换两者位置 再比较此时的元素2和元素3如果元素2大于元素3则交换两者位置 再比较此时的元素3和元素4…… 一趟冒泡排序完成后就能完成当前数组中最大值的排序排在尾部再进行下一趟冒泡排序前要缩小数组排序范围排除已经排序好的最大值 这样多趟冒泡排序完成后就能完成数组的排序 冒泡排序的特性总结 冒泡排序是一种非常容易理解的排序 该算法时间复杂度O(N^2) 该算法空间复杂度O(1) 该算法稳定性稳定 --------------------------------------------------------------------------------------------- BubbleSort函数 -- 冒泡排序实现函数 定义嵌套for循环完成冒泡排序外层for循环控制当前数组范围数组范围慢慢减小减到变成1时排序完成至少有两个数才能比较 内层for循环循环一趟完成当前数组范围内的最值的排序 在当前冒泡排序过程中设置一个变量exchange记录当前一趟冒泡排序过程中是否有发生元素的交换 一趟冒泡排序后如果没有任何元素发生交换 说明目前已经排好序了那就直接终止之后的冒泡排序 图示 该函数执行逻辑图 对应函数测试 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 对应代码 Sort.h -- 排序头文件 #pragma once//包含之后所需头文件
#include stdio.h//打印数组函数
void PrintArray(int* a, int n);//直接插入排序函数
//第一个参数接收要排序的数组首元素地址a
//第二个参数接收该数组的长度n
void InsertSort(int* a, int n);//希尔排序函数
//第一个参数接收要排序的数组首元素地址a
//第二个参数接收该数组的长度n
void ShellSort(int* a, int n);
//1、预排序分组排间隔为gap(间距间隔)分为一组
// 预排序意义
// 让大的数更快的到数组后面小的数更快的到数组前面
// gap值越大“跳”得越快但是越不接近有序
// gap值越小“跳”得越慢但是越接近有序
// 当gap1时就相当于直接插入排序
//2、直接插入排序//冒泡排序函数
//第一个参数接收要排序的数组首元素地址a
//第二个参数接收该数组的长度n
void BubbleSort(int* a, int n); //直接选择排序函数
//第一个参数接收要排序的数组首元素地址a
//第二个参数接收该数组的长度n
void SelectSort(int* a, int n);--------------------------------------------------------------------------------------------- Sort.c -- 排序函数实现文件 #define _CRT_SECURE_NO_WARNINGS 1//包含排序头文件
#include Sort.h//打印数组函数
void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf();
}//直接插入排序函数升序
//第一个参数接收要排序的数组首元素地址a
//第二个参数接收该数组的长度n
void InsertSort(int* a, int n)
{//使用for循环进行循环插入排序/*要取“前后元素”“后元素”要依次和“前面所有元素”进行比较直到“后元素”找到合适位置并插入而“后元素”下标最大为[n-1]所以“前元素”下标最大为[n-2]*/for (int i 0; i n - 1; i)//循环到 i n-2 -- “前元素”下标最大为[n-2]{//遍历下标的起始位置从 0 开始到 n-2 结束int end i; //“前元素”//保存end下标元素的后一个元素int tmp a[end 1]; //“后元素”//使用while循环为“后元素”寻找合适位置//“后元素”循环和其前面所有元素进行比较直到找到合适位置while (end 0)//“前面所有元素”下标 0 时就还有 “前元素”//那“后元素”就需要继续进行比较{if (tmp a[end])//“后元素” 小于 “前元素”{//那就将“前元素(较大)”往后插入覆盖:a[end 1] a[end];//a[end 1]被覆盖的元素还保留在tmp中//所以不用担心覆盖后找不到“后元素”}else//后元素 大于等于 前元素{//说明“后元素”的“前面较大元素”都已经往后覆盖完成了//找到了后元素的恰当位置//break退出循环将“后元素”tmp插入该位置break;}end--;//当前end--下次循环判断“前前元素”需不需要再往前覆盖//end减到-1退出while循环的话说明“后元素”是数组中最小的元素//导致其前面所有元素都需要往后覆盖挪出位置}//注意合适的位置是[end 1]//因为后元素 大于等于 前元素的话//那“后元素”就理应排在“前元素”后面即[end 1]a[end 1] tmp;//如果是end减到-1退出的while循环//那[end 1]就等于0即数组首元素位置//让“后元素”排在数组首元素位置}
}
//时间复杂度
//O(N^2) -- 逆序最坏情况
//O(N) -- 顺序有序
//冒泡排序和插入排序论时间复杂度它们是同一档次
//但在细节上如局部有序插入排序会更优//希尔排序函数
//第一个参数接收要排序的数组首元素地址a
//第二个参数接收该数组的长度n·
void ShellSort(int* a, int n)
{//定义分组间隔和分组个数int gap n;//只要当前预排序gap值还没到1//while循环就继续循环进行预排序while (gap 1){//变化gap值进行多次预排序//让数组越来越接近有序gap gap / 2;//当 gap 1 时就是预排序//当 gap 1 时就是插入排序//这个for循环控制 “当前gap组” 的排序//一组“gap分”组排完再排另一组gap分组for (int j 0; j gap; j)/** 假设gap取3* 就在数组中以3(gap)为间隔取数为一组gap分组* 总共取3(gap)组*/{//这个for循环控制gap组中其中一组的排序for (int i 0; i n - gap; i gap)/** 循环条件n - gap *控制“前元素end”范围保证“后元素tmp”通过end取值时不出界* 迭代条件i gap*i每次迭代时就gap实现以gap为间隔取数为一组gap分组*/{//保存当前分组的“前元素”记录int end i;//保存当前分组的“后元素”记录int tmp a[end gap];//使用while循环为“后元素”寻找合适位置://(“后元素”循环和其前面所有元素进行比较直到找到合适位置)//(和直接插入类似只是值与值间隔不同)while (end 0)//“前面所有元素”下标 0 时就还有 “前元素”//那“后元素”就需要继续进行比较{if (tmp a[end])//“后元素” 小于 “前元素”{//(gap分组中)//那就将“前元素(较大)”往后插入覆盖:a[end gap] a[end];//a[end gap]被覆盖的元素还保留在tmp中//所以不用担心覆盖后找不到“后元素”end - gap;//(gap分组中)//当前end-gap下次循环判断“前前元素”需不需要再往前覆盖//end减到0时退出while循环的话说明“后元素”是数组中最小的元素//导致其前面所有元素都需要往后覆盖挪出位置}else//后元素 大于等于 前元素{//说明“后元素”的“前面较大元素”都已经往后覆盖完成了//找到了后元素的恰当位置//break退出循环将“后元素”tmp插入该位置break;}}//注意合适的位置是[end gap]//因为后元素 大于等于 前元素的话//那“后元素”就理应排在“前元素”后面即[end gap]a[end gap] tmp;//如果是 end减到0 退出的while循环//那[end gap]就找到当前gap组首元素位置//让“后元素”排在当前gap组首元素位置}}}
}//两值交换函数
void Swap(int* x, int* y)
{//创建中间值进行值的交换int tmp *x;*x *y;*y tmp;
}//冒泡排序函数
//第一个参数接收要排序的数组首元素地址a
//第二个参数接收该数组的长度n
void BubbleSort(int* a, int n)
{/** 定义嵌套for循环完成冒泡排序* 内层for循环一趟完成当前数组范围内的最值的排序* 外层for循环则控制当前数组范围* 数组范围慢慢减小减到变成1时排序完成* 至少有两个数才能比较*///这个for循环控制内嵌for循环的数组范围for (int j 0; j n; j){int exchange 0; //如果没发生交换该变量就为0//内嵌for循环进行循环比较交换for (int i 1; i n-j; i)/**n-j 通过判断条件控制数组范围*因为一趟下来就完成一个当前最值的排序*下次再排序的数组范围就要排除这个已经排好序的最值*通过外部for循环的j来控制数组范围*/{if (a[i - 1] a[i])//如果“前元素” 大于 “当前元素”// i 从1开始{//进行交换Swap(a[i - 1], a[i]);exchange 1;//如果发生了变化该变量就为1}}/** 内嵌for循环整个执行完就是一趟* 当遇到最大值后因为最大所以会一直被交换* 直到被交换至数组尾部* 这就完成了当前数组最大值的排序*/if (exchange 0)//一趟冒泡排序后如果没有发生交换{//说明目前已经排好序了//就没必要再进行之后的冒泡排序了break;} }
}//直接选择排序函数
//第一个参数接收要排序的数组首元素地址a
//第二个参数接收该数组的长度n
void SelectSort(int* a, int n)
{/** 思路* 排序一趟选出当前最小值下标和当前最大值下标,* 通过对应下标将最小值放“左边”最大值放“右边”*///数组开始位置下标 -- 0int begin 0;//数组尾部结束位置下标 -- n-1int end n - 1;//使用while循环控制多趟直接选择排序while (begin end)/** 只要 begin 还小于 end左右下标就还没重合* begin 和 end 之间就还有元素要被排序*/{//对当前数组范围进行一趟直接选择排序//存放当前最小值下标int mini begin; //默认为下标0//存放当前最大值下标int maxi begin; //默认为下标0//使用for循环遍历一次当前数组//找到当前最大值和当前最小值for (int i begin1; i end; i)/** mini 和 maxi 默认下标都是0* 所以循环时下标从[begin1]开始等于[n-1]结束*/{//选出当前最大值下标if (a[i] a[maxi])//如果“i下标元素”大于“maxi下标元素”{//将较大值下标i赋给maxi下标maxi i;}//选出当前最小值下标if (a[i] a[mini])//如果“i下标元素”小于“mini下标元素”{//将较小值下标i赋给mini下标mini i;}} //(for循环中)//将找到的当前数组最小值放入数组起始左边位置Swap(a[begin], a[mini]);/** 注如果begin下标元素为最大值* 那么maxi下标也会指向该元素即begin maxi* 当begin元素和mini交换后只是值交换* begin 和 maxi下标还是重叠在原位置指向交换后的mini元素* 此时如果再执行 Swap(a[end], a[maxi]);* 就反而会将最小值移到数组尾部去* 所以要调整 beginmaxi 重叠的情况*/if (maxi begin)//排除maxi和begin下标重叠的情况{//maxibegin等于当前最大值下标上面交换后//当前最大值就在mini下标处//那就把maxi最大值下标指向mini下标处即可maxi mini;}//将找到的当前数组最大值放入数组尾部右边位置Swap(a[end], a[maxi]);/** 执行到这就选出了两个最值并放到了合适位置一趟直接选择排序* 调整 begin 和 end 下标调整数组范围数组范围往中间缩小* 再开始新一趟直接选择排序*/begin;--end;} //(while循环中)
}
//时间复杂度O(N^2) --------------------------------------------------------------------------------------------- Test.c -- 排序测试文件 #define _CRT_SECURE_NO_WARNINGS 1//包含排序头文件
#include Sort.h//插入排序测试
void ISTest()
{//创建要进行插入排序的数组int a[] { 3,4,2,1,5 };//调用插入排序函数进行排序InsertSort(a, 5);//循环打印排序后的数组printf(使用直接插入排序后的数组: );for (int i 0; i 5; i){printf(%d , a[i]);}
}//希尔排序测试
void SSTest()
{//创建要进行插入排序的数组int a[] { 9,1,2,5,7,4,8,6,3,5 };//调用希尔排序函数进行排序ShellSort(a, sizeof(a) / sizeof(int));//使用自定义打印函数打印排序后数组printf(使用希尔排序后的数组: );PrintArray(a, sizeof(a) / sizeof(int));
}//冒泡排序测试
void BSTest()
{//创建要进行插入排序的数组int a[] { 9,1,2,5,7,4,8,6,3,5 };//调用冒泡排序函数进行排序BubbleSort(a, sizeof(a) / sizeof(int));//使用自定义打印函数打印排序后数组printf(使用冒泡排序后的数组: );PrintArray(a, sizeof(a) / sizeof(int));
}//直接选择排序测试
void SlSTest()
{//创建要进行插入排序的数组int a[] { 9,1,2,5,7,4,8,6,3,5 };//调用直接选择排序函数进行排序SelectSort(a, sizeof(a) / sizeof(int));//使用自定义打印函数打印排序后数组printf(使用直接选择排序后的数组: );PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{//ISTest();//SSTest();//BSTest();SlSTest();return 0;
}
