【数据结构】基于比较的排序算法 - 插入排序

一前言排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减地排列起来的操作。而对于一个排序算法而言我们通常会从以下三个方面分析其性能稳定性假设待排序序列中存在多个重复值若是经过排序后重复值之间的相对位置不变则称这个排序算法是稳定的否则就是不稳定。时间复杂度代码执行次数随n的增长趋势通常使用大O的渐进法表示空间复杂度额外存储随n的增长趋势其中递归算法空间递归栈的最大深度通常使用大O渐进表示法常见的基于比较的排序算法有七种对于这七种排序算法又因其实现方式不同划分为以下四类插入排序直接插入排序、希尔排序选择排序选择排序、堆排序交换排序冒泡排序、快速排序归并排序归并排序本节内容主要讲解插入排序并且都是以排升序为例进行讲解。二直接插入排序1算法思想直接插入排序是一种简单的插入排序法其基本思想是当插入第ii1个元素时前面的array[0]array[1]...array[i-1]已经排好序此时用array[i]与前面已排好序的数据进行比较找到合适位置将其插入将插入位置及以后的元素依次后移一位。2算法特性当待排序序列越趋于有序时比较次数越少排序效率越高。时间复杂度最好情况O(N)待排序序列已经有序每次只需比较一次最坏情况O(N^2)序列完全逆序平均情况O(N^2)空间复杂度O(1)稳定性稳定3排序过程演示注由上演示也可得相同元素在排序后相对位置不变这便是稳定的排序算法。同时稳定的排序算法会同时存在稳定和不稳定两种实现并不是绝对的4算法实现/** * 直接插入排序 * param array 待排序序列 */ public static void insertionSort(int[] array) { if(array null) return; int n array.length; for(int i 1; i n; i ) { // 记录本轮待插入元素 int key array[i]; // 向前寻找插入位置同时后移元素 int j i - 1; while(j 0 key array[j]) { array[j 1] array[j]; j --; } // 出循环即找到插入位置写入即可 array[j 1] key; } }注意1i从1开始是因为默认第一个元素有序2内层循环条件为 key array[j]即找到第一个小于等于key的元素时停止默认前面均有序故key插入到此处一定有序这样可以保证排序是稳定的若是判断条件取等则该排序就变为不稳定三希尔排序1算法思想希尔排序又称为缩小增量排序是基于直接插入排序的一种优化其在排序前进行多轮预排序使得数据趋于有序最后一轮再对整组数据进行直接插入排序由于此时数据趋于有序故速度大大提升。其实现方式是先选定一个整数gap表示同一组中元素之间的间距再对按照间距gap分的每一组分别进行排序。重复前文操作gap不断变小最后为1当gap为1时即是对整组数据进行排序如下图所示2算法特性正式排序前执行多组预排序可以显著改善直接插入排序在趋于逆序数据中的劣势。时间复杂度取决于增量序列。平均约 O(n^1.3)若采用原始折半增量n/2, n/4, …, 1最坏为O(n²)采用 Hibbard 增量最坏 O(n^1.5)Sedgewick 增量最坏 O(n^1.3)。空间复杂度O(1)稳定性不稳定因为相同的元素可能被分到不同增量组中跨组移动后可能改变它们的相对次序3算法实现/** * 希尔排序 * param array 待排序序列 */ public static void shellSort(int[] array) { if(array null) return; // 缩小增量排序 int gap array.length / 2; while(gap 0) { insertionSortByGap(array, gap); gap / 2; } } /** * 按增量gap进行分组插入排序 * param array 待排序序列 * param gap 增量 */ private static void insertionSortByGap(int[] array, int gap) { int n array.length; for(int i gap; i n; i ) { int key array[i]; // 内层向前寻找步长为gap如此即可保证每次都是同组间排序 int j i - gap; while(j 0 key array[j]) { array[j gap] array[j]; j - gap; } array[j gap] key; } }注上述代码中的insertionSortByGap()方法其本质相当于交替插入排序其并非是每次将同一组排序完而是在不同组之间使用插入排序。当gap!1时外层循环每次步进都会切换到另一组而内层循环每次步进gap则可以保证每次都在本组内操作。也就是代码实现并没有显式地把数组分成若干组而是通过下标间隔gap直接对同组元素做插入排序。