算法数据结构学习笔记-插入排序

近来想重新研究并实践一下大学时候学的的算法和数据结构，于是下了本《Introduction to Algorithms》作为参考书。因为原来理论基本上都学过了，但是实践的比较少，所以打算对某个topic先动手写写看能不能用程序实现出来，并对程序做一定的时间空间效率分析，接下来再参考书上是如何研究分析和改进一个算法的。废话少说，第一个topic：Insertion Sort

public class InsertionSort
{
	public static void main(String[] args) {
		int[] data = {32, 24, 25, 324, 30, 23, 233, 34, 233};
		insertionSort(data);
	}
	
	/**
	 *Insertion Sort in ascending order.
	*/
	public static void insertionSort(int[] data){
		if(data == null) {
			return;
		}
		
		int temp;
		for(int i = 1; i < data.length; i++) {
			temp = data[i];
			for(int j = i - 1; j >= 0 && temp < data[j]; j--) {
					data[j+1] = data[j];
					data[j] = temp;

					print(data, i);
					print(data, data.length - 1);
					System.out.println();
			}
		}
	}

	/**
	* Print out the array with index less than the specified bound.
	*/
	public static void print(int[] data, int bound) {
		for( int i = 0; i <= bound; i++) {
			System.out.print(data[i] + " ");
		}

		System.out.println();
	}
}

排序过程及结果：

24 32
24 32 25 324 30 23 233 34 233

24 25 32
24 25 32 324 30 23 233 34 233

24 25 32 30 324
24 25 32 30 324 23 233 34 233

24 25 30 32 324
24 25 30 32 324 23 233 34 233

24 25 30 32 23 324
24 25 30 32 23 324 233 34 233

24 25 30 23 32 324
24 25 30 23 32 324 233 34 233

24 25 23 30 32 324
24 25 23 30 32 324 233 34 233

24 23 25 30 32 324
24 23 25 30 32 324 233 34 233

23 24 25 30 32 324
23 24 25 30 32 324 233 34 233

23 24 25 30 32 233 324
23 24 25 30 32 233 324 34 233

23 24 25 30 32 233 34 324
23 24 25 30 32 233 34 324 233

23 24 25 30 32 34 233 324
23 24 25 30 32 34 233 324 233

23 24 25 30 32 34 233 233 324
23 24 25 30 32 34 233 233 324

插入排序的原理就是：当前元素从后往前查找到升比自己小（序）或比自己大（降序）的元素，在查找过程中的同时还要将前一个元素向后一个元素的位置移动，所以当前的元素的值会被冲掉，因此要先将其保存在temp里面。
时空效率分析：
空间：进行排序动作时，需要一个额外的临时变量用来保存当前元素
时间复杂度：1 + 2 + ........n-1 ( n >= 1) = (n-1 + 1)(n-1)/2 = (n^2 - n)/2，即为O(n^2)

附：考虑到概率问题，当前元素data[i] 与data[1..i-1]平均需要i/2次比较，故实际比较次数应为1/2 + 2/2 + ............(n-1)/2 ( n >= 1) = (n^2-n)/4

以上程序只选择int类型作为处理数据，考虑到通用性，可以通过传入一个Comparator实现类来对所有的类型进行排序。

import java.util.Comparator;

class IntComparator implements Comparator
{

	public int compare(Object obj1, Object obj2) {
		Integer num1 = (Integer)obj1;
		Integer num2 = (Integer)obj2;

		return num1 - num2;
	}

	/**
	*To determine that two distinct Comparators impose the same order thus improve the performance in some cases.
	*/
	public boolean equals(Object obj) {
		if( this == obj ) {
			return true;
		}
		if(!(obj instanceof IntComparator) ){
			return false;
		}

		return false;
	}
}

import java.util.Comparator;

public class GenericInsertionSort 
{
	public static void main(String[] args) {
		Integer[] data = {32, 23, 3234, 324, 343};
		insertionSort(data, new IntComparator());
		for(int i = 0; i < data.length; i++) {
			System.out.println(data[i]);
		}
	}
	public static <T> void insertionSort(T[] data, Comparator comparator) {
		if(data == null) {
			return;
		}

		int length = data.length;
		for( int i = 1; i < length; i++ ) {
			T temp = data[i];
			for(int j = i - 1; j >= 0 && comparator.compare(temp, data[j]) < 0; j--) {
				data[j+1] = data[j];
				data[j] = temp;
			}
		}
	}
}

这样，就可以对任何类型进行排序了，这时需要传入一个实现了Comparator接口的比较类。比如想结合员工的工龄和工资进行排序，在Compartor方法里实现想要的逻辑就行了。