发表文章

[最新] 希尔排序

a214704 27天前 0

希尔排序 

        基于插入排序的快速的排序算法,将数组从最大H( h=1,h<n/3,h=3*h+1)有序逐渐变为H=1有序,最终排序成功,这样对于序列比较乱,交换距离比较远的数组排序起来比较快。

package com.mahai.sort;

import java.util.Scanner;

public class Shell {
	/**
	 * TODO 希尔排序
	 * 按照升序排列
	 */
	public static void sort(String[] a) {
		int n = a.length;
		int h = 1;
		while (h < n/3) {//将数组变为H有序
			h = 3*h + 1;
		}
		while (h >= 1) {
			for (int i = h; i < n; i++) {
				//将a[i]插入到a[i-h],a[i-2h]......
				for (int j = i; j >= h && less(a[j], a[j-h]); j-=h) {
					exch(a, j, j-h);
				}
			}
			h = h/3;
		}
	}
	//TODO 比较方法
	private static boolean less(String a, String b) {
		return a.compareTo(b) < 0;
	}
	//TODO 交换方法
	private static void exch(String[] a,int i,int j) {
		String ex;
		ex = a[i];
		a[i] = a[j];
		a[j] = ex;
	}
	//TODO 显示方法
	private static void show(String[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+" ");
		}
		System.out.println();
	}
	//TODO main方法
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		System.out.println("请输入数组长度:");
		int length = s.nextInt();
		String[] a = new String[length];
		for (int i = 0; i < length; i++) {
			System.out.println("请输入第"+(i+1)+"个元素:");
			a[i] = s.next();
		}
		s.close();
		System.out.println("输入完毕!");
		show(a);
		sort(a);
		show(a);
	}

}

 

相关推荐
最新评论 (0)
返回
发表文章
a214704
文章数
16
评论数
0
注册排名
746045