冒泡排序時間之所以效率低，就是因為將所有數(shù)都一視同仁不做區(qū)分挨個比較，這是最普通的做事方法，所以效率也是最普通的，時間復(fù)雜度為N的平方；而歸并排序效率高，則是采用了分治的思想，將一個整體分成多個小份，每個小份排好序之后再互相比較，這樣就比冒泡快了不少，時間復(fù)雜度為NlogN；快速排序的平均時間復(fù)雜度也是NlogN，但是實際的耗費時間會比歸并排序快兩三倍（當(dāng)然快排在最壞的情況下時間復(fù)雜度還是N的平方，比歸并排序大），它的平均執(zhí)行時間能比歸并更快一些是因為它每次分組時不是隨機分組而是相對有序的分組，即先從數(shù)組中隨機取一個數(shù)作為基數(shù)，然后將數(shù)據(jù)移動，使得基數(shù)一邊的數(shù)都比它小，另一邊的數(shù)都比它大，再在兩邊各取一個基數(shù)進行相同的移動、分組操作，遞歸下去，這樣每個細(xì)分的小組都在整體的大數(shù)組中有個位置，合并時直接按從小到大將各個分組合并起來即可，所以一般情況下會比歸并快一些。
了解了思想之后，再用代碼實現(xiàn)相對就會容易很多。此處就再借用一個直觀一點的例子來說明歸并與快排二者的區(qū)別。假設(shè)有1000個學(xué)生，想對他們的成績進行排序。方法1借用歸并排序的思想，具體這樣做：將這1000個人分成10組，將每組的100人進行排序，排完之后再在各組之間從小到大依次進行比較，最后得到整個的成績排名。方法2借用快速排序的思想，具體需這樣做：將1000個人也是分成10組，但是是按分?jǐn)?shù)段分，0-10分的放在一組，10-20分的放在一組，20-30分的放在一組，依次類推，分完組之后再在各個小組中進行排序，而當(dāng)你合并各個小組時，只需將其按從小到大的順序直接合并就行，無需跟方法1一樣將各小組中的數(shù)據(jù)取出來跟其他小組中的數(shù)據(jù)挨個比較。看到這里，想必各位道友對快排比歸并排序還要快一些的原因就有了解了。
算法可以理解成做事的技巧或者說套路，我們對其的理解可以不止于編程，完全可以推廣出去。比如歸并的分治法，將一個大事情拆解成多個小事件，解決起來就會方便很多。閑話扯了一大堆，下面就將我自己寫的排序給大家貼出來，附帶上注釋講解，如果有之前不了解的道友，相信看完之后便會念頭通透，原地飛升 >_< 。 正文 [erji]歸并排序[/erji]
// 歸并排序
public static void mergeSort (int[] arr) {
// 建一個臨時數(shù)據(jù)來存放數(shù)據(jù)
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
}
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) { // 如果起始下標(biāo)跟結(jié)束下標(biāo)差值小于1，則不進行操作
int mid = (left + right) / 2;
mergeSort(arr, left, mid, temp); // 分組，將左邊分為一組，遞歸調(diào)用進行排序
mergeSort(arr, mid+1, right, temp); // 將右邊分為一組
merge(arr, left, mid, right, temp); //將左右分組合并
}
}
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 定義左指針
int j = mid + 1; // 定義右指針
int t = 0; // 給temp臨時數(shù)組用的指針
while (i <= mid && j <= right) { // 設(shè)置左右指針的移動邊界
if (arr[i] <= arr[j]) { // 此處是升序，故誰小誰先賦給臨時數(shù)組
temp[t++] = arr[i++];
} else {
temp[t++] = arr[j++];
}
}
while (i <= mid) { // 如果左邊有剩余，則放在temp中
temp[t++] = arr[i++];
}
while (j <= right) { // 如果右邊有剩余，依次放入temp中
temp[t++] = arr[j++];
}
t = 0;
// 此時temp中已經(jīng)是arr數(shù)組中下標(biāo)從left到right之間排好序的數(shù)據(jù)了，因為temp每次都是從0開始賦值，所以需將排好序的數(shù)放回arr的對應(yīng)位置
while (left <= right) {
// 將left到right之間排好序的數(shù)據(jù)放回arr中，此時left到right之間的數(shù)就是最終排好序的數(shù)
arr[left++] = temp[t++];
}
}
快速排序
// 快速排序
public static void quickSort (int[] arr, int left, int right) {
// 先將異常情況處理掉
if (arr == null || arr.length < 2) {
return;
}
if (right <= left) {
return;
}
if (right - left == 1 && arr[left] <= arr[right]) {
return;
}
// 取第一個數(shù)為基準(zhǔn)數(shù)(基數(shù)取哪個都行，此處是為了方便)
int index = arr[left];
int i = left + 1; // 左指針
int j = right; // 右指針
while (i < j && i < right && j > left) { // 設(shè)置指針的移動邊界
while (arr[j] > index && j > left) {j--;} // 找到從右邊數(shù)第一個比index小的數(shù)
while (arr[i] < index && i < right) {i++;} // 找到從左邊數(shù)第一個比index大的數(shù)
if (i < j) { // 交換這兩個數(shù) 如果i == j，說明二者定位到了同一個位置，則不用交換；如果i > j，說明二者已經(jīng)相遇然后背向而行了，也不交換
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 執(zhí)行完上面循環(huán)后，arr已經(jīng)是左邊比index小，右邊比index大的數(shù)組了，只是基準(zhǔn)數(shù)仍在基準(zhǔn)位置left處，需放到它應(yīng)該在的位置
if (j != left && arr[j] != arr[left]) {
// j最后停留位置的數(shù)，肯定是一個小于等于index的值，所以如果不是同一個位置的話，直接將二者調(diào)換一下位置即可
int temp = arr[j];
arr[j] = arr[left];
arr[left] = temp;
}
quickSort(arr, left, j-1); // 將基準(zhǔn)數(shù)左邊排序
quickSort(arr, j+1, right); // 將基準(zhǔn)數(shù)右邊排序
}
