上海住房和城乡建设厅网站首页,网站建设微信,WordPress图片无缝,文案策划公司#x1f31f;#x1f31f;作者主页#xff1a;ephemerals__
#x1f31f;#x1f31f;所属专栏#xff1a;算法
目录
前言
写一串测试数据
交换两元素的函数
一、冒泡排序
二、选择排序
三、插入排序
四、希尔排序
程序全部代码
总结 前言 排序算法是计算机科…
作者主页ephemerals__
所属专栏算法
目录
前言
写一串测试数据
交换两元素的函数
一、冒泡排序
二、选择排序
三、插入排序
四、希尔排序
程序全部代码
总结 前言 排序算法是计算机科学领域的基石之一它不仅在算法的理论研究中占据重要地位更是实际开发当中解决数据组织检索处理等问题的关键工具。现如今数据日益增长理解并掌握这些排序算法的原理、特点及其适用场景对于提升程序效率、优化用户体验至关重要。 八大排序算是排序算法当中知名度较高的了它们不仅涵盖了简单直观的排序方法以便初学者学习理解也包含了高效复杂的排序策略广泛应用于实际开发。 本篇文章作者主要介绍并实现八大排序算法的其中四种冒泡排序、选择排序、插入排序、希尔排序。
正文开始
写一串测试数据 首先我们写一个乱序的数组便于后续排序测试
#include stdio.hint main()
{int arr[] { 5,9,4,0,2,7,8,0,0,1,4,4,1,3,5,6,3,2,9,7 };int sz sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数for (int i 0; i sz; i)//打印数组{printf(%d , arr[i]);}return 0;
}
交换两元素的函数 在这里我们将交换两个元素的步骤封装成一个函数便于后续多次调用。
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}
一、冒泡排序 冒泡排序是一种简单的排序算法易于初学者理解和学习。它的核心思想就是重复遍历数组比较相邻两个元素如果它们的顺序错误则交换之。直到数组中没有顺序错误的情况则排序已经完成。 它的具体步骤描述如下 1.遍历数组比较所有的相邻元素如果前者大于后者默认升序则交换它们。 2.当遍历到数组最后一对相邻元素后数组中最后一个元素会是最大的数。此时一趟冒泡排序完成。 3.重新遍历数组比较相邻元素最后一个元素除外因为已经是最大的了。一趟结束后数组中第二大的元素将位于倒数第二个位置。 4.重复进行上述步骤已经就位的元素除外直到所有元素均不需要再交换。 动图表示 接下来我们尝试实现冒泡排序
void BubbleSort(int* arr, int n)
{//外层循环控制排序的趟数for (int i 0; i n - 1; i)//每一趟排序使一个元素就位n个元素的数组需要n-1趟排序最后一趟会使前两个元素就位{//内层循环控制需要比较的相邻元素for (int j 0; j n - 1 - i; j)//每一趟结束后需要比较的元素便减少一个所以要减去i{if (arr[j] arr[j 1])//若前者大于后者说明顺序错误需要交换{Swap(arr[j], arr[j 1]);//交换两元素}}}
}
不难发现如果没有到达排序的趟数但是数组已经有序程序就会继续进行不必要的元素比较运行效率降低。基于这一点我们可以做出如下改进
void BubbleSort(int* arr, int n)
{//外层循环控制排序的趟数for (int i 0; i n - 1; i)//每一趟排序使一个元素就位n个元素的数组需要n-1趟排序最后一趟会使前两个元素就位{int flag 1;//假设数组已经有序//内层循环控制需要比较的相邻元素for (int j 0; j n - 1 - i; j)//每一趟结束后需要比较的元素便减少一个所以要减去i{if (arr[j] arr[j 1])//若前者大于后者说明顺序错误需要交换{Swap(arr[j], arr[j 1]);//交换两元素flag 0;//发生了交换说明数组并非有序}}if (flag 1)//如果数组已经有序则不需要排序直接退出循环{break;}}
}
接下来我们对测试数组进行排序
int main()
{int arr[] { 5,9,4,0,2,7,8,0,0,1,4,4,1,3,5,6,3,2,9,7 };int sz sizeof(arr) / sizeof(arr[0]);BubbleSort(arr, sz);//冒泡排序for (int i 0; i sz; i){printf(%d , arr[i]);}return 0;
}
运行结果 可以看到排序成功了。 冒泡排序的特性总结 空间复杂度O(1) 时间复杂度O(N^2) 稳定性相同值的元素排序前后的相对次序是否保持不变稳定 无论数组是否有序都有大量元素被重复地进行比较和交换运行效率不高 二、选择排序 选择排序是一种比较接近人类思想的排序算法它的核心思想非常简单从数组中寻找最小最大元素将其放于数组第一个位置最后一个位置处然后再从剩余的元素中寻找最小最大值放到数组第二个位置倒数第二个位置处...... 具体步骤如下 1.首先遍历数组寻找到数组中最小的元素将其与数组的首元素进行交换。 2.开始遍历数组的剩下部分寻找最小值与该部分的首元素进行交换。 3.重复第二步直到“该部分”只有一个元素为止说明数组已经排序好。 动图表示 接下来我们尝试代码实现选择排序
void SelectSort(int* arr, int n)
{//外层循环控制遍历次数以及遍历的起始位置for (int i 0; i n; i){int mini i;//假设最小值位于遍历部分的首元素处//内层循环寻找最小值for (int j mini 1; j n; j){if (arr[j] arr[mini])//将更小的元素标记为mini{mini j;}}Swap(arr[i], arr[mini]);//将最小值与遍历部分的首元素交换}
}
运行测试 选择排序特性总结 空间复杂度O(1) 时间复杂度O(N^2) 稳定性不稳定 使用寻找最值进行交换的方式虽然在效率上相比冒泡排序有所提升但是依然不是很实用。 三、插入排序 插入排序是一种适用于对少量数据进行排序的算法它的效率要略高于冒泡排序和选择排序。就像玩扑克牌一样它的核心思想是将一个个数据不断插入到已经有序的数组的合适位置从而使整个数组有序。 具体步骤如下 1.将数组首元素视为有序。 2.将有序数组的下一个元素取出然后开始对该元素之前的部分进行遍历找到合适位置并插入。 3.将这部分有序数组看成整体重复第二步直到将最后一个元素调整完成。 动图表示 代码实现如下
void InsertSort(int* arr, int n)
{//外层循环确定遍历次数for (int i 0; i n - 1; i){int end i;//记录有序数组的末尾位置int tmp arr[end 1];//保存需要插入的元素tmp//内层循环控制对有序数组的遍历while (end 0)//当end小于0时一次遍历结束{if (arr[end] tmp){arr[end 1] arr[end];//该值后移一位留空缺end--;//继续向前走}else//当tmp值比有序数组中某元素小或相等时说明tmp应该插入在该元素之后终止遍历{break;}}arr[end 1] tmp;//插入到该元素之后的位置}
}
代入测试 插入排序性能总结 空间复杂度O(1) 时间复杂度O(N^2) 稳定性稳定 虽然在时间复杂度上没有什么变化但是相比冒泡排序和选择排序性能有所提升。由于它是按照顺序进行扫描并且插入的所以相同值元素的相对位置不会改变是一种稳定的排序算法是排序少量数据的首选。不过面对的数据量庞大时依然不够看。 四、希尔排序 希尔排序又称为缩小增量排序是一种效率很高的排序算法算是插入排序的升级版。它的核心思想也比较简单首先对数组进行预排序使其接近有序然后进行插入排序。 这里介绍一下排序的思路 首先选定一个增量gap(这里我们使gap数组元素n/3)将数组中相差gap个位置的元素视为一个子序列然后分别对这些子序列进行插入排序。当所有子序列排序结束之后使gap的值逐渐减小再除以3然后再将相差gap个位置的元素构成的子序列进行插入排序......直到gap为1时构成的序列就是数组本身对其进行一次插入排序即可。 当然这里的增量gap并不是只有n/3这一种取法。他还有很多种取法例如n/2、n/4等。但要注意变化的gap值应尽量满足没有除1以外的公因子并且最后一次gap的值是1。
接下来我们尝试实现希尔排序
void ShellSort(int* arr, int n)
{int gap n;//定义增量gap//循环控制预排序的次数以及进行最后一次插入排序while (gap 1){gap gap / 3 1;//首先调整gap值//进行插入排序//注意细节处理是对相隔gap的元素进行排序for (int i 0; i n - gap; i)//一次循环结束后i就走向了下一个子序列的起始位置{int end i;//记录有序部分的末尾位置int tmp arr[end gap];//endgap位置的元素视为子序列中的下一个元素while (end 0){if (arr[end] tmp){arr[end gap] arr[end];end - gap;//一次向前走gap个位置}else{break;}}arr[end gap] tmp;}}
}
从代码角度看它相比插入排序又多了一层循环效率怎么会高于插入排序呢实际上有了预排序之后最后一次插入排序所节省的时间要远远大于预排序消耗的时间。
代入数据测试 希尔排序性能总结 空间复杂度O(1) 时间复杂度O(N^1.3)(计算过程相对复杂) 稳定性不稳定 相比冒泡排序选择排序和插入排序希尔排序的时间复杂度较低运行效率更高更适用于大规模数据的排序。但是它的性能不稳定易受数据和增量选择的影响。 程序全部代码
程序全部代码如下
#include stdio.h
#include stdlib.h//交换函数
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}//冒泡排序
void BubbleSort(int* arr, int n)
{//外层循环控制排序的趟数for (int i 0; i n - 1; i)//每一趟排序使一个元素就位n个元素的数组需要n-1趟排序最后一趟会使前两个元素就位{int flag 1;//假设数组已经有序//内层循环控制需要比较的相邻元素for (int j 0; j n - 1 - i; j)//每一趟结束后需要比较的元素便减少一个所以要减去i{if (arr[j] arr[j 1])//若前者大于后者说明顺序错误需要交换{Swap(arr[j], arr[j 1]);//交换两元素flag 0;//发生了交换说明数组并非有序}}if (flag 1)//如果数组已经有序则不需要排序直接退出循环{break;}}
}//选择排序
void SelectSort(int* arr, int n)
{//外层循环控制遍历次数以及遍历的起始位置for (int i 0; i n; i){int mini i;//假设最小值位于遍历部分的首元素处//内层循环寻找最小值for (int j mini 1; j n; j){if (arr[j] arr[mini])//将更小的元素标记为mini{mini j;}}Swap(arr[i], arr[mini]);//将最小值与遍历部分的首元素交换}
}//插入排序
void InsertSort(int* arr, int n)
{//外层循环确定遍历次数for (int i 0; i n - 1; i){int end i;//记录有序数组的末尾位置int tmp arr[end 1];//保存需要插入的元素tmp//内层循环控制对有序数组的遍历while (end 0)//当end小于0时一次遍历结束{if (arr[end] tmp){arr[end 1] arr[end];//该值后移一位留空缺end--;//继续向前走}else//当tmp值比有序数组中某元素小或相等时说明tmp应该插入在该元素之后终止遍历{break;}}arr[end 1] tmp;//插入到该元素之后的位置}
}//希尔排序
void ShellSort(int* arr, int n)
{int gap n;//定义增量gap//循环控制预排序的次数以及进行最后一次插入排序while (gap 1){gap gap / 3 1;//首先调整gap值//进行插入排序//注意细节处理是对相隔gap的元素进行排序for (int i 0; i n - gap; i)//一次循环结束后i就走向了下一个子序列的起始位置{int end i;//记录有序部分的末尾位置int tmp arr[end gap];//endgap位置的元素视为子序列中的下一个元素while (end 0){if (arr[end] tmp){arr[end gap] arr[end];end - gap;//一次向前走gap个位置}else{break;}}arr[end gap] tmp;}}
}int main()
{int arr[] { 5,9,4,0,2,7,8,0,0,1,4,4,1,3,5,6,3,2,9,7 };int sz sizeof(arr) / sizeof(arr[0]);//BubbleSort(arr, sz);//SelectSort(arr, sz);//InsertSort(arr, sz);ShellSort(arr, sz);for (int i 0; i sz; i){printf(%d , arr[i]);}return 0;
}
总结 今天我们学习了八大排序的其中四种冒泡排序选择排序插入排序和希尔排序。在理解这些排序思想和实现它们的过程当中我们感受到了算法之美也加强了分析问题、解决问题的能力。之后博主会和大家分享剩下的几种排序算法。如果你觉得博主讲的还不错就请留下一个小小的赞在走哦感谢大家的支持❤❤❤
