排序算法之初级排序

首先，将涉及到排序的基本操作抽象为一个接口，其中包括一下一些方法：（这里的约定是从小到大的排序）

public interface Sort {

	/**
	 * 对数组a进行排序
	 * @param a
	 */
	public void sort(Comparable[] a);
	
	/**
	 * 大小比较
	 * @param a
	 * @param b
	 * @return 如果a<b，返回true，否则false
	 */
	public boolean less(Comparable a,Comparable b);
	
	/**
	 * 交换数组中连个元素的位置
	 * @param a
	 * @param i
	 * @param j
	 */
	public void exch(Comparable[] a,int i,int j);
	
	/**
	 * 打印数组
	 */
	public void show(Comparable[] a);
	
	/**
	 * 判断数组是否已经排序
	 * @return
	 */
	public boolean isSorted(Comparable[] a);
	
}

很多的方法是通用的，抽象成一个抽象父类：

public abstract class AbstractSort implements Sort {

	@Override
	public boolean less(Comparable m, Comparable n) {
		return m.compareTo(n) < 0;
	}

	@Override
	public void exch(Comparable[] a, int i, int j) {
		Comparable tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	@Override
	public void show(Comparable[] a) {
		for(Comparable c : a){
			System.out.print(c + " ") ;
		}
		System.out.println();
	}

	@Override
	public boolean isSorted(Comparable[] a) {
		for(int i= 1;i<a.length;i++){
			if(less(a[i],a[i-1])) return false;
		}
		return true;
	}

}

选择排序

该算法的思想最简单，即每次从非排序区查找一个最小元素放到已排序区的最后面：

/**
 * 选择排序
 * @author huqiao
 */
public class SelectionSort extends AbstractSort {

	@Override
	public void sort(Comparable[] a) {
		for(int i = 0 ;i<a.length;i++){
			//从非排序段中找到目前最小的，放到已排序区的最末端，即i处
			for(int j = i+1;j<a.length;j++){
				if(less(a[j],a[i])){
					exch(a,i,j);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		int size = 100000;
		Integer[] a = RandomFactory.randomInt(size,400);
		
		SelectionSort sort = new SelectionSort();
		//sort.show(a);
		long t = System.currentTimeMillis();
		sort.sort(a);
		t = System.currentTimeMillis() -t;
		//sort.show(a);
		
		System.out.println("Selection sort");
		System.out.println("time:" + t);
		System.out.println("random data size : " + size);
	}

}

测试对10万条数据排序结果如下：

Selection sort
time:15475
random data size : 100000

插入排序

思想类似于整理扑克牌，从无序区取一个元素，从有序区的末端往前比较，直到发现一个比自己小的元素才停止。

如上图所示，黄色部分表示有序区，白色部分表示无序区，上图展示了无序区的第一个元素（即4）从有序区往前移动的轨迹（发现3比自己小，于是停止）。

代码如下：

/**
 * 插入排序
 * @author huqiao
 */
public class InsertSort extends AbstractSort {

	@Override
	public void sort(Comparable[] a) {
		for(int i = 1 ;i<a.length;i++){
			//拿着非排序段的第一个元素，从一排序段的末尾开始逐个比较往前移动，直到发现比自己小的元素
			for(int j = i;j>0 && less(a[j],a[j-1]);j--){
				exch(a,j,j-1);
			}
		}
	}
	
	public static void main(String[] args) {
		int size = 100000;
		Integer[] a = RandomFactory.randomInt(size,400);
		
		InsertSort sort = new InsertSort();
		//sort.show(a);
		long t = System.currentTimeMillis();
		sort.sort(a);
		t = System.currentTimeMillis() -t;
		//sort.show(a);
		System.out.println("Insert sort");
		System.out.println("time:" + t);
		System.out.println("random data size : " + size);
	}

}

插入排序的表现比选择排序稍好，不过优势不是很明显：

Insert sort
time:12851
random data size : 100000

希尔排序

希尔排序是在插入排序的基础上改进而来的，它要解决的问题是，插入排序中元素移动的速度太慢。比如一个最小的元素如果排在了长度为N数组的末尾，那么它最终要移动到数组的第一位需要移动的次数是N-1。希尔排序通过h有序的方式加速了元素的移动速度：

/**
 * 插入排序
 * @author huqiao
 */
public class ShellSort extends AbstractSort {

	@Override
	public void sort(Comparable[] a) {
		int N = a.length;
		int h = 1;
		while(h<N/3) h = 3*h + 1;
		while(h>=1){
			for(int i = h ;i<a.length;i++){
				//拿着非排序段的第一个元素，从一排序段的末尾开始逐个比较往前移动，直到发现比自己小的元素
				for(int j = i;j>=h && less(a[j],a[j-h]);j-=h){
					exch(a,j,j-h);
				}
			}
			h = h/3;
		}
	}
	
	public static void main(String[] args) {
		int size = 100000;
		Integer[] a = RandomFactory.randomInt(size,40000);
		
		ShellSort sort = new ShellSort();
		//sort.show(a);
		long t = System.currentTimeMillis();
		sort.sort(a);
		t = System.currentTimeMillis() -t;
		//sort.show(a);
		
		System.out.println("Shell sort");
		System.out.println("time:" + t);
		System.out.println("random data size : " + size);
	}

}

希尔排序的表现惊人，优势很明显：

Shell sort
time:54
random data size : 100000

实际情况中，许多高级排序算法相对与希尔排序的优势也不是和明显，加上算法复杂度的考虑，希尔排序不失为一种既价廉又物美的算法。