/*
希尔排序
在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。
希尔排序是不稳定的,其时间复杂度为O(n ^2)。
*/
public class ShellSort{
public static void main(String[] args){
// int[] array = {49,38,65,97,76,13,27};
int[] array = {49,38,65,97,76,13,27,49,55,04};
// shellSort(array,array.length);
for(int i=0;i<array.length;i++){
System.out.print(array[i]+" ");
}
}
/*
public static void shellSort(int[] arr,int length){
int h;
while(arr.length/3>h){
h = h*3+1;
}
while(h>0){
for(int i=h;i>0;i++){
int temp = arr[i];
int j =i;
while(j >h-1 && arr[j-h]>temp ){
arr[j] = arr[j-h];
j -=h;
}
arr[j] = temp;
}
h=(h-1)/3;
}
}
*/
/*
public static void shellSort(int[] array,int length){
int increment=length/2; //增量初值,不妨设n>0
do {
shellPass(array,increment,length);//一趟增量为increment的Shell插入排序
increment=increment/3+1;//求下一增量
}while(increment>1);
} //ShellSort
public static void shellPass(int[] array,int d,int length){//希尔排序中的一趟排序,d为当前增量
for(int i=d+1;i<length;i++) //将R[d+1..n]分别插入各组当前的有序区
if(array[i]<array[i-d]){
array[0]=array[i];
int j=i-d;//R[0]只是暂存单元,不是哨兵
do {//查找R[i]的插入位置
array[j+d]=array[j];//后移记录
j=j-d;//查找前一记录
}while(j>0&&array[0]<array[j]);
array[j+d]=array[0]; //插入R[i]到正确的位置上
} //endif
} //ShellPass
*/
/*
//希尔排序, array要排序的数据, len数据的个数
public static void shellSort(int[] array, int len){
//以step分组,step每次减为原来的一半。
for (int step = len / 2; step > 0; step /= 2){
//对每个组进行排序
for (int i = 0 ;i < step; i++){
sortGroup(array, len, i, step);
}
}
}
public static void sortGroup(int[] array, int len, int start,int step){
for (int i = start + step; i < len; i += step){
//寻找i元素的位置,
for (int j = start; j < i; j+= step){
//如果比他小,则这里就是他的位置了
if (array[j]>array[i]){
int nTemp = array[i];
for (int k = i; k > j; k -= step){
array[k] = array[k - step];
}
array[j] = nTemp;
}
}
}
}
public static void shellSort2(int arr[], int n){
int i, j;
int key;
int h;
for (h = 1; h <= (n-1)/9; h = 3*h + 1)
for (; h > 0; h /= 3)
for (i = h; i < n; i++){
key = arr[i];
j = i;
while ((j >= h) && (arr[j-h] > key)){
arr[j] = arr[j-h];
j -= h;
}
arr[j] = key;
}
}
*/
}
分享到:
相关推荐
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
一个数据结构作业,对刚刚学习希尔排序知识的同学有用,用C++做的
合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现,原创。
希尔排序 希尔排序希尔排序希尔排序希尔排序希尔排序希尔排序希尔排序
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
希尔排序的源代码; 平台:CentOS release 5.4 (Final) 编译器:GCC 4.3.2
用C++,模板写的 7中排序. 快速排序, 归并排序,插入排序,选择排序,起泡排序,堆排序,希尔排序
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
此希尔排序算法采用增量减半的方法来进行数据的排序,内有部分注释
排序算法: 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序
1) 至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。并把排序后的结果保存在不同的文件中。 2) 统计每一种排序方法的性能(以上机...
希尔排序法,最经典的排序法,但不是容易懂。包括希尔插入排序,希尔交换排序
排序算法很多,下面有基数排序,堆排序,希尔排序,直接插入排序的代码和思路
本实验含有四部分内容——直接插入排序、希尔排序、选择排序、快速排序,在上述内容的基础上,将所有排序算法整合在一个程序中。学生可参考教材中的伪代码。鼓励学生自创新思路,新算法。
就利用汇编版的希尔排序来写了一下超级列表框排序.发现,从取值-排序-显示过程才花了1秒的时间.速度是七号排序的30倍,凌晨孤星-超级列表框排序的3倍.而这个希尔排序模块.只用增加,删减自定义数据类型成员.即可变身另...
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
希尔排序,堆排序,快速排序,简单选择排序,插入排序,冒泡排序
插入排序之希尔排序
了解冒泡,选择,插入,希尔排序 基本的渐进分析
希尔排序(程序).txt希尔排序(程序).txt希尔排序(程序).txt