北京北大青鸟学校讲解：插入排序

什么是插入排序？北京北大青鸟学校学术老师讲解：插入排序是一种通过不断地把新元素插入到已排好序的数据中的排序算法，常用的插入排序算法包括直接插入排序和shell排序，直接插入排序实现比较简单，时间复杂度是O（n），但是直接插入没有充分的利用已插入的数据已经排序这个事实，因此有很多针对直接插入排序改进的算法，例如折半插入排序等，下边是直接插入排序的Java实现：(北大青鸟课程)

view sourceprint?
01 public static void insertSort(int[] elements){ 
02 for(int I = 1;I <elements.length; i++){ 
03 int j = -1; 
04 while(j <= I && elements[i] > elements[++j]);//找到element[i]应该摆放的位置，此处可以利用查找算法进行优化 
05 if(j < i){ 
06 //将j之后的数据移动一位，然后把elements[i]移动到j处 
07 int temp = elements[i]; 
08 for(int k = i-1;k >= j;k--){ 
09 elements[k+1] = elements[k]; 
10 } 
11 elements[j] = temp; 
12 } 
13 } 
14 }(北大青鸟课程)

北京北大青鸟学校介绍另一种常用的插入排序算法：Shell排序也是对直接插入排序算法的一种优化，因此可以说直接插入排序是一种特殊的Shell排序，Shell排序对直接插入排序的优化主要体现在，Shell排序通过使用一个增量序列（递减），每次把要排序的数组分成几个子数组，然后对子数组进行插入排序，这样可以减少比较和移动数据的次数，Shell排序是一种非常高效的排序算法，该算法的思想是：

1.以h（h一般取n/2）为间隔将n个元素列分为几个小组，在每个小组内按直接插入法排序
2.令h=h/2，重复第1步
3.当h=1时，排序结束（此时相当于直接插入排序，不过由于数据已经基本排好序，因此比较次数和移动次数比直接插入排序少很多）

Shell排序的Java实现如下：
view sourceprint?
01 public static void shellSort(int[] elements){ 
02 for(int h = elements.length/2;h > 0;h /= 2){ 
03
04 for(int i = h;i < elements.length; i++){ 
05 int j = i % h; 
06 while(j <= i && elements[i] > elements[j]) j += h;//找到element[i]应该摆放的位置 
07 if(j < i){ 
08 //将j之后的数据移动h位，然后把elements[i]移动到j处 
09 int temp = elements[i]; 
10 for(int k = i-h;k >= j;k -= h){ 
11 elements[k+h] = elements[k]; 
12 } 
13 elements[j] = temp; 
14 } 
15 } 
16
17 } 
18 }(北大青鸟课程)
文章由北京北大青鸟学校学术部老师提供