数据结构算法:算法回顾之插入排序

使用范围:对小规模数据进行排序的方案，而且是稳定排序。
算法复杂度:O(n2)
思想:
首先我们来想一个问题。我们能否找到一种方法将一个数插入到有序数组中，并确保它仍然是有序的？
那么，我们如何将一组无序的数字插入到有序数组中，并确保它仍然是有序的呢？
至此，聪明的读者会发现，解决了这两个问题，我们就知道如何排序了。
下面详细解释一下检查排序的思路:
首先我们把一组无序的数分成两组，一组有序的，标记为A，一组无序的，标记为b，一开始A中只有一个元素，显然只有一个元素数组是有序的。我们开始把B中的元素一个一个地插入到A中，每次插入都保证A是有序的。B中的所有元素总是被插入到A中，所以我们把这个数组按顺序排列。
让我们看看如何在有序数组中插入一个数字。有一个数组{3，5，7，9，12}和一个数字6。我们可以从数组的前面开始搜索，直到找到一个不小于6的数，然后在前面加6。我们也可以从数组的后面开始搜索，直到找到一个不大于6的数字，然后在后面加上6。或者我们可以用binary找到6在数组中应该在的位置，然后把6放在那里。在这个寻找位置的过程中，基于比较的复杂度依次为O(n)，O(n)，O(log2n)。
那么，对一个数组排序的过程就是增加有序数组的过程。从一开始只有一个元素，然后整个数组都是有序的。然后，每次插入的时间复杂度与有序数组的大小有关。假设当前排序的数组大小为I，那么这次插入的最坏比较次数为I，那么，在最坏的情况下，当数组逆序时，总比较次数为1+2。
平均一次插入的比较次数为i/2，总比较次数为1/2+2/2+3/2+……+(n-1)/2 = n(n-1)/4
。所以平均比较复杂度为O(n2)，而
细心的读者会发现插入排序的时间复杂度不是O(n2)？怎么变成O(nlog2n)了？其实在排序的过程中，除了比较的成本，还有元素移动的成本。
如果用数组实现，每次移动的代价为O(n)，总代价为O(n2)。
如果用链表，每次移动的代价是O(1)，但是搜索的时候不能用二分法，所以总的代价是O(n2)。
下面是一段使用数组对数据结构的插入进行排序的c++代码:
/**
* Insert排序方法
* @param array数组名
* @ param length数组的起始位置[/Br/]* @长度进行排序[Br/]* @ Author Oracle OT & iceer[/Br/]*/[/Br/]Void Insert(int * array，int left，int length){[/Br/]//对于初始数组，
for(int I = left+1；I <左+长度；+I){
//现在的任务是将array[i]插入array[left，i]。
int current = array[I]；
int j；
//如果当前不小于array[j]，检查当前进入j+1的位置。()
for(j = I-1；(j > = left)& &(current < array[j])；-j){
array[j+1]= array[j]；
}
array[j+1] =当前；
}
}