Java排序算法总结之（一）——插入排序（直接插入排序、折半插入排序、希尔排序）

排序方法可以分为两种：内部排序 和 外部排序

内部排序的方法很多，常用的大致可以分为：

1. 插入排序（直接插入排序、折半插入排序、希尔排序）
2. 交换排序（冒泡排序、快速排序）
3. 选择排序（简单选择排序、堆排序）
4. 归并排序
5. 基数排序

评价排序算法的优劣一般从三个角度分析：

• 空间复杂度：存储器使用量
• 时间复杂度：最差、最好和平均时间复杂度
• 稳定性。当序列中出现相等的数据时，经过排序后，前后顺序位置不变。

插入排序（Insertion Sort）

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

插入排序有很多种实现方式：

1 直接插入排序

基本操作：将一个数据插入到已排好序的有序表中，从而得到一个新的、长度加 1 的有序表，直接插入的步长为 1，即待插入的数据为当前有序表的下一数据。

图例：

         

代码：

package com.yanshx.sort;

public class InsertSort {
//直接插入排序
public static int[] insertSort(int[] s){

for (int i = 1; i < s.length; i++) {//i = 0一个数据可以看成一个有序表，故从i = 1开始
int j = i;
while (j > 0 && s[j] < s[j - 1]) {//将每一位向后移动一位，直到将s[i]插入到合适的位置上
int temp = s[j];
s[j] = s[j - 1];
s[j - 1] = temp;
j -= 1;//从后向前扫描
}
}
return s;
}

}
}

效率分析：

空间：只需要一个记录的辅助空间，空间复杂度O(1)。

时间：排序的基本操作为：比较两个数据的大小和移动记录。当待排序列按正序（即我们想要的顺序）排列时，进行的比较比较次数为最小值 n - 1 次，移动 0 次；而当序列为逆序时，比较次数达到最大值 n(n-1)/2，移动 n(n-1)/2 次。若序列为随机的，则待排序序列各种排列的概率相同，可取最小值与最大值的平均，时间复杂度为O(n^2)。

稳定性：true.当两者大小相等时，不进行交换，故前后顺序不变，稳定。

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找插入排序（又叫折半插入排序法）。

2 折半插入排序法

基本概念：是直接插入排序的一种改进。因为待插入元素前的序列为有序序列，折半查找的方法来加快寻找插入点的速度。

代码：

public static int[] binInsertSort(int[] s) {
<span style="white-space:pre"></span>for (int i = 1; i < s.length; i++) {
<span style="white-space:pre"></span>if (s[i] < s[i - 1]) {
<span style="white-space:pre"></span>int mid;// 记录折半后的中间值
<span style="white-space:pre"></span>int start = 0, end = i - 1;
<span style="white-space:pre"></span>int temp = s[i];// 寄存当前需要插入的值
<span style="white-space:pre"></span>while (start <= end) {// 跳出时，start的位置就是要插入的位置（start = end + 1）
<span style="white-space:pre"></span>mid = start + (end - start) / 2;
<span style="white-space:pre"></span>if (temp < s[mid]) {// 待插入的值小于中间值，则插入点在低半区
<span style="white-space:pre"></span>end = mid - 1;
<span style="white-space:pre"></span>}else { // <span style="font-family: Arial, Helvetica, sans-serif;">待插入的值大于中间值，则插入点在高半区</span>
<span style="white-space:pre"></span>start = mid + 1;
<span style="white-space:pre"></span>}
<span style="white-space:pre"></span>}
<span style="white-space:pre"></span>for (int j = i; j > start; j--) {
<span style="white-space:pre"></span>s[j] = s[j - 1];
<span style="white-space:pre"></span>}
<span style="white-space:pre"></span>s[start] = temp;
<span style="white-space:pre"></span>}
<span style="white-space:pre"></span>}
<span style="white-space:pre"></span>return s;
<span style="white-space:pre"></span>}

效率分析：
复杂度：时间与空间复杂度和直接插入排序算法一样

稳定性：true.

3 希尔排序

基本概念：希尔排序又称“缩小增量排序”，先将整个待排序序列分割成若干子序列分别进行插入排序，分割规则为设定一个步长delta，每次比较 i, i + delta, i + 2*delta...序列，进行插入排序，然后缩短步长delta（一般取当前值的一半），直到delta = 1，对全体进行一次直接插入排序。

希尔排序示例：左图摘自严蔚敏等编著的数据结构一书，右图为算法的动态展示。

代码：

package com.yanshx.sort;

public class InsertSort {

//希尔排序
public static int[] shellSort(int[] s){
int delta = s.length;
while (true) {
delta = delta / 2;//步长选择
for (int i = delta; i < s.length; i++) {
int k = i;
while (k > delta - 1 && s[k] < s[k - delta]) {
int temp = s[k];
s[k] = s[k - delta];
s[k - delta] = temp;
k -= delta;
}
}
if (delta == 1) {//步长为1时，排序一遍后即退出
break;
}
}

return s;
}
}

效率分析：

空间：O(1)

时间：步长选择是希尔排序的重要部分，不同步长下对应的最坏情况复杂度是不同的。

步长序列	最坏情况下复杂度

稳定性：false.大步长的情况下可能会影响相等数据的相对顺序。

参考文献：

1. 插入排序-Wikipedia
2. 排序算法-Wikipedia
3. [97严] 严蔚敏，吴伟民，《数据结构C语言版》，清华大学出版社，1997年4月

步长序列	最坏情况下复杂度