当前位置：首页 > news >正文

【算法】插入排序

news 来源：原创 2025/8/21 10:30:03

算法系列五：插入排序

一、直接插入排序

1.原理

2.实现

3.性质

3.1时间复杂度

3.2空间复杂度

3.3稳定性

二、希尔排序

1.原理

1.1优化方向

1.2优化原理

2.设计

2.1比较无序时

2.2比较有序时

3.实现

4.性质

4.1时间复杂度

4.2空间复杂度

4.3稳定性

解放变量

多变量存储数据可实现其中的变量被解放了可去不失数据覆盖存别的值，被解放变量覆盖存别的值又是从变量里来的又能再解放出下一对数据解放传递着，能实现数据在变量间的调整交换位置存放，实现排序的基础

一、直接插入排序

1.原理

插排就是要排的数据举着往前面维护着的有序数列在解放交换数据的模式下找到它大小的位置解放安全地覆盖放入，从前往后一个个插入排好序进去，维护成的有序数列从前往后越来越大，直到把所有数据都插入维护进去，插排排序就完成了

2.实现

public static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int tmp = array[i];int j = i-1;for (; j >= 0 ; j--) {if(array[j] > tmp) {array[j+1] = array[j];}else {break;}}array[j+1] = tmp;}}

3.性质

3.1时间复杂度

首先第一个元素去维护进有序数列时，它一进去只有它一个一定就直接有序了不需要维护成有序，从第二个元素起，每个元素都要举着往有序数列前找它大小的解放位置放，n个元素一共要去往前检查维护n-1次：

在完全有序的情况下，每次里面的for循环一进去执行就break，时间复杂度为O(n)
在完全逆序的情况下，每个数据维护进当前有序数组都要遍历比较到有序数组末尾，执行次数为1~n-1递增的等差数列和次数，时间复杂度为O(n^2)

3.2空间复杂度

O(1)

3.3稳定性

稳定

二、希尔排序

希尔排序是直接插入排序的优化版

1.原理

1.1优化方向

直接插入排序中，因为n个元素要去检查维护n-1次是固定变不了的，要优化就只能从尽可能减少每次的检测维护里往前检查搜寻次数、交换次数来实现

1.2优化原理

待对它插排的整体数组越有序，即数组里面每个数据最开始离它们各自的最终排序位置都越近，那么n-1次每个元素对待的前面已排好序的数组就会都是兼容性顺序很好很接近它们在当前数组的排序位置且也是最终整体数组相对排序的位置：

每个元素去维护数组时经常都是没检查搜寻几次交换几次就到达了当前维护数组的排序位置就break了且该位置也是最终整体排好序数组的相对位置说明数据先后进来维护都自然地从前往后排的不怎么需要往前检查移动交换，因为它们这些数据本身就很接近最终数组排序位置，排序时按顺序从前往后进来维护它们也是进来就直接处在要排的位置上了，按顺序来直接到直接是最终位置

2.设计

2.1比较无序时

比较无序时，每次维护里连续重复地进前面有序数组维护交换次数会很多且不靠近最终整体数组有序位置，所以：

无序时大跨越式地横跨取数进维护有序组，会发现最终维护的组会很多因为跨数太大了它们无法前后续上，所以它们的比较不是很会连续重复进行，且它们的交换跨度很大，能用一次少的比较成本实现数据的大幅度交换，小成本实现数据的大致整体左小右大排列

2.2比较有序时

无序时的大跨越式横跨小成本实现整体数组大致左小右大比较有点序后：

跨越式取数的gap适当变小缩为原来的一半，因为此时面对的是较有点序的整体数组，我们的排序就以它更有点序下对应用到它有点序的程度来深入，一路上全合适的程度全效地利用着它的渐有序进行排列，到后面随着数组越来越有序，分的组越来越少，精确程度地深入去排已经很有序的数据高效地全完成

3.实现

public static void shellSort(int[] array) {int gap = array.length;while (gap > 1) {gap /= 2;shell(array,gap);}}private static void shell(int[] array,int gap) {for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i-gap;for (; j >= 0 ; j-=gap) {if(array[j] > tmp) {array[j+gap] = array[j];}else {break;}}array[j+gap] = tmp;}}

4.性质

4.1时间复杂度

O(n^1.3)

4.2空间复杂度

O(1)

4.3稳定性

不稳定

一、直接插入排序

1.原理

2.实现

3.性质

3.1时间复杂度

3.2空间复杂度

3.3稳定性

二、希尔排序

1.原理

1.1优化方向

1.2优化原理

2.设计

2.1比较无序时

2.2比较有序时

3.实现

4.性质

4.1时间复杂度

4.2空间复杂度

4.3稳定性

相关文章：