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

       希尔排序是对直接插入排序算法的一种改进，其基本原理就是让一个无序的数列变得“基本有序”，那么在最后进行直接插入排序的时候时间复杂度将会降低很多（在理想情况下，如果一个数列是有序的，那么使用直接插入排序的算法时间复杂度为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

 运行结果：