十大排序：插入排序

插入排序及希尔排序

插入排序的思想：插入排序的思想有点类似摸扑克牌，首先抽取第一张，当做已经排好序，然后第二张，插入到已经排好序的扑克牌中，依次类推，第三张...直到最后一张。

void insertSort(int arr[],int len)
{for(int i=1;i<len;i++){//类似于倒着的冒泡排序for(int j=0;j<i && arr[j] < arr[j-1];j++){swap(arr,j,j-1);}}
}//还有一种方法是找到比前面大的数之后,整体向后移动.
void insertSort(int arr[],int len)
{for(int i=1;i<len;i++){int tmp = arr[i];for(int j=0;j<i;j++){if(arr[j] > tmp){for(int k=i;k>j;k--){arr[k] = arr[k-1];}arr[j] = tmp;tmp = arr[i];}}}
}

分析：插入排序比冒泡排序快。

在数组基本有序的情况下比选择排序好。

简单排序比较：

冒泡排序基本不用，太慢；

选择排序基本不用，不稳定；

插入排序在数量小且基本有序的情况下优先选择。

下面介绍一下改进的插入排序：希尔排序

希尔排序的思想：根据一个数组的长度取一个间隔N，每间隔N个数取一个值，在数组中取一组数，对这一组数用插入排序排列。直到全排列。然后再缩小这个间隔，变为N/2或者其他比N小的间隔，然后每隔新的间隔取一组数，再次对这组数排列，直到全排列，一直缩小N，直到N变为1，再对全数进行一次插入排序，就得到了最终的结果。

分析：

缺点：希尔排序不稳定。

优点：间隔N比较大的时候，移动的次数少。并且经过大间隔数的排序后，小的数靠前了，大的数靠后了。

间隔小的时候，移动的距离比较短。两者结合，总的移动的次数会比单纯的插入排序的次数少。

第一种取间隔的方式：N->N/2->N/4....1

void shellSort(int arr[],int len)
{for(int gap = len >> 1;gap > 0;gap = gap/2){for(int i=gap;i<len;i++){for(int j=i;j>gap-1;j-=gap){if(arr[j] < arr[j-gap]){swap(arr,j,j-gap);}}}}
}

第二种取间隔的方式：

Knuth序列

h=1
h=3*h+1

1,4,13,....

根据Knuth序列和数组的长度，确定一个最大的间隔h，然后依次递减到1.

void shellSort(int arr[],int len)
{int h;while(h <= len/3){h = 3 * h + 1;}for(int gap = h;gap > 0;gap = (gap-1)/3){for(int i=gap;i<len;i++){for(int j=i;j>gap-1;j-=gap){if(arr[j] < arr[j-gap]){swap(arr,j,j-gap);}}}}
}