排序(三)：插入排序法

81 阅读 0 评论 54 点赞

我是靠谱客的博主阔达母鸡，最近开发中收集的这篇文章主要介绍排序(三)：插入排序法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一. 基本思想
插入排序从左到右进行，每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左部数组依然有序。
第 j 元素是通过不断向左比较并交换来实现插入过程：当第 j 元素小于第 j - 1 元素，就将它们的位置交换，然后令 j 指针向左移动一个位置，不断进行以上操作。

二. 代码实现

版本一

/**
- <br>插入排序</br>
- 对比选择排序 com.hong.sort.SelectionSort
- 插入排序可以提前终止比较，而选择排序为了每次在剩下的元素中找到最小值，
- 不得不把当前元素与剩下未排序的元素挨个比较，没有提前终止的机会，
- 所以理论上插入排序的效率要高于选择排序。
*/
public class InsertionSort {
public static void sort(int[] arr) {
int n = arr.length;
/**
* 这里的i从1开始，因为插入排序的思想是把当前元素依次和它前面
* 已排好序的元素做比较,第0个元素前面没有元素，所以直接从第1个开始。
*/
for (int i = 1; i < n; i++) {
// 寻找arr[i]合适的插入位置
/*for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
swap(arr,j,j-1);
}*/
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
} else {
/**
* 因为插入排序当前元素前面的元素都是排好序的，
* 所以一旦发现当前元素>当前元素的前一个元素，就可以直接停止比较，继续下一个
*/
break;
}
}
}
}
private static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
/**
* 对arr[l...r]的区间使用InsertionSort排序
* @param arr
* @param l
* @param r
*/
public static void sort(int[] arr, int l, int r) {
for (int i = l + 1; i <= r; i++) {
int e = arr[i];
int j = i;
for (; j > l && arr[j - 1] > e; j--) {
arr[j] = arr[j - 1];
}
arr[j] = e;
}
}

版本二

/**
* <br>插入排序改进</br>
*/
public class InsertionSort2 {
/**
* 改进策略:
* 在之前的排序中,我们每次从第i个元素开始,向后递减,依次遍历相邻的两个元素大小,符合条件就交换位置,这样一轮比较后arr[i]就放到了合适的位置.
* 现在在每轮比较前,先将arr[i]的值拷贝一份出来,然后将这个拷贝的值temp依次与它前面的元素x比较，若temp < x，则直接将x覆盖x的后一个位置的元素，
* 直到找到temp >= y,停止循环比较，并将temp直接覆盖y的后一个位置的元素。
*
* @param arr
*/
public static void sort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int temp = arr[i];
int j = i;
for (; j > 0 && temp < arr[j - 1]; j--) {
arr[j] = arr[j - 1];
}
// 经过上面的遍历比较后,j已经是arr[i]的正确插入位置了,直接替换这个位置下标对应的值
arr[j] = temp;
}
}
}