基本排序之插入排序（直接插入排序、Shell、折半）

一、直接插入排序

直接插入排序大概是我们最容易理解的一类排序了。

1、原理

对于n个元素的记录。

第一趟　　：　　把第2个元素拿出来跟第1个元素对比，小的在前面、大的在后面。

第二趟　　：　　把第3个元素拿出来插入到前2个元素中，使他们有序。

第三趟　　：　　把第4个元素拿出来插入到前3个元素中，使他们有序。

…

第n-1趟　：　　把第n个元素拿出来插入到前n-1个元素中，排序完成。
　　2、时间复杂度和稳定性
　　直接插入排序的时间复杂度是O(N2)。
　　假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1！因此，直接插入排序的时间复杂度是O(N2)。
　　直接插入排序是稳定的算法，它满足稳定算法的定义。
　　3、结果示例
　　
　二、折半插入排序

1、原理

折半插入排序是对直接插入排序的改进。

我们看直接插入排序的步骤简单而言其实就2步，第1步是从已经排好序的数组中找到该插入的点，第2步是将数据插入，然后后面的数据整体后移。那么直接插入排序是如何找到该插入的点的呢？是无脑式的从头到尾的遍历。问题是被插入的数组是排好序的，根本没有必要从头到尾遍历。折半插入排序就是改进了第1步——从已经排好序的数组中找到该插入的点。

折半插入排序是怎么做的呢？非常简单。取已经排好序的数组的中间元素，与插入的数据进行比较，如果比插入的数据大，那么插入的数据肯定属于前半部分，否则属于后半部分。这样，不断遍历缩小范围，很快就能确定需要插入的位置。这就是所谓“折半”。
　2、时间复杂度和稳定性
　　折半插入排序的时间复杂度是O(N2)。
　　折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。
　　折半插入排序是稳定的算法，它满足稳定算法的定义。
　3、结果示例
　
　三、Shell排序

1、原理

Shell排序也是对直接插入排序的改进。它实质上是一种分组插入方法。可以这么简单理解：

对于n个元素的数组，假设增量为 h：

第一趟　　：　　从第1个元素开始，每隔h取一个元素，那么最后可以得到n/h个元素，一边取，一边通过直接插入将这h个元素排序

第二趟　　：　　从第2个元素开始，每隔h取一个元素，跟第一趟一样。

…

第h趟　　 ：　　从第h个元素开始，每隔h取一个元素，跟第一趟一样。

（此时，整个数组还不是有序的）

然后，减少h的值，重复上面的操作，直到h减小为1，排序完成。
　　2、时间复杂度和稳定性
　　Shell排序的时间复杂度是根据增量h的不同而不同，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(N²)。Shell排序的时间复杂度在O(n3/2)-O(n7/6)之间。
　　Shell排序算法是一种不稳定的排序算法。
　　3、结果示例

四、常用排序算法的复杂度

/**

• ————————如果觉得本博文还行，别忘了推荐一下哦，谢谢！
• 作者：钱书康
• 欢迎转载，请保留此段声明。
• 出处：http://www.cnblogs.com/zrtqsk/
  */