十大经典排序之：插入排序 ｜希尔排序
- 插入排序
- 插入排序原理
- 算法实现
- 例题
- 希尔排序（壳排序）
- 希尔排序原理
- 算法实现
- 例题
插入排序
插入排序原理
插入排序(InsertionSort)，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。
排序的基本方法是：每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。
算法实现
1、算法描述
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
2、图示
3、算法空间复杂度和时间复杂度
空间复杂度：
- 最坏：o（ n 2 n^{2 } n2）
- 最好：o（ n n^{} n）
- 平均：o（ n 2 n^{2 } n2）
时间复杂度（辅助存储）：o（1）
稳定性：稳定
例题
用插入排序将以下数列按照从小到大的顺序输出：123,45,6,22,99,1,38,41,-6,0
java代码：
public class Test {
static void insertSort(int[] arr) {
int i, j, temp;
for (i = 1; i < arr.length; i++) {
temp = arr[i];
for (j = i; j > 0 && arr[j-1] > temp; j--)
arr[j] = arr[j - 1];
arr[j] = temp;
}
}
public static void main(String[] args) {
int[] arr=new int[]{123,45,6,22,99,1,38,41,-6,0};
//插入排序
insertSort(arr);
System.out.println("插入排序后的结果是:");
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+"\t");
}
}
希尔排序（壳排序）
希尔排序原理
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序，也称递减增量排序算法，它是为了解决插入排序在一些情况下的缺点，例如500长度的数组，前200的都比第201的一个大，这个时候第201的数需要跟前面200个数都比较一下，就非常的影响性能。我们就要想办法尽可能早点让小的值靠前，让大的值靠后，这样就能避免上述情况了，这就是希尔排序要解决的问题。
算法实现
1、算法描述
shell排序的思想是根据步长由长到短分组，进行排序，直到步长为1为止，属于插入排序的一种。
shell排序是对插入排序的一个改装,它每次排序把序列的元素按照某个增量分成几个子序列,对这几个子序列进行插入排序,然后不断的缩小增量扩大每个子序列的元素数量,直到增量为一的时候子序列就和原先的待排列序列一样了,此时只需要做少量的比较和移动就可以完成对序列的排序了。
该方法实质上是一种分组插入方法。
2、图示
3、算法空间复杂度和时间复杂度
空间复杂度：
- 最坏：o（ n 2 n^{2} n2）
- 最好：o（ n n n）
- 平均：o（ n 1.3 n^{1.3} n1.3）
时间复杂度（辅助存储）：o（
1
1
1）
稳定性：不稳定
例题
用希尔排序将以下数列按照从小到大的顺序输出：
66,13,51,76,81,26,57,69,23
java代码：
import java.util.Arrays;
public class Test {
public static void shellSort(int[] arr){
// 获取初始的间隔长度 increment = increment/2,不断地缩小间隔的大小，进行分组插入排序
for (int interval = arr.length/2; interval > 0;interval = interval/2){
//不断地缩小间隔的大小，进行分组插入排序
//希尔增量是希尔排序中希尔给出的增量序列ht = N / 2, h[k+1] = h[k] / 2，即{N/2, (N / 2)/2, ..., 1}
for (int i = interval; i < arr.length; i++) {
//按增量进行简单插入排序
int current = arr[i];
int preId = i - interval;
while (preId > -1 && arr[preId] > current){
arr[preId + interval] = arr[preId];
preId -= interval;
}
arr[preId + interval] = current;
}
System.out.println("希尔增量为" + interval + "，排序结果为：" + Arrays.toString(arr));
}
}
public static void main(String[] args) {
int[] arr=new int[]{66,13,51,76,81,26,57,69,23};
//希尔排序
shellSort(arr);
System.out.println("希尔排序后的结果是:");
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+"\t");
}
}