一直都有寫技術博客的想法，以前由于儲備知識不夠，一直沒寫。如今在女朋友的支持下，開始嘗試寫寫技術博客，就當方便自己查找的工具貼吧。好了，廢話不說了，上干貨。

排序算法大體分為5大類：選擇排序，插入排序，交換排序，歸并排序，基數排序

一.交換排序（冒泡排序+快速排序）

1.冒泡排序

冒泡排序的核心思想就是將權重輕的氣泡上升到序列最前（對于升序排列），而對于降序排列則反之。

由于使用java寫的，所以要使用到java當中的一些特性，比如泛型和比較類

根據比較類comparator來判斷是升序排列還是降序排列，comparator中的compare函數返回a > b ? 1 : (a < b ? -1 : 0)，是升序排列，返回a > b ? -1 : (a < b ? 1 : 0)，則是降序排列

冒泡排序的基本思路是：

①假定整個數組都是無序區域②無序區域第一個氣泡一次和后續氣泡進行比較③不滿足排序規則的氣泡，則讓兩個氣泡交換位置④一趟遍歷過后，有序區域出現一個氣泡，無序區域還剩下n-1個氣泡⑤重復①~④步驟

public static <T> void bubbleSort(T[] t, Comparator<? super T> comparator) {		int size = t == null ? 0 : t.length;		T temp = null;   // 用于記錄臨時數據		for(int i = 0; i < size - 1; i++) {			for(int j = i + 1; j < size; j++) {				// 交換兩個數的位置				if(comparator.compare(t[i], t[j]) > 0) {					temp = t[i];					t[i] = t[j];					t[j] = temp;				}			}		}	}時間復雜度：O(n^2)
空間復雜度：O(1)
二.快速排序
快速排序主要用到了分治法的基本思想，分治法就是將一個原問題分解成幾個規模更小但是結構和原問題相似的子問題，然后遞歸解決。
根據比較類comparator來判斷是升序排列還是降序排列，comparator中的compare函數返回a > b ? 1 : (a < b ? -1 : 0)，是升序排列，返回a > b ? -1 : (a < b ? 1 : 0)，則是降序排列
快速排序基本思路：① 選擇第一個數為基準值②從左到右遍歷，遍歷到第一個比基準值大的數為止③從右向左遍歷，遍歷到第一個比基準值小的數為止④步驟②和步驟③所在的元素進行交換⑤重復②~④，這樣的得出過結果是一側是全比基準點小的元素，一側是全比基準點大的元素⑥對兩側元素分別進行遞歸計算
public static <T> void quickSort(T[] t, int start, int end, Comparator<? super T> comparator) {   	    if (start < end) {   	        T base = t[start]; // 選定的基準值（第一個數值作為基準值）   	        T temp;            // 記錄臨時中間值   	        int i = start, j = end;   	        while(i < j) {   	            while((comparator.compare(t[i] ,base) < 0) && (i < end)) {  	                i++;   	            }	            while((comparator.compare(t[j], base) > 0) && (j > start)) {   	                j--;   	            }	            if(i <= j) {   	                temp = t[i];   	                t[i] = t[j];   	                t[j] = temp;   	                i++;   	                j--;   	            }   	        }   	        if(start < j) { 	        	quickSort(t, start, j, comparator);   // 對低字段表進行遞歸排序	        }	        if(end > i) {	        	quickSort(t, i, end, comparator);     // 對高字段表進行遞歸排序	        }	    }   	}
時間復雜度：O(nlog2n)
空間復雜度：O(log2n)
測試一下算法的性能吧，選用不同的排序算法對程序整體的性能影響還是挺大的。
首先需要打亂已知數組的順序思路：①假定已知數組是一個有序序列②隨機一個有序序列的索引，該所在的元素和有序序列最后一個元素交換③有序序列的最后一個元素加入到無序序列中④重復①~③時間復雜度：O(n)空間復雜度：O(1)
public static <T> void disturbOrder(T[] t) {		int size = t == null ? 0 : t.length;		if(size != 0) {			int randCount = 0; // 索引			int position = 0;  // 當前位置			T temp;			do {    				Random rand = new Random();  				int r = size - randCount;  				position = rand.nextInt(r);    			 	randCount++;  			 	// 將隨機出的索引所在的位置的數據和r位數據進行交換			 	temp = t[position];			 	t[position] = t[r - 1]; 			 	t[r - 1] = temp;		 	} while (randCount < size);		}	}
簡單寫個測試程序
public static void main(String[] args) {		Integer[] numbers = new Integer[10000];		for(int i = 0; i < numbers.length; i++) {			numbers[i] = i;		}		disturbOrder(numbers);		long start = System.currentTimeMillis();		quickSort(numbers, 0, numbers.length - 1, new Comparator<Integer>() {			@Override			public int compare(Integer a, Integer b) {				return a > b ? 1 : (a < b ? -1 : 0);			}		});		long end = System.currentTimeMillis();		System.out.PRintln("快速排序耗時:" + (end - start));				disturbOrder(numbers);		long start1 = System.currentTimeMillis();		bubbleSort(numbers, new Comparator<Integer>() {			@Override			public int compare(Integer a, Integer b) {				return a > b ? 1 : (a < b ? -1 : 0);			}		});		long end1 = System.currentTimeMillis();		System.out.println("冒泡排序耗時:" + (end1 - start1));}控制臺打印結果：
快速排序耗時:43ms冒泡排序耗時:225ms