排序算法比较之一：冒泡和归并

冒泡和归并排序是两种常用的排序方法，实际应用中性能差别有多大呢，通过如下有两个小测试可以看到它们之间大概的差距。

 

需求：

对10000个员工根据编号排序，员工编号以A开头。由于各公司分别编号，员工编号可以重复。

 

util类：

 

public class SortUtil {
	private static final int EMP_NUMBER = 10000;
	
	public static void swap(Employee[] employees, int i, int j){
		Employee temp = employees[i];
		employees[i] = employees[j];
		employees[j] = temp;
	}
	
	public static Employee[] createEmployees(){
		long start = System.currentTimeMillis();
		Employee[] employees = new Employee[EMP_NUMBER];
		
		for(int i = 0; i < EMP_NUMBER; i++){
			employees[i] = new Employee();
			employees[i].setEmNO("A"+ String.valueOf((int)(Math.random() * 1000)));
		}
		System.out.println("~~~~~~~~ createEmployees() Time elapsed : "+ (System.currentTimeMillis() - start));
		
		return employees;
	}
}

 

 

2路归并排序：

 

/**
 * 对10000个员工号码进行排序
 * 归并排序
 * 
 * @author Administrator
 *
 */
public class TestSortMergeEmployee {
	private static Employee[] employees = null;
	
	public void mergeSort(Employee[] array) {
		if(employees == null || employees.length == 0 || employees.length == 0)
			throw new RuntimeException("******** Array is null or Empty!");
		
		long start = System.currentTimeMillis();
		Employee[] temp = new Employee[array.length];
		mSort(array, temp, 0, array.length - 1);
		System.out.println("~~~~~~~~ Merge sort time elapsed : "+ (System.currentTimeMillis() - start));
	}

	private void mSort(Employee[] a, Employee[] temp, int first, int last) {
		if (first < last) {
			int mid = (first + last) / 2;
			
			mSort(a, temp, first, mid);
			mSort(a, temp, mid + 1, last);
			merge(a, temp, first, mid, last);
		}
	}

	private void merge(Employee[] a, Employee[] temp, int first, int mid, int last) {
		int i = first;
		int j = mid + 1;
		int m = mid;
		int n = last;
		int k = 0;
		
		while (i <= m && j <= n) {
			//if (a[i] < a[j])
			if(a[i].compareTo(a[j]) < 0)
				temp[k++] = a[i++];
			else
				temp[k++] = a[j++];
		}
		
		while (i <= m)
			temp[k++] = a[i++];
		
		while (j <= n)
			temp[k++] = a[j++];
		
		for (i = 0; i < k; i++)
			a[first + i] = temp[i];
	}
	
	
	public static void main(String[] args) {
		TestSortMergeEmployee sortEmployees = new TestSortMergeEmployee();
		employees = SortUtil.createEmployees();
		sortEmployees.mergeSort(employees);
		
		/*for(int i = 0; i < employees.length; i++){
			System.out.println(employees[i].getEmNO());
		}*/
	}

}

 

 

冒泡排序：

/**
 * 对100000个员工号码进行排序
 * 冒泡排序
 * 
 * @author Administrator
 *
 */
public class TestSortBubbleEmployees {
	private static Employee[] employees = null;	
	
	
	public Employee[] sortBuddle(Employee[] employees){
		if(employees == null || employees.length == 0 || employees.length == 0)
			return employees;		
		
		int length = employees.length;
		
		long start = System.currentTimeMillis();
		for(int i = 0; i < length; i++){
			for(int j = length - 1; j > i + 1; j--){
				if(employees[i].compareTo(employees[j]) > 0)
					SortUtil.swap(employees, i, j);
			}
		}
		System.out.println("~~~~~~~~ Bubble sort time elapsed : "+ (System.currentTimeMillis() - start));
		
		return employees;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		TestSortBubbleEmployees sortEmployees = new TestSortBubbleEmployees();
		employees = SortUtil.createEmployees();
		Employee[] rtnEmployees = sortEmployees.sortBuddle(employees);
		
		/*for(int i = 0; i < rtnEmployees.length; i++){
			System.out.println(rtnEmployees[i].getEmNO());
		}*/
	}

}

 

测试结果：

 

归并排序：

~~~~~~~~ Merge sort time elapsed : 40

 

冒泡排序：

~~~~~~~~ Bubble sort time elapsed : 11390

 

 

测试结论：

虽然测试环境等因素会影响测试结果，但以上测试结果可以初步证明冒泡排序和归并排序性能差距比较大，大约相差200倍左右。究其原因，冒泡排序移动次数太多了，造成用时较多。

 

如果按照以上的代码进行测试，当员工增长到10万人时，冒泡排序程序运行几分钟也排不完。如果排序超大数据集时，用时之久可想而知。

 

因此，虽然冒泡算法是很基础的算法，并且具备比较简单和容易编写等特点，但可用性太差，建议大多数情况下，应该回避该算法。