希尔排序(Shell Sort)又称为“缩小增量排序”。是1959年由D.L.Shell提出来的。该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。
具体做法:首先确定一组增量d0,d1,d2,d3,...,dt-1()其中n>d0>d1>...>dt-1=1),对于i=0,1,2,...,t-1,依次进行下面的各趟处理:根据当前增量di将n个元素分成di个组,每组中元素的下标相隔为di;再对各组中元素进行直接插入排序.
给定实例的shell排序的排序过程
假设待排序文件有10个记录,其关键字分别是:
49,38,65,97,76,13,27,49,55,04。
增量序列的取值依次为:
5,3,1
排序过程如【动画模拟演示】。
希尔排序的JAVA实现
public class Test {
public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 };
public static void main(String args[]) {
int i; // 循环计数变量
int Index = a.length;// 数据索引变量
System.out.print("排序前: ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a[i]);
System.out.println("");
ShellSort(Index - 1); // 选择排序
// 排序后结果
System.out.print("排序后: ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a[i]);
System.out.println("");
}
public static void ShellSort(int Index) {
int i, j, k; // 循环计数变量
int Temp; // 暂存变量
boolean Change; // 数据是否改变
int DataLength; // 分割集合的间隔长度
int Pointer; // 进行处理的位置
DataLength = (int) Index / 2; // 初始集合间隔长度
while (DataLength != 0) // 数列仍可进行分割
{
// 对各个集合进行处理
for (j = DataLength; j < Index; j++) {
Change = false;
Temp = a[j]; // 暂存Data[j]的值,待交换值时用
Pointer = j - DataLength; // 计算进行处理的位置
// 进行集合内数值的比较与交换值
while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) {
a[Pointer + DataLength] = a[Pointer];
// 计算下一个欲进行处理的位置
Pointer = Pointer - DataLength;
Change = true;
if (Pointer < 0 || Pointer > Index)
break;
}
// 与最后的数值交换
a[Pointer + DataLength] = Temp;
if (Change) {
// 打印目前排序结果
System.out.print("排序中: ");
for (k = 0; k < Index; k++)
System.out.printf("%3s ", a[k]);
System.out.println("");
}
}
DataLength = DataLength / 2; // 计算下次分割的间隔长度
}
}
}
算法分析
1.增量序列的选择
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征:
① 最后一个增量必须为1;
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验,给出了目前较好的结果:当n较大时,比较和移动的次数约在nl.25到1.6n1.25之间。
2.Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因:
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
③在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。
因此,希尔排序在效率上较直接插人排序有较大的改进。
3.稳定性
希尔排序是不稳定的。参见上述实例,该例中两个相同关键字49在排序前后的相对次序发生了变化
分享到:
相关推荐
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。
基本思想 先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2重复上述的分组和排序,直至所取的增量...
希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列(由相隔某个“增量”的记录组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的记录"基本有序"时,再对全体记录进行一次...
希尔排序是一种改进的插入排序算法,它的基本思想是将待排序的数组按照一定的间隔进行分组,对每组使用插入排序算法进行排序,然后缩小间隔,再对分组进行排序,直到间隔为1为止。 逐渐减小间隔大小的方法有助于...
希尔排序(Shell Sort)是插入排序的一种更高效的改进版本,也称为“缩小增量排序”。它的基本思想是:先将整个待排序的记录序列分割成若干个子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体...
通过学习和完成这个练习,读者将能够掌握希尔排序算法的思想和实现过程,并了解其在排序算法中的应用。此外,文档还提供了练习题和答案,帮助读者巩固所学知识并检查自己的理解。 无论您是C++编程的初学者还是有...
排序思想:希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序,如果数组的最大值刚好是在第一位,要将它挪到正确的位置就需要 n – 1 次移动。当原数组的一个元素如果距离它正确的位置很远的话,需要...
C++ 算法之希尔排序算法详解及实例 希尔排序算法 定义: 希尔排序是插入排序的一种,也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。 算法思想: 希尔排序是把记录按下标的一定增量分组,对每组...
希尔排序的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素...
希尔排序:代码定义了一个名为`shell_sort`的函数,接受一个待排序的数组作为参数。在函数内部,首先确定初始的间隔`gap`为数组长度的一半,然后进行循环直到`gap`为0。 #在每一次循环中,使用插入排序的思想对数组...
内容为用希尔排序法实现元素的非递减排序,它的基本思想是:先将整个待排序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本”有序时,再对全体记录进行一次直接插入排序。
希尔排序是指记录按下标的一定增量分组,对每一组使用 直接插入排序 ,随着增量逐渐减少,每组包含的关键字越来越多,当增量减少至 1 时,整个序列恰好被分成一组,算法便终止。 操作步骤: 先取一个小于 n(序列...
枚举算法,递归与分治策略,递归与迭代的思想、求最大值最小值、线性查找、二分查找与冒泡排序以及选择与交换排序、插入和希尔排序。本课程除了强调经典的算法理论和模型,亦兼顾编程实践能力。力图使得学员面对复杂...
整合各种算法,利用选择排序法,冒泡排序法,希尔排序法,堆排序法等算法
希尔排序 思想 用增量来将数组进行分隔,直到增量为1。底层干的还是插入排序干的活 做法 最外层for外循环控制增量的数量,每次/2 第二层for循环控制每次增量那组开始进行插入...
本文实例讲述了php实现希尔排序算法的方法。分享给大家供大家参考,具体如下: 虽然现在各种程序语言都有其各自强大的排序库函数,但是这些底层实现也都是利用这些基础或高级的排序算法。...希尔排序的一个思想就是,分
排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个关键字...其中快排尤为重要,几乎可以说IT开发类面试必考内容,而希尔排序和归并排序的思想也非常重要。
通过实验,帮助学生由浅入深地掌握各种简单排序和高级排序的基本思想,让他们比较其性能,也让他们更好地理解希尔排序和快速排序的方法。 1.任意输入一个数组并利用简单选择排序算法对此数组的元素按从大到小的顺序...
// 希尔排序 /* { int dlta2[3] = { 3, 2, 1 }; ShellSort( a, dlta2, 3 ); } */ // 起泡排序 //BubbleSort( a ); // 快速排序 //QuickSort( a, 1, LENGTH ); // 选择排序 //SelectSort( a ); // ...
通过对直接插入插排序、折半插入排序、冒泡排序、快速排序、希尔排序、直接选择排序、堆排序、归并排序这几种内部排序算法进行比较,能够加深我们对这些排序的基本思想及排序算法的掌握和理解。 通过该题目的设计...