创建qq网站吗,基于jsp网站开发参考文献,wordpress 博客信息,文山网站开发插入排序 插入排序代码实现代码优化 排序#xff1a; 排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的操作。
稳定性#xff1a; 假定在待排序的记录序列中#xff0c;存在多个具有相同的关键字的记录 排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。
稳定性 假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中 r[i] r[j] 且 r[i] 在 r[j] 之前而在排序后的序列中 r[i] 仍在 r[j] 之前则称这种排序算法是稳定的否则称为不稳定的。 注意稳定排序可以实现为不稳定的形式 而不稳定的排序实现不了稳定的形式 内部排序 数据元素全部放在内存中的排序。
外部排序 数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
插入排序
插入排序基本思想可以描述为 初始状态 将第一个元素视为已排序部分而将其余部分视为未排序部分。 逐步构建有序序列 从未排序部分依次取出元素将它们插入到已排序部分的合适位置以构建一个更大的有序序列。 比较并插入 对于未排序部分的每个元素将它与已排序部分的元素逐个比较找到合适的插入位置。通常比较过程会从已排序部分的末尾开始逐步向前移动直到找到合适的位置。 重复步骤 重复以上步骤直到所有元素都被放置在正确的位置上整个序列变成有序。
插入排序的核心思想是将未排序部分的元素逐个插入到已排序部分中不断地扩大已排序部分的长度直到整个序列有序为止。插入排序是一种稳定的排序算法它适用于小型数据集或已经部分有序的数据集。虽然它的平均时间复杂度为O(N^2)但在有序的情况下插入排序的时间复杂度为 ON。实际中我们玩扑克牌时就用了插入排序的思想。 代码实现 public static void insertSort(int[] arr) {int len arr.length;for (int i 1; i len; i) {// 从已经有序的位置从后往前开始比较int key arr[i];int end i-1;while (end 0 arr[end] key) {// 数据往后挪arr[end1] arr[end];end--;}// 找到了合适位置, 就插入进去arr[end1] key;}}代码优化
优化一二分插入排序
直接插入排序每次往前插入时是按顺序依次往前查找数据量较大时必然比较耗时效率低。
改进思路 在往前找合适的插入位置时采用二分查找的方式即折半查找。 public static void insertSort2(int[] arr) {int len arr.length;for (int i 1; i len; i) {// 从已经有序的位置从后往前开始比较int key arr[i];// 二分查找int left 0;int right i-1;while (left right) {int mid ((right-left) 1) left;if (arr[mid] key) {left mid 1;} else {right mid - 1;}}// 已经找到合适的位置了// 开始往后挪动元素for (int j i-1; j left; j--) {arr[j1] arr[j];}// 插入该元素arr[left] key;}}
注意 虽然找到合适位置使用了二分查找 但是最终还是需要挪动数据的 所以虽然性能有提升 但是时间复杂度还是 O N*N
优化二
先将整个待排元素序列分割成若干个子序列由相隔某个“增量”的元素组成的分别进行直接插入排序然后依次缩减增量再进行排序待整个序列中的元素基本有序增量足够小时再对全体元素进行一次直接插入排序。
改进思路二的方法实际上就是希尔排序。希尔排序详解
总结
时间复杂度 ON*N 最好情况是已经有序 时间复杂度是 ON 最坏是逆序 时间复杂度是 ON*N空间复杂度 O1是稳定排序对数据比较敏感 当数据本身就有序时 只需一趟 时间复杂度是 ON所以对数据本身的顺序比较敏感。不适合对于数据量比较大的排序应用。但是如果需要排序的数据量很小例如量级小于千那么插入排序还是一个不错的选择。元素集合越接近有序直接插入排序算法的时间效率越高。 插入排序可以作为快速排序的补充。
以上就是对插入排序的讲解 希望能帮到你 评论区欢迎指正
