希尔排序
简单插入排序存在的问题
我们看简单的插入排序可能存在的问题.
数组 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} 请从小到大排序. 请分别使用
-
希尔排序时， 对有序序列在插入时采用交换法, 并测试排序速度.
-
希尔排序时， 对有序序列在插入时采用移动法, 并测试排序速度
- 代码实现
交换式
java;gutter:true;
package com.xuge.sort;</p>
<p>import java.util.Arrays;</p>
<p>/<strong>
* author: yjx
* Date :2022/5/3015:06
</strong>/
public class ShellSort {
public static void main(String[] args) {
int arr[]={8,9,1,7,2,3,5,4,6,0};
shellSort(arr);</p>
<p>}
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=0;j-=gap){
//如果当前元素大于加上步长后的那个元素，需要交换
if(arr[j]>arr[j+gap]){
temp=arr[j];
arr[j]=arr[j+gap];
arr[j+gap]=temp;
}</p>
<pre><code> }
}
System.out.println("希尔排序第"+(++count)+"轮"+Arrays.toString(arr));
}
/*
//希尔排序第一轮
//将10个数据分成5组10/2
for(int i=5;i=0;j-=5){
//如果当前元素大于加上步长后的那个元素，需要交换
if(arr[j]>arr[j+5]){
temp=arr[j];
arr[j]=arr[j+5];
arr[j+5]=temp;
}
}
}
</code></pre>
<p>//5/2=2
temp=0;
for(int i=2;i=0;j-=2){
//如果当前元素大于加上步长后的那个元素，需要交换
if(arr[j]>arr[j+2]){
temp=arr[j];
arr[j]=arr[j+2];
arr[j+2]=temp;
}</p>
<pre><code> }
}
System.out.println("====希尔排序第二轮"+Arrays.toString(arr));
//2/2=1
for(int i=1;i=0;j-=1){
//如果当前元素大于加上步长后的那个元素，需要交换
if(arr[j]>arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
System.out.println("====希尔排序第三轮"+Arrays.toString(arr));
</code></pre>
<p>*/</p>
<p>}
}</p>
<pre><code>
## 速度测试
;gutter:true;
public static void main(String[] args) {
int arr[]={8,9,1,7,2,3,5,4,6,0};
shellSort(arr);
int arr2[] = new int[80000];
for (int i = 0; i < 80000; i++) {
arr2[i] = (int) (Math.random() * 80000000);//生成随机数[0,80000000);
}
System.out.println("====输出数组=====");
Date data = new Date();
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String str = sdf.format(data);
System.out.println("排序前的时间是:" + str);//24
shellSort(arr2);
Date data2 = new Date();
String str2 = sdf.format(data2);
System.out.println("排序后的时间是" + str2);//34
}
移位式
java;gutter:true;
//移位式
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]=0&&temp
Original: https://www.cnblogs.com/XugeA/p/16328164.html
Author: xugeA
Title: 排序算法-希尔排序
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/605025/
转载文章受原作者版权保护。转载请注明原作者出处！