Java希尔排序实现

 

package com.sort.shell;

import java.util.Calendar;
import java.util.Random;

public class ShellSort {
	public static void main(String[] args) {
		Random random = new Random();
		int nums[] = new int[100000];
		for (int i = 0; i < nums.length; i++) {
			nums[i] = random.nextInt(1000000);
		}
		int nums2[] = nums.clone();
		
		long t1 = System.currentTimeMillis(); // 排序前取得当前时间 
		shellSort(nums);
		
		
		System.out.println("--------after ShellSort--------");
		long t2 = System.currentTimeMillis(); // 排序后取得当前时间  

		Calendar c = Calendar.getInstance();  
        c.setTimeInMillis(t2 - t1);  
  
        System.out.println("耗时: " + c.get(Calendar.MINUTE) + "分 "  
                + c.get(Calendar.SECOND) + "秒 " + c.get(Calendar.MILLISECOND)  
                + " 毫秒");  
        
        
        
		
		t1 = System.currentTimeMillis(); // 排序前取得当前时间
		popSort(nums2);
		
		
		System.out.println("--------after PopSort--------");
		t2 = System.currentTimeMillis(); // 排序后取得当前时间  
        c.setTimeInMillis(t2 - t1);  
  
        System.out.println("耗时: " + c.get(Calendar.MINUTE) + "分 "  
                + c.get(Calendar.SECOND) + "秒 " + c.get(Calendar.MILLISECOND)  
                + " 毫秒");  
        
	}

	private static void popSort(int[] nums) {
		
		int len = nums.length;
		
		for(int i=0;i<len;i++) {

			for(int j=1;j<len;j++) {
				if(nums[j-1] > nums[j] ) {
					int temp = nums[j-1];
					nums[j-1] = nums[j];
					nums[j] = temp;
				}
			}
		}
		
	}

	public static void shellSort(int nums[]) {
		int h = 1;
		int len = nums.length;
		while (h < len) {
			h = 3 * h + 1;
		}
		h = (h - 1) / 3;

		while (h > 0) {

			int inner, outer;
			int temp;

			for (outer = h; outer < len; outer++) {
				temp = nums[outer];
				inner = outer;
				while (inner >= h && nums[inner - h] >= temp) {
					nums[inner] = nums[inner - h];
					inner -= h;
				}
				nums[inner] = temp;
			}

			h = (h - 1) / 3;
		}
	}
	
	
}

 

 

希尔排序与冒泡的对比·····

 

输出结果：

 

--------after ShellSort--------

耗时: 0分 0秒 32 毫秒

--------after PopSort--------

耗时: 1分 13秒 125 毫秒