网站做后台,网站开发课题开发背景,360建筑网一级消防工程师招聘,兰州网站备案谁家做#x1f525;博客主页#xff1a; 小羊失眠啦. #x1f3a5;系列专栏#xff1a;《C语言》 《数据结构》 《Linux》《Cpolar》 ❤️感谢大家点赞#x1f44d;收藏⭐评论✍️ 文章目录 一、排序的概念及其运用1.1 排序的概念1.2 常见的算法排序 二、 冒泡排序三、直接插入排… 博客主页 小羊失眠啦. 系列专栏《C语言》 《数据结构》 《Linux》《Cpolar》 ❤️感谢大家点赞收藏⭐评论✍️ 文章目录 一、排序的概念及其运用1.1 排序的概念1.2 常见的算法排序 二、 冒泡排序三、直接插入排序四、希尔排序五、 选择排序 一、排序的概念及其运用
1.1 排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。排序算法就是如何使得记录按照要求排列的方法。
稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。
内部排序数据元素全部放在内存中的排序。
外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 常见的算法排序
排序算法分为比较类排序和非比较类排序如下图所示 二、 冒泡排序
思想 : 在一个序列中每次对序列中的相邻记录的键值大小进行比较将较大(升序)或较小(降序)的记录向后移动。如此循环大/小的记录会慢慢“浮”到序列的后端整个过程就像是冒泡一样顾称之为冒泡排序。冒泡过程以下是对某个序列进行冒泡排序的过程 可以看出对于上面具有5个元素的无序数组我们通过4趟的冒泡后就将其变为有序数组每一趟冒泡后都可以使最大的数沉底。 动图演示我们可以通过一下动图感受一下冒泡两两比较的过程 循环控制很明显我们需要两层循环来控制冒泡排序的过程。内层循环控制当前趟的数据交换外层循环控制冒泡排序的趟数。外层循环结束条件由于每一趟结束后都有一个数冒到序列后端因此对于N个数的序列来说一共需要N-1趟(只剩一个数不需要冒泡)。
for (int i 0; i n - 1; i) //外层循环N-1趟
{;
}内层循环结束条件内层循环用于数据的比较。已知N个数据共需比较N-1次由于每一趟结束后就有数据到正确的位置下一趟需要比较的数据个数就会少1因此每趟的比较次数随着趟数的增加呈递减趋势初始为N-1次。
for (int i 0; i n - 1; i) //外层循环N-1趟
{for (int j 0; j n - 1 - i; j) //内层循环次数随趟数增加而递减初始为N-1{;}
}完整代码
void swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void BubblingSort(int* a, int n)
{for (int i 0; i n - 1; i) //外层循环N-1趟{for (int j 0; j n - 1 - i; j) //内层循环次数随趟数增加而递减初始为N-1{if (a[j] a[j 1]) //升序排列较大的往后移{swap(a[j], a[j 1]); //交换}}}
}改进优化上面的代码还存在着改进空间我们来看下面两个情景 对于情境1我们只需一趟冒泡即可让数组有序而如果按照上面的代码我们依旧要进行4趟的冒泡即有三趟是无效的。 而情境2就更夸张了数组已经有序我们却傻乎乎的做了4趟无效冒泡。无疑是非常浪费时间的。 考虑到这些情况我们提出了优化方案在每趟结束后判断一下当前趟是否发生了元素交换如果没有则说明序列已经有序了及时止损反之继续。优化后的代码如下 void swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void BubblingSort(int* a, int n)
{for (int i 0; i n - 1; i) //外层循环N-1趟{int flag 0;for (int j 0; j n - 1 - i; j) //内层循环次数随趟数增加而递减初始为N-1{if (a[j] a[j 1]) //升序排列较大的往后移{swap(a[j], a[j 1]); //交换flag 1;}}if (flag 0)break;}
}时间/空间复杂度结合上面的图片和代码我们可以看出总共N-1趟每趟N-1N-2…次比较共比较 (N-1) (N-2) (N-3) (N-4) (N-5) … 1次时间复杂度为O(N^2)而由于没有额外的辅助空间空间复杂度为O(1)。稳定性分析由于我们是将较大的或较小的进行交换当两个数相等时并不会进行交换因而不会改变相同元素的先后次序所以冒泡排序是稳定的排序。 三、直接插入排序
思想把待排序的数据按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的数据插入完为止得到一个新的有序序列 。 实际中我们玩扑克牌时就用了插入排序的思想。 注意数组中除了第一个元素默认有序其余所有元素都看作待插入数据。
排序步骤
将有序数据的最后一个元素的下标记为 end则第一个待插入元素的下标为 end1记作 tmp将 tmp 与有序数据从后向前依次比较如果 tmp a[end]就将 a[end] 向后移动end–再去找下一位进行比较直到 tmp a[end] 或者 end 0将 tmp 插入到 end1 的位置重复步骤就可以实现排序
代码实现
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];}else{break;}--end;}a[end 1] tmp;}
}时间/空间复杂度结合上面的图片和代码我们可以看出时间复杂度为O(N^2)由于没有额外的辅助空间空间复杂度为O(1)。稳定性分析是稳定的排序。 四、希尔排序 思想 先选定一个整数把待排序文件中所有记录分成个组所有距离为3的数据分在同一组内并对每一组内的数据进行排序。然后重复上述分组和排序的工作。当距离1时所有数据在统一组内排好序。 希尔排序分为两步 预排序直接插入排序 当元素集合越接近有序直接插入排序的效率很高希尔排序就是通过预排序使元素集合接近有序再进行直接插入排序这样大大提高了效率。 排序步骤:
选取一个合适的 gap 作为间距将间距为 gap 的数据分为一组分成 gap 组每一组数据都进行直接插入排序使数据接近有序不断缩小间距当 gap1 时数据进行直接插入排序实现排序
代码实现
void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}特点: 希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算。空间复杂度O(1)稳定性不稳定 五、 选择排序
思想 : 每一次从待排序的数据元素中选出最小(升序)或最大(降序)的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。**选择过程**以下是对某个序列进行选择排序的过程 动图演示我们一样通过动图感受一下选择排序的过程 循环控制类似的我们需要两层循环来控制选择排序的过程。内层循环遍历序列找出最大/最小值外层循环控制选择的次数。外层循环结束条件每一次遍历完都可以选出一个数换到起始位置一共N个数故要选N-1次(最后一个数不需要选择)
for (int i 0; i n-1; i) //外层循环共要选择n-1次
{;
}内层循环结束条件内层循环通过比较进行选数一开始N个数需要比较N-1次然后每趟结束后下一次选择的起始位置就往后移动一位比较次数减1
for (int i 0; i n-1; i) //外层循环共选择n-1次
{for (int j i 1; j n; j) //内层循环起始位置开始向后进行比较选最小值{;}
}完整代码
void swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void SelectSort(int* a, int n)
{for (int i 0; i n - 1; i) //外层循环共选择n-1次{int mini i; //记录最小值的下标初始为第一个数下标for (int j i 1; j n; j) //内层循环起始位置开始向后进行比较选最小值{if (a[mini] a[j]) //比最小值小交换下标{mini j;}}swap(a[mini], a[i]); //将最小值与起始位置的数据互换}
}时间/空间复杂度一共选了N-1次每次选择需要比较N-1N-2N-3…次加起来和冒泡一样时间复杂度为O(N)没有用到辅助空间空间复杂度为O(1)稳定性分析由于是选数交换在交换的过程中很可能会打乱相同元素的顺序例如下面这个例子 我们发现在第一趟交换中黑5被交换到了红5后面在整个排序结束后黑5依然在红5的后方与最开始的顺序不一致。由此我们可以得出选择排序是不稳定的排序。
本次的内容到这里就结束啦。希望大家阅读完可以有所收获同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言小羊一定认真修改写出更好的文章~~
