排序算法-4--- 插入排序 （Insertion Sort）
插入排序 （Insertion Sort）
1、概念
插入排序 是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到 O(1)}的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
2、运行过程
插入排序可以分为两种方式插入，分别是直接插入和折半插入。
我们首先来看一下直接插入的思路和运行过程
1、直接插入
-
基本思路：
顺序地把待排序的序列中的各个元素按其关键字的大小，插入到已排序的序列的适当位置。 -
运行过程
- 1、将待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
-
2、从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
image
2、折半插入
- 基本思路：
顺序地把待排序的序列中的各个元素按其关键字的大小，通过折半查找插入到已排序的序列的适当位置。 - 运行过程
- 1、将待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 2、从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置，在查找元素的适当位置时，采用了二分搜索。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
3、二分搜索
如何确定一个元素在数组中的位置? (假设数组里面全都是 整数)
如果是无序数组,从第0个位置开始遍历搜索,平均时间复杂度: 0(n)
image
如果是有序数组，可以使用二分搜索，最坏时间复杂度: 0(logn)
image
二分搜索的思路：
- 假没在[begin, end)范圃内捜索某个元素v, mid == (begin + end)/2
- 如果v< m,去[begin, mid)范国内二分搜索
- 如果v> m，去[mid + 1, end)范国内二分搜索
-
如果v== m,直接返回mid
image
二分查找思路实现
image
4、代码：
- 直接插入
java
public void sort(Integer[] array){
for (int i = 1; i < array.length; i++) {
Integer cur = i;
Integer v = array[cur];
while (cur > 0 && v < array[cur - 1]){
array[cur] = array[cur-1];
array[cur-1] = v;
cur --;
}
}
}
- 折半插入
public int[] array;
public int[] sort() {
for (int begin = 1; begin < array.length; begin++) {
insert(begin, search(begin));
}
return array;
}
/**
* 将source位置的元素插入到dest位置
* @param source
* @param dest
*/
private void insert (int source ,int dest){
int v = array[source];
for (int i = source;i > dest;i--){
array[i] = array[i - 1];
}
array[dest] = v;
}
/*
* 利用二分搜索找到index 位置元素的待插入位置
* 已经排好的数组的区间范围是 【0，index）
* @param index
* @return
*/
private int search(int index){
int begin = 0;
int end = index;
while (begin < end){
int current = (end + begin)/2;//(end - begin )>>1;
if (array[index] < array[current] ){
end = current;
}else{
begin = current + 1;
}
}
return begin;
}
public void setArray(int[] array) {
this.array = array;
}
public int[] getArray() {
return array;
}
5、性能
当原始序列“正序”时，直接插入排序效果最好，所以直接插入排序最好情况下时间复杂度为O(n)；当原始序列“逆序”时，直接插入排序效果最差，所以直接插入排序最坏情况下时间复杂度为O(n^2)。
直接插入排序平均时间复杂度为O(n^2)；空间复杂度为O(1)；是稳定的排序算法。
需要注意的是，使用了二分搜索后,只是减少了比较次数,但插入排序的平均时间复杂度依然是0(n^2)
6、逆序对 （Inversion）
什么是逆序对?
数组<2,3,8,6,1>的逆序对为: <2,1> <3,1> <8,1> <8,6> <6,1>,共5个逆序对
插入排序的时间复杂度与逆序对的数量成正比关系
逆序对的数量越多，插入排序的时间复杂度越高
最坏、平均时间复杂度: 0(n^2)
最好时间复杂度: 0(n)
空间复杂度: 0(1)
属于稳定排序
当逆序对的数量极少时，插入排序的效率特别高甚至速度比0(nlogn)级别的快速排序还要快
数据量不是特别大的时候，插入排序的效率也是非常好的
参考：《恋上数据结构与算法第二季》
