算法与结构--插入排序
前言
万事万物皆算法,一切的始源与终点皆为思想。
在介绍插入算法之前,我们来简单回顾上一篇学的选择排序,选择排序基本思路就是每次遍历找到最小的元素放在首位置,这样他的时间复杂度是n2,但是由于其交换的次数不是很多,他的时间并没有冒泡排序等n2时间大。那么我们本节学习的插入排序有什么优势和缺点呢,废话不多说,割了
------------------------------------------------------
插入排序
怎么记住插入排序呢,大家都玩过扑克牌,每次抓玩牌整理纸牌的时候都会挑选出小牌插入到该有的位置,这个工程和插入排序很像,我们先看下插入排序的动图。
从图上可以看出,他的时间复杂度也为n2,而且每次插入会导致后面的元素都交换位置,大家都知道,数组交换位置相比遍历要耗时的多,那么插入排序的优势在哪呢,我们先来写下代码,还是在上一篇的选择排序的基础上写。
/**
* 插入排序
*/
private static void insertSort(int arr[]) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
SortHelper.swapArr(arr, j, j - 1);
}
}
}
}
代码很简单,我么从i=1开始最外层遍历,然后比较i之前两两元素的大小,符合就交换位置,这样就实现了排序,我们测试下选择排序和插入排序的时间对比吧,还是比较10000个元素的排序时间
/**
* 选择排序
*
* @author wangmj
* @since 2019/3/13
*/
public class SortTest {
public static void main(String[] args) {
//随机生成区间内的正整数
int[] arr = SortHelper.generateArr(10000, 2, 30000);
//copy数据
int[] arr1 = Arrays.copyOf(arr, 10000);
//选择排序
long start = System.nanoTime();
selectionSort(arr);
long endTime = System.nanoTime();
System.out.println("selection time = " + TimeUnit.NANOSECONDS.toMillis(endTime - start));
SortHelper.printer(arr);
//插入排序
long start1 = System.nanoTime();
insertSort(arr1);
long endTime1 = System.nanoTime();
System.out.println("insert time = " + TimeUnit.NANOSECONDS.toMillis(endTime1 - start1));
SortHelper.printer(arr1);
}
/**
* 插入排序
*/
private static void insertSort(int arr[]) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
SortHelper.swapArr(arr, j, j - 1);
}
}
}
}
/**
* 选择排序
*
* @param arr 数组
*/
private static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
SortHelper.swapArr(arr, i, minIndex);
}
}
}
结果如下
可以看到选择排序的时间会比插入排序的小一点(大多数是,主要是看交换次数)。
改进插入排序
那么插入排序为什么比较重要呢,我们先分析下为什么我们刚写的插入排序为什么这么慢呢,其实刚开始的时候我们已经介绍过,慢的原因无疑就是每次j遍历的时候,会比较j和j-1的大小,并且会交换,交换次数会特别多,那么我们怎么改进呢。
这次我们比较之后不轻易交换位置,直到找到合适的位置在把i的元素放到j的位置
/**
* 升级版插入排序
*/
private static void insertSortPro(int arr[]) {
for (int i = 0; i < arr.length; i++) {
int value = arr[i];
int j;
for (j = i; j > 0 && arr[j - 1] > value; j--) {
arr[j] = arr[j - 1];
}
//说明没有过交换
if (j != i) {
arr[j] = value;
}
}
}
这次我们再次测试下三个排序的时间
可以看到,改进后的时间只有32ms,若是一个接近有序的数组,其时间会更低,时间复杂度也降低至接近n,此速度是非常快的
总结
插入排序在改进后速度很快,他的时间复杂度n2,但是当数组接近有序的时候,其时间复杂度会接近为o(n),这也导致很多复杂排序会在内部结合插入排序,因为其简单并且在某些情况下很高效,后面我们要学习的希尔排序就是插入排序的一种变种