一、简单插入排序存在的问题
我们看简单的插入排序可能存在的问题.
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论 : 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.
二、希尔排序法介绍
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种 插入排序 ，它是简单插入排序经过改进之后的一个 更高效的版本 ，也称为缩小增量排序。
三、希尔排序法基本思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序：随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
四、希尔排序法的示意图
五、希尔排序法应用实例
有一群小牛，考试成绩分别是{8,9,1,7,2,3,5,4,6,0}请从小到大排序，请分别使用
（1）希尔排序时，对有序序列在插入时采用交换法，并测试排序速度。
（2）希尔排序时，对有序序列在插入时采用移动法，并测试排序速度。
代码实现
public class ShellSort {
public static void main(String[] args) {
int[] arr = {8,9,1,7,2,3,5,4,6,0};
// shellSort(arr);
shellSort2(arr);
}
public static void shellSort(int[] 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组，每组有）
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(Arrays.toString(arr));
}
//对交换式的希尔排序进行优化->移位法
public static void shellSort2(int[] arr){
//增量gap,并逐步的缩小增量
for(int gap=arr.length/2;gap>0;gap/=2){
//从第gap个元素，逐个对其所在的组进行直接插入排序
for(int i=gap;i<arr.length;i++){
int j=i;
int temp=arr[j];
if(arr[j]<arr[j-gap]){
while(j-gap >=0 && temp < arr[j-gap]){
//移动
arr[j]=arr[j-gap];
j-=gap;
}
//当退出while后，就给temp找到插入的位置
arr[j]=temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}
全部代码
public class BubbleSort2{
public static void main(String[] args) {
// int arr[] = {3, 9, -1, 10, 20};
//
// System.out.println("排序前");
// System.out.println(Arrays.toString(arr));
//为了容量理解，我们把冒泡排序的演变过程，给大家展示
//测试一下冒泡排序的速度O(n^2), 给80000个数据，测试
//创建要给80000个的随机的数组
int[] arr = new int[80000];
for(int i =0; i < 80000;i++) {
arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数
}
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是=" + date1Str);
//测试冒泡排序
bubbleSort(arr);
Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序后的时间是=" + date2Str);
//System.out.println("排序后");
//System.out.println(Arrays.toString(arr));
/*
// 第二趟排序，就是将第二大的数排在倒数第二位
for (int j = 0; j < arr.length - 1 - 1 ; j++) {
// 如果前面的数比后面的数大，则交换
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第二趟排序后的数组");
System.out.println(Arrays.toString(arr));
// 第三趟排序，就是将第三大的数排在倒数第三位
for (int j = 0; j < arr.length - 1 - 2; j++) {
// 如果前面的数比后面的数大，则交换
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第三趟排序后的数组");
System.out.println(Arrays.toString(arr));
// 第四趟排序，就是将第4大的数排在倒数第4位
for (int j = 0; j < arr.length - 1 - 3; j++) {
// 如果前面的数比后面的数大，则交换
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第四趟排序后的数组");
System.out.println(Arrays.toString(arr)); */
}
// 将前面额冒泡排序算法，封装成一个方法
public static void bubbleSort(int[] arr) {
// 冒泡排序 的时间复杂度 O(n^2), 自己写出
int temp = 0; // 临时变量
boolean flag = false; // 标识变量，表示是否进行过交换
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
// 如果前面的数比后面的数大，则交换
if (arr[j] > arr[j + 1]) {
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
//System.out.println("第" + (i + 1) + "趟排序后的数组");
//System.out.println(Arrays.toString(arr));
if (!flag) { // 在一趟排序中，一次交换都没有发生过
break;
} else {
flag = false; // 重置flag!!!, 进行下次判断
}
}
}
}
