Insert sort 插入排序
插入排序
直接插入排序应该算法思想简单程度仅次于冒泡排序的简单算法了。 但是想要一次性写对也是有一定的难度的。下面就记录下一些需要注意的地方：
public static void InsertSort(List<Integer> list) {
for (int i = 1; i < list.size(); i++) {
if (less(list, i, i - 1)) {
int j;
int temp = list.get(i);
for (j = i - 1; j >=0 && list.get(j) > temp; j--) {
list.set(j + 1, list.get(j));
}
list.set(j + 1, temp);
}
}
}其中的辅助函数less()见这里
看起来很简单，但是还是有一些需要注意的地方。
- 在内层循环中的条件判断中，一定要确保j不能为负。
- 在内层循环结束后，将temp赋值给第j＋1个位置，而不是j， 因为在内层循环中每次都是把j＋1这个位置空了出来。所以temp要赋值给j+1。
- 外循环的i一定要在temp中暂存，因为内循环的向后移动第一次就会覆盖掉i所在的值。
- 还有需要注意的就是外层循环是从第二个元素开始的，因为第一个元素自身是有序的。
在《算法》这本书里，插入排序用的实现细节不是很一样，下面看代码：
public static void InsertSortV1(int[] a) {
int N = a.length;
for (int i = 1; i < N; i++) {
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}
}
}辅助函数如下：
public static boolean less(int i, int j) {
return i < j;
}
public static void exch(int[] c, int i, int j) {
int temp = c[i];
c[i] = c[j];
c[j] = temp;
}与原始的插入排序相比，V1版本的插入排序要简洁的多，看上去也更加优雅。
那么问题来了，为什么V1版本的要优雅的多呢？首先显而易见的是，
V1版本的内层循环是从i开始，而不是从i－1开始，这样的好处就是，
它可以不用设置temp哨兵，每次都是简单的前后交换。不存在一个覆盖的过程，
所以也就不需要temp来保存值。而且这样的交换还可以利用辅助函数exch，
而不像原始版本那样，交换过程还得手动完成。
插入排序有个特别适用的场景，就是当数组部分有序时，它会特别的快。 倒置指的是数组中的两个顺序颠倒的元素。如果数组中倒置的数量小于数组的大小的某个倍数， 那么我们就说这个数组是部分有序的。下面是几种典型的部分有序数组：
- 数组中每个元素距离它的最终位置都不远；
- 一个有序的大数组接一个小数组；
- 数组中只有几个元素的位置不正确
插入排序对以上情况会进行的非常快。
希尔排序
希尔排序是插入排序的升级版，其思想与插入排序是一样的， 不同的是它比较的不仅仅是前后相邻的，而是从一个很大的跨度上渐渐缩小。
public static void ShellSort(List<Integer> list) {
int n = list.size() / 3;
while (n >= 1) {
for (int i = n; i < list.size(); i++) {
if (less(list, i, i - n)) {
for (int j = i; j >=n && less(list, j, j-n); j -= n) {
exchange(list, j, j-n);
}
}
}
n = n/3;
}
}希尔排序需要注意的内层循环，循环遍历j的自减不再是以1为单位，而是以步长n为单位，
并且在比较大小时也不是比较前后两位，而是步长单位的前后两位，所以less的参数也是减步长n。
希尔排序的外层循环也不是从0开始，而是从步长开始，因为它是从后往前模拟插入排序，
往前的逻辑是在内层循环中完成的，外层只是控制起始位置，与插入排序类似。
blog comments powered by Disqus