插入排序基本思路
思想概念
举例说明
假设有一个数组，int[] arr = {2, 7, -1, 10, 19};
1、 第一轮假如2为一个有序表，7，-1,10,19为无序表，从无序表中抽出元素7与2进行比较，将2,7组成有序列表；
2、 第二轮2,7为一个有序列表，-1,10,19为无序列表，从无序列表中抽出-1插入有序列表中的适当位置，有序列表变为-1,2,7；
3、 第三轮-1,2,7为一个有序列表，10,19为无序列表操作步骤同上，第四论也一样，直到无序列表中的元素为空为止；
代码思路
//第1轮
int insertVal = arr[1];//无序列表第一个元素
int insertIndex =1-1; //有序列表的最大角标
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
//遍历有序列表,如果发现小与有序列表的元素，就让这个元素前进一位
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
arr[insertIndex + 1] = insertVal;//insertIndex+1是因为比较最后一个符合条件的元素多减去1
System.out.println("第1轮插入");
System.out.println(Arrays.toString(arr));
//第2轮
insertVal = arr[2];
insertIndex = 2 - 1;
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
arr[insertIndex + 1] = insertVal;
System.out.println(Arrays.toString(arr));
//第3轮
insertVal = arr[3];
insertIndex = 3 - 1;
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
arr[insertIndex + 1] = insertVal;
System.out.println(Arrays.toString(arr));
//第4轮
insertVal = arr[4];
insertIndex = 4 - 1;
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
arr[insertIndex + 1] = insertVal;
System.out.println(Arrays.toString(arr));
最终代码
int[] arr = {
2, 7, -1, 10, 19};
for (int i = 1; i < arr.length; i++) {
//第1轮
int insertVal = arr[i];//无序列表第一个元素
int insertIndex =i-1; //有序列表的最大角标
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
//遍历有序列表,如果发现小与有序列表的元素，就让这个元素前进一位
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
arr[insertIndex + 1] = insertVal;//insertIndex+1是因为比较最后一个符合条件的元素多减去1
System.out.println(Arrays.toString(arr));
}
插入排序的缺点
希尔排序（插入排序的优化）
希尔排序的思想
希尔排序是按照下标进行分组，对每组进行希尔排序，随着分组逐渐的减少，每组的关键词原来越多，直到分组为1的时候终止
希尔排序示意图
希尔排序代码思路
int[] arr = {
8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
int temp;
// 希尔排序的第1轮排序
//因为第1轮排序，是将10个数据分成了 5组
for (int i = 5; i < arr.length; i++) {
// 遍历各组中所有的元素(共5组，每组有2个元素), 步长5
for (int j = i - 5; j >= 0; j -= 5) {
// 如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + 5]) {
temp = arr[j];
arr[j] = arr[j + 5];
arr[j + 5] = temp;
}
}
}
System.out.println("希尔排序1轮后=" + Arrays.toString(arr));//
// 希尔排序的第2轮排序
// 因为第2轮排序，是将10个数据分成了 5/2 = 2组
for (int i = 2; i < arr.length; i++) {
// 遍历各组中所有的元素(共5组，每组有2个元素), 步长5
for (int j = i - 2; j >= 0; j -= 2) {
// 如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + 2]) {
temp = arr[j];
arr[j] = arr[j + 2];
arr[j + 2] = temp;
}
}
}
System.out.println("希尔排序2轮后=" + Arrays.toString(arr));//
// 希尔排序的第3轮排序
// 因为第3轮排序，是将10个数据分成了 2/2 = 1组
for (int i = 1; i < arr.length; i++) {
// 遍历各组中所有的元素(共5组，每组有2个元素), 步长5
for (int j = i - 1; j >= 0; j -= 1) {
// 如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.println("希尔排序3轮后=" + Arrays.toString(arr));
最终版本
int temp = 0;
int count = 0;
// 根据前面的逐步分析，使用循环处理
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
// 遍历各组中所有的元素(共gap组，每组有个元素), 步长gap
for (int j = i - gap; j >= 0; j -= gap) {
// 如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
System.out.println("希尔排序第" + (++count) + "轮 =" + Arrays.toString(arr));
}
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: