`
狂盗一枝梅
  • 浏览: 18172 次
  • 性别: Icon_minigender_1
  • 来自: 青岛
社区版块
存档分类
最新评论

【数据结构】【排序】希尔排序

阅读更多

       希尔排序是对直接插入排序算法的一种改进,其基本原理就是让一个无序的数列变得“基本有序”,那么在最后进行直接插入排序的时候时间复杂度将会降低很多(在理想情况下,如果一个数列是有序的,那么使用直接插入排序的算法时间复杂度为O(n));希尔排序算法的效率和“步长”的定义息息相关,但是如何给出一个步长使得希尔排序算法的效率最高,是非常困难的。

import java.util.Scanner;

public class ShellInsertSort{
	public static void main(String args[]){
		Scanner scanner=new Scanner(System.in);
		int total=scanner.nextInt();
		int[] array=new int[1024];
		for(int i=0;i<total;i++){
			array[i]=scanner.nextInt();
		}
		//定义步长数组
		int[] step={10,8,6,5,4,3,2,1};
		shellSort(array,total,step);
		output(array,total);
	}
	public static void output(int[] array,int total){
		for(int i=0;i<total;i++){
			System.out.print(array[i]+" ");
		}
		System.out.println();
	}
	/**
		参数说明:
		array:待排数组;
		total:数组长度;
		step:步长定义
	*/
	public static void shellSort(int[] array,int total,int[] step){
		for(int i=0;i<step.length;i++){
			int dk=step[i];
			int temp=0;
			for(int j=dk;j<total;j++){
				if(array[j]<array[j-dk]){
					temp=array[j];				 
					int k=0;
					for(k=j-dk;k>=0&&temp<array[k];k-=dk){
						array[k+dk]=array[k];
					}
					array[k+dk]=temp;
				}
				
			}
		}		
	}
}

 测试用例:仍然使用MyRandom类生成1024个打乱的整数:

import java.util.Random;

public class MyRandom {
	public static void main(String args[]){
		int[] array=new int[1024];
		for(int i=0;i<1024;i++){
			array[i]=i;
		}
		for(int i=0;i<=1023;i++){
			int m=new Random().nextInt(1024);
			int n=new Random().nextInt(1024);
			int temp=array[m];
			array[m]=array[n];
			array[n]=temp;
		}
		System.out.println("1024");
		for(int i=0;i<1024;i++){
			System.out.print(array[i]+" ");
		}
		System.out.println();
	}
}

 运行方法:

java MyRandom | java ShellSort

 运行结果:

 

  • 大小: 134.3 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics