八大排序-插入排序

概要

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

插入排序原理

排序过程

插入排序的核心是循环将数组插入有序序列中，使得数组从小到大最终有序。上图以数组int n[] = { 6, 5, 2, 7, 3, 9, 8 }为例，第一趟排序将6插入仅一个元素的数组序列{ 5 }中，构造出有序序列{ 5, 6 }；第二躺排序将2插入2个元素的数组序列{ 5, 6 }中，继续构造出有序序列{ 2, 5, 6 },如此循环最终整个数组有序。

一趟排序

以第四趟排序说明，一趟排序的详细过程为：当待插入数字比有序数组当前位置数字小时，将有序数组当前数字往后移一位，并将待插入数字插入到数组当前位置，反正如果待插入数字大于或等于有序数组当前位置数字则无需交换，一趟排序结束。将待插入数字3和有序数组{ 2, 5, 6, 7 }进行从后往前对比，第一次3和7对比交换得到{ 2, 5, 6, 3, 7 },第二次3和6对比交换得到{ 2, 5, 3, 6, 7 }，第三次3和5对比交换得到{ 2, 3, 5, 6, 7 }，第四次3和2对比交换得到{ 2, 3, 5, 6, 7 }，因为是有序数组因此无需继续往前对比可以结束对比（事实上也达到了边界）。

编码实践

public class Test {

	public static void main(String[] args) {
		int n[] = { 6, 5, 2, 7, 3, 9, 8 };
		insertSort(n);
		System.out.print("插入排序结果：");
		for (int m : n) {
			System.out.print(m + " ");
		}
	}

	/**
	 * 插入排序
	 * 
	 * @param n 待排序数组
	 */
	public static void insertSort(int n[]) {
		for (int i = 1; i < n.length; i++) {
			int temp = n[i];
			for (int j = i - 1; j >= 0; j--) {
				if (temp < n[j]) {
					n[j + 1] = n[j];
					n[j] = temp;
				} else {
					break;
				}
			}
		}
	}

结果

插入排序结果：2 3 5 6 7 8 9

编码说明

for循环（注意循环次从数组下标1开始，待插入数字初始为第2个数，第一个数构成初始已排序数组）
   1、声明待插入数字；
   2、for循环进行一躺插入排序（从已排序数组的最后一位开始往前对比）；
       2.1、若待插入数字小于已排序数组中当前数字，则将当前数组数字后移一位，并将数组当前数字赋值为待插入数字；
       2.2、若待插入数字大于或等于已排序数组中当前数字，一趟循环结束；

一趟排序的优化

在插入思想不变的情况下，可以减少一躺排序中的循环中的对当前位置的赋值操作，即n[j] = temp。具体如下图所示：

编码实践

	/**
	 * 插入排序
	 * 
	 * @param n 待排序数组
	 */
	public static void insertSort(int n[]) {
		for (int i = 1; i < n.length; i++) {
			int temp = n[i];
			int j = i - 1;
			for (; j >= 0; j--) {
				if (temp < n[j]) {
					n[j + 1] = n[j];
				  //n[j] = temp; 减少循环赋值操作
				} else {
					break;
				}
			}
			//一躺对比结束后，将待插入数字插入最后结束循环位置的后一位
			n[j + 1] = temp;
		}
	}

与优化前对比，主要将插入赋值操作放在一躺排序结束后。

结语

本篇以最简单的图文形式讲解八大排序之一的插入排序的核心思想和具体实现，插入排序对有序数组进行插入的思想在很多算法或是算法优化中都会使用到，是一种十分重要的基础排序算法~

关注订阅号获取更多干货～