网上代码很多的,找个易理解的学习。
基本思想:希尔排序把n个元素按一定的间隔分成几组,然后按组为单位进行插入排序。 。
将待排记录序列以一定的增量间隔h 分割成多个子序列,对每个子序列分别进行一趟直接插入排序, 然后逐步减小分组的步长h ,对于每一个步长h 下的各个子序列进行同样方法的排序,直到步长为1 时再进行一次整体插入排序。
因为不管记录序列多么庞大,关键字多么混乱,在先前较大的分组步长h下每个子序列的规模都不大,用直接插入排序效率都较高。 尽管在随后的步长h递减分组中子序列越来越大,但由于整个序列的有序性也越来越明显,则排序效率依然较高。这种改进抓住了直接插入排序的两点本质,大大提高了它的时间效率。
希尔算法的本质是缩小增量排序,是对直接插入排序算法的改进。
程序的增量序列常采用的表达式:
(1)h=3*h+1。(h=1,4,13,40,121,364...)
(2)h=2^k-1。(h=1,3,7,15,31,63...
例:待排序列:5,9,1,4,8,2,6,3,7
代码:
import java.util.Arrays;
public class SortTest{
// 交换数组中的两个元素的位置
private void swap(int[] array, int i, int j) {
if (i != j) {//只有不是同一位置时才需交换
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
/**
* 数组元素后移一位
* @param array 待移动的数组
* @param startIndex 从哪个开始移
* @param endIndex 到哪个元素止
*/
private void move(int[] array, int startIndex, int endIndex) {
for (int i = endIndex; i >= startIndex; i--) {
array[i + 1] = array[i];
}
}
/**
* 以指定的步长将数组元素后移,步长指定每个元素间的间隔
* @param array 待排序数组
* @param startIndex 从哪里开始移
* @param endIndex 到哪个元素止
* @param step 步长
*/
private void move(int[] array, int startIndex, int endIndex, int step) {
for (int i = endIndex; i >= startIndex; i -= step) {
array[i + step] = array[i];
}
}
/**
* 希尔排序算法的实现,对数组中指定的元素进行排序
* @param array 待排序的数组
*/
public void shelltSort(int[] array) {
//初始步长,实质为每轮的分组数
int step = initStep(array.length);
//第一层循环是对排序轮次进行循环。(step + 1) / 2 - 1 为下一轮步长值
for (; step >= 1; step = (step + 1) / 2 - 1) {
//对每轮里的每个分组进行循环
for (int groupIndex = 0; groupIndex < step; groupIndex++) {
//对每组进行直接插入排序
insertSort(array, groupIndex, step);
}
}
}
/**
* 直接插入排序实现
* @param array 待排序数组
* @param groupIndex 对每轮的哪一组进行排序
* @param step 步长
*/
private void insertSort(int[] array, int groupIndex, int step) {
int startIndex = groupIndex;//从哪里开始排序
int endIndex = startIndex;//排到哪里
/*
* 排到哪里需要计算得到,从开始排序元素开始,以step步长,可求得下元素是否在数组范围内,
* 如果在数组范围内,则继续循环,直到索引超现数组范围
*/
while ((endIndex + step) <= array.length-1) {
endIndex += step;
}
// i为每小组里的第二个元素开始
for (int i = groupIndex + step; i <= endIndex; i += step) {
for (int j = groupIndex; j < i; j += step) {
int insertedElem = array[i];
//从有序数组中最一个元素开始查找第一个大于待插入的元素
if (array[j]>insertedElem) {
//找到插入点后,从插入点开始向后所有元素后移step位
move(array, j, i - step, step);
array[j] = insertedElem;
break;
}
}
}
}
private static int initStep(int len) { //从最小步长1推导出最长初始步长值
/*
* 初始值设置为步长公式中的最小步长,从最小步长推导出最长初始步长值,即按照以下公式来推:
* 1,3,7,15,...,2^(k-1)-1,2^k-1
* 如果数组长度小于等于4时,步长为1,即长度小于等于4的数组不且分组,此时直接退化为直接插
* 入排序
*/
int step = 1;
//试探下一个步长是否满足条件,如果满足条件,则步长置为下一步长
while ((step + 1) * 2 - 1 < len - 1) {
step = (step + 1) * 2 - 1;
}
System.out.println("初始步长 : " + step);
return step;
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
int[] intArr = { 5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7 };
System.out.println("源 : " + Arrays.toString(intArr));
SortTest test=new SortTest();
//test.insertSort(intArr);
test.shelltSort(intArr);
System.out.println("升 : " + Arrays.toString(intArr));
}
}
源码下载:
- 大小: 60.6 KB
分享到:
相关推荐
下面是一个简单的希尔排序Java代码实现: ```java public class ShellSort { public static void shellSort(int[] arr) { int len = arr.length; // 定义增量序列,例如初始增量为len/2 int gap = len / 2; ...
希尔排序
在Java中,希尔排序可以通过定义一个希尔排序方法,接收一个整型数组作为参数,然后根据上述步骤实现排序。具体代码如下(使用Sedgewick增量序列): ```java public class ShellSort { public static void shell...
按下标的一定增量分组,对每组使用直接插入算法排序;随着增量 * 逐渐减少,每组包含的关键字越来越多,当增量减至1时,整个文件恰 * 好被分成一组,算法便终止。 * 8,9,1,7,2,3,5,4,6,0 * //初始增量 gap=...
希尔排序:分别使用Java和Python实现希尔排序算法 希尔排序:分别使用Java和Python实现希尔排序算法 希尔排序:分别使用Java和Python实现希尔排序算法 希尔排序:分别使用Java和Python实现希尔排序算法 希尔排序:...
在Java中实现希尔排序,我们可以定义一个希尔排序的函数,接受一个整型数组作为参数,然后按照上述步骤进行排序。代码如下: ```java public class ShellSort { public static void sort(int[] arr) { int len = ...
在`AlgorithmShellSort.java`这个文件中,我们可以预期看到希尔排序的具体实现。通常,Java代码会包含一个名为`shellSort()`的函数,它接收一个整数数组作为参数,并对其进行希尔排序。以下是希尔排序的基本步骤: ...
希尔排序代码,其中是希尔排序的代码部分,又不知道的可以进来看一下
该资源提供了一份全面的指南,介绍了如何在Java中实现希尔排序。文档中涵盖了希尔排序的基本概念,包括如何对数组进行排序以及如何在Java中实现希尔排序。此外,文档还包括一个逐步指南,介绍如何在Java中实现希尔...
希尔排序 希尔排序.java 使用Java实现
5. 实现方式:希尔排序可以使用各种编程语言实现,如C、C++、Java等。在C语言中,可以通过编写函数来实现希尔排序,主要涉及到数组的操作和循环控制。 6. 应用场景:希尔排序适用于需要快速排序但对稳定性要求不高...
以下是一个简单的希尔排序Java实现的详细分析: ```java public static void shellSort(int[] intArray) { // 输出原始数组 System.out.print("将要排序的数组为: "); for (int k = 0; k ; k++) System.out....
文章还提供了一个简单的Java实现代码示例,演示了希尔排序的具体执行过程。 适合人群:具备基础编程能力的开发人员、算法爱好者。 使用场景及目标:适合于需要对大量数据进行排序的场景,特别是在内存空间受限的情况...
希尔排序算法详解与 Java 代码实现 希尔排序是一种改进的插入排序算法,也被称为缩小增量排序。它通过将待排序的数据按照一定的增量分组,对每个分组进行插入排序,然后逐渐缩小增量,再次对分组进行插入排序,直至...
希尔排序是插入排序的一种优化版本,通过设定一个增量序列,将待排序的数组按照增量分成多个子序列,对每个子序列进行插入排序,最后减小增量,直至为1,整个数组有序。这种方法减少了元素移动的次数,提高了排序...
希尔排序的Java实现方法ShellSort,简单易懂,适合算法初学者。
`ShellSort.java` 文件可能是实现希尔排序的Java代码示例。在该文件中,可以看到以下关键部分: - 定义间隔序列:这通常通过定义一个方法来实现,根据所选的序列生成一系列间隔。 - 插入排序:希尔排序的核心是插入...
在Java中实现希尔排序,你需要创建一个希尔排序的函数,接受一个整数数组作为参数。函数内部可以定义一个增量序列,然后用for循环控制间隔的减小,每次间隔变化时,遍历整个数组,根据当前间隔将每个元素看作子序列...
在 Java 中,希尔排序可以使用以下代码实现: ```java public class Shell { public static void shellSort(int[] arr) { int n = arr.length; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; ...