一、排序思想把n个待排的元素看成一个有序表和一个无序表，开始时，有序表只包含1个元素，无序表中有n - 1个元素。排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码比较，将它插入适当的位置，使之成为新的有序表。 1. 案例： 假如现有待排序列如下(带 * 号的是有序表元素)： 17* 3 25 14 20 9
那么开始的时候，17就是有序表，剩余元素是一个无序表。 - 第一次：让3和有序表最后一个元素17比较，发现3比17小，那么就让17往后挪一位，然后让3再和前面的比较，发现前面没有元素了，所以第一次排序后的结果是：
3* 17* 25 14 20 9
- 第二次：让25和17比较，发现25比17大，那么就不用变换位置，第二次排序后的结果是：
3* 17* 25* 14 20 9
3* 14* 17* 25* 20 9
3* 14* 17* 20* 25* 9
3* 9* 14* 17* 20* 25*
二、代码实现代码中有详细的注释： public static void sort(int[] arr) {
if (arr == null || arr.length == 1) {
return;
}
for(int i=1; i<arr.length; i++) { // 默认第一个是有序表，从第二个元素开始进行插入排序
int insertVal = arr[i]; // 待排元素
int insertIndex = i - 1; // 从有序表最后一个元素开始比较
while (insertIndex >= 0 && insertVal < arr[insertIndex]) { // 如果还没有将有序表比较完 && 待排元素还没找到位置
arr[insertIndex + 1] = arr[insertIndex]; // 比待排元素大的元素后移一位
insertIndex --; // 继续往前比较
}
// 找到位置后，其他元素都后移了，自己占坑
if (insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
}
}
三、存在的问题假如现在有如下序列： 16, 23, 12, 8, 1
要求按照从小到大的顺序排列，你会发现，最小的1在最后面，第二小的8在倒数第二个位置，那么在排序的时候，就会发生很多次交换，即while循环里面的代码会执行很多次，1在排序的时候就会执行四次，这样性能就下降了。有没有优化的空间呢？有，那就是希尔排序……敬请期待
|
