算法3 七大排序之：直接插入排序和希尔排序

上一篇总结了直接选择排序和堆排序，这一篇要总结的是插入排序中的直接插入排序和希尔排序，我们主要从以下几点进行总结。

1、直接插入排序及算法实现

2、希尔排序及算法实现

3、直接插入排序PK希尔排序

1、直接插入排序及算法实现

什么是直接插入排序呢？直接插入排序的基本思想是：每次从无序序列中取出第一个元素插入到已经排好序的有序序列中，从而得到一个新的，数量加1的有序序列。

1-1、示意图

下面是直接插入排序的图解说明。

1-2、代码

下面是直接插入排序的算法实现代码。

InsertSort.Java

public class InsertSort { public static void main(String[] args) { int[] list = {90, 10, 20, 50, 70, 40, 80, 60, 30, 52}; System.out.println("************直接插入排序************"); System.out.println("排序前："); display(list); System.out.println(""); System.out.println("排序后："); insertSort(list); display(list); } /** * 直接插入排序算法 */ public static void insertSort(int[] list) { // 从无序序列中取出第一个元素 (注意无序序列是从第二个元素开始的) for (int i = 1; i < list.length; i++) { int temp = list[i]; int j; // 遍历有序序列 // 如果有序序列中的元素比临时元素大，则将有序序列中比临时元素大的元素依次后移 for (j = i - 1; j >= 0 && list[j] > temp; j--) { list[j + 1] = list[j]; } // 将临时元素插入到腾出的位置中 list[j + 1] = temp; } } /** * 遍历打印 */ public static void display(int[] list) { System.out.println("********展示开始********"); if (list != null && list.length > 0) { for (int num : list) { System.out.print(num + " "); } System.out.println(""); } System.out.println("********展示结束********"); } } 

测试结果：

2、希尔排序及算法实现

希尔排序是直接插入排序的一种更高效的改进版本，又称为“缩小增量排序”。

2-1、示意图

2-2、代码

ShellSort.java 

public class ShellSort { public static void main(String[] args) { int[] list = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}; System.out.println("************希尔排序************"); System.out.println("排序前："); display(list); System.out.println(""); System.out.println("排序后："); shellSort(list); display(list); } /** * 希尔排序算法 */ public static void shellSort(int[] list) { // 取增量 int gap = list.length / 2; while (gap >= 1) { // 无序序列 for (int i = gap; i < list.length; i++) { int temp = list[i]; int j; // 有序序列 for (j = i - gap; j >= 0 && list[j] > temp; j = j - gap) { list[j + gap] = list[j]; } list[j + gap] = temp; } // 缩小增量 gap = gap / 2; } } /** * 遍历打印 */ public static void display(int[] list) { System.out.println("********展示开始********"); if (list != null && list.length > 0) { for (int num : list) { System.out.print(num + " "); } System.out.println(""); } System.out.println("********展示结束********"); } } 

测试结果：

3、直接插入排序PK希尔排序

既然希尔排序是直接插入排序的改进版，我们就来测试一下希尔排序是否真的比直接插入排序更快？ 

代码：

InsertSortPkShellSort.java