高級排序算法

本篇包括歸并排序和快速排序，它們都是采用了分治法的 O(NlogN) 算法。

歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法，其將兩個有序的序列歸并成一個更大的有序序列。

原地歸并

原地歸并將兩個不同的有序序列歸并到第三個序列中，在實現(xiàn)過程中就需要一個輔助序列。

Python3 實現(xiàn)

def?merge(lst, l, mid, r):? ?"""? ?將 lst[l...mid] 和 lst[mid+1...r] 兩部分進(jìn)行歸并? ?"""? ?aux = copy.deepcopy(lst[l:r +?1]) ?#輔助序列aux? ?i, j = l, mid +?1? ?for?k?in?range(l, r +?1):? ? ? ?if?i > mid: ?# 左半部分元素已經(jīng)處理完畢? ? ? ? ? ?lst[k] = aux[j - l]? ? ? ? ? ?j +=?1? ? ? ?elif?j > r: ?# 右半部分元素已經(jīng)處理完畢? ? ? ? ? ?lst[k] = aux[i - l]? ? ? ? ? ?i +=?1? ? ? ?elif?aux[i - l] < aux[j - l]:? ? ? ? ? ?lst[k] = aux[i - l]? ? ? ? ? ?i +=?1? ? ? ?else:? ? ? ? ? ?lst[k] = aux[j - l]? ? ? ? ? ?j +=?1

Java 實現(xiàn)

// 將 arr[l...mid] 和 arr[mid+1...r] 兩部分進(jìn)行歸并public?static?void?merge(Comparable[] arr,?int?l,?int?mid,?int?r)?{? ?int?i = l;? ?int?j = mid +?1;? ?System.arraycopy(arr, l, aux, l, r - l +?1); ?//輔助序列aux? ?for?(int?k = l; k <= r; k++) {? ? ? ?if?(i > mid) arr[k] = aux[j++];?//左半部分元素已經(jīng)處理完畢? ? ? ?else?if?(j > r) arr[k] = aux[i++];?//右半部分元素已經(jīng)處理完畢? ? ? ?else?if?(aux[i].compareTo(aux[j]) <?0) arr[k] = aux[i++];? ? ? ?else?arr[k] = aux[j++];? ?}}

自頂向下歸并排序

對子序列 a[l…r] 進(jìn)行排序， 先將其分為 a[l…mid] 和 a[mid+1…r] 兩部分，分別通過遞歸調(diào)用將它們單獨(dú)排序，最后將有序的子序列歸并為最終的排序結(jié)果。

Python3 實現(xiàn)

def?sort(lst):? ?"""? ?初始化，使歸并排序邊界正確? ?"""? ?sort_next(lst,?0, len(lst) -?1)def?sort_next(lst, l, r):? ?"""? ?使用自頂向下、遞歸進(jìn)行歸并排序,對 lst[l...r] 的范圍進(jìn)行排序? ?"""? ?if?l >= r:? ? ? ?return? ?mid = (l + r) //?2? ?sort_next(lst, l, mid) ?#將左半部分排序? ?sort_next(lst, mid +?1, r) ?#將右半部分排序? ?# 對于 lst[mid] <= lst[mid + 1]的情況, 不進(jìn)行merge? ?if?lst[mid] > lst[mid +?1]:? ? ? ?merge(lst, l, mid, r) ?#歸并

Java 實現(xiàn)

private?static?Comparable[] aux;?// 輔助數(shù)組public?static?void?newSort(Comparable[] arr)?{? ?int?n = arr.length;? ?aux =?new?Comparable[n];?// 一次性分配空間? ?newSort(arr,?0, n -?1);}// 使用遞歸進(jìn)行歸并排序,對 arr[l...r] 的范圍進(jìn)行排序public?static?void?newSort(Comparable[] arr,?int?l,?int?r)?{? ?if?(l >= r)? ? ? ?return;? ?int?mid = (l + r) /?2;? ?newSort(arr, l, mid);?// 將左半部分排序? ?newSort(arr, mid +?1, r);?// 將右半部分排序? ?// 對于arr[mid] <= arr[mid+1]的情況,不進(jìn)行merge? ?if?(arr[mid].compareTo(arr[mid +?1]) >?0)? ? ? ?merge(arr, l, mid, r);?// 歸并}

自底向上歸并排序

原理：首先進(jìn)行兩兩歸并，然后四四歸并，接著八八歸并，一直下去，即先歸并微型序列，再成對歸并得到的子序列，一直下去，直到將整個序列歸并。

Python3 實現(xiàn)

def?sort(lst):? ?"""? ?進(jìn)行 lgN 次兩兩歸并? ?"""? ?n = len(lst)? ?sz =?1??# sz 子數(shù)組大小? ?while?sz < n:? ? ? ?l =?0??# l 子數(shù)組索引? ? ? ?while?l < n - sz:? ? ? ? ? ?# 對于 lst[mid] <= lst[mid + 1]的情況, 不進(jìn)行merge? ? ? ? ? ?if?lst[l + sz -?1] > lst[l + sz]:? ? ? ? ? ? ? ?merge(lst, l, l + sz -?1, min(l + sz + sz -?1, n -?1))? ? ? ? ? ?l += sz + sz? ? ? ?sz += sz

Java 實現(xiàn)

private?static?Comparable[] aux;// 進(jìn)行 lgN 次兩兩歸并public?static?void?newSort(Comparable[] arr)?{? ?int?n = arr.length;? ?aux =?new?Comparable[n];? ?for?(int?sz =?1; sz < n; sz += sz) {? ? ? ?for?(int?l =?0; l < n - sz; l += sz + sz) {? ? ? ? ? ?// 對于arr[mid] <= arr[mid+1]的情況,不進(jìn)行merge? ? ? ? ? ?if?(arr[l + sz -?1].compareTo(arr[l + sz]) >?0)? ? ? ? ? ? ? ?merge(arr, l, l + sz -?1,? ? ? ? ? ? ? ? ? ? ? ?Math.min(l + sz + sz -?1, n -?1));? ? ? ?}? ?}}

歸并排序特點

快速排序

快速排序?qū)⒁粋€序列分成兩個子序列，兩部分獨(dú)立地排序。

步驟：

Python3 版本

def?sort(lst):? ?"""? ?對序列所有元素進(jìn)行隨機(jī)排序? ?"""? ?sort_next(lst,?0, len(lst) -?1)def?sort_next(lst, l, r):? ?"""? ?快速排序? ?"""? ?if?r <= l:? ? ? ?return? ?p = partition(lst, l, r) ?#切分? ?sort_next(lst, l, p -?1) ?#將左半部分 lst[l...p-1] 排序? ?sort_next(lst, p +?1, r) ?#將右半部分 lst[p+1...r] 排序def?partition(lst, l, r):? ?"""? ?將序列切分為 lst[l...p-1], lst[p], lst[p+1, r]? ?"""? ?v = lst[l]? ?j = l? ?for?i?in?range(l +?1, r +?1):? ? ? ?if?lst[i] < v:? ? ? ? ? ?j +=?1? ? ? ? ? ?lst[j], lst[i] = lst[i], lst[j]? ?lst[l], lst[j] = lst[j], lst[l]? ?return?j

Java 版本

public?class?QuickSort?{? ?public?static?void?newSort(Comparable[] arr)?{? ? ? ?newSort(arr,?0, arr.length -?1);? ?}? ?public?static?void?newSort(Comparable[] arr,?int?l,?int?r)?{? ? ? ?if?(l >= r)?return;? ? ? ?int?p = partition(arr, l, r);?//切分? ? ? ?newSort(arr, l, p -?1);?//將左半部分 arr[l...p-1] 排序? ? ? ?newSort(arr, p +?1, r);?//將右半部分 arr[p+1...r] 排序? ?}? ?//將序列切分為 arr[l...p-1], arr[p], arr[p+1, r]? ?public?static?int?partition(Comparable[] arr,?int?l,?int?r)?{? ? ? ?Comparable v = arr[l];? ? ? ?int?j = l;? ? ? ?for?(int?i = l +?1; i <= r; i++) {? ? ? ? ? ?if?(arr[i].compareTo(v) <?0) {? ? ? ? ? ? ? ?j++;? ? ? ? ? ? ? ?swap(arr, i, j);? ? ? ? ? ?}? ? ? ?}? ? ? ?swap(arr, l, j);? ? ? ?return?j;? ?}? ?//交換數(shù)組中兩個數(shù)? ?public?static?void?swap(Object[] arr,?int?index1,?int?index2)?{? ? ? ?Object temp = arr[index1];? ? ? ?arr[index1] = arr[index2];? ? ? ?arr[index2] = temp;? ?}}

算法改進(jìn)——保持序列的隨機(jī)性

快速排序的最好情況是每次都正好將序列對半分，但對于一個趨近有序的序列，會出現(xiàn)切分不平衡的情況，使得算法極為低效。此時打亂原有序列的順序便能預(yù)防這種情況。

random.shuffle(lst)

StdRandom.shuffle(arr);

算法改進(jìn)——雙路快速排序

改進(jìn)快速排序的第二個方法是使用雙路快速排序，其切分部分在選定一個基準(zhǔn)后，會從序列左端開始向右掃描直到找到一個大于等于它的元素，再從序列右端開始向左掃描直到找到一個小于等于它的元素，交換這兩個元素，如此繼續(xù)。

Python3 版本

def?partition(lst, l, r):? ?"""? ?將序列切分為 lst[l...p-1], lst[p], lst[p+1, r]? ?"""? ?v = lst[l]? ?i, j = l, r +?1? ?while?True:? ? ? ?i +=?1? ? ? ?j -=?1? ? ? ?while?i <= r?and?lst[i] < v:? ? ? ? ? ?i +=?1? ? ? ?while?j >= l?and?lst[j] > v:? ? ? ? ? ?j -=?1? ? ? ?if?i >= j:? ? ? ? ? ?break? ? ? ?lst[i], lst[j] = lst[j], lst[i]? ?lst[l], lst[j] = lst[j], lst[l]? ?return?j

Java 版本

public?static?int?partition(Comparable[] arr,?int?l,?int?r)?{? ?Comparable v = arr[l];? ?int?i = l, j = r +?1;? ?while?(true) {? ? ? ?while?(arr[++i].compareTo(v) <?0?&& i <= r);? ? ? ?while?(arr[--j].compareTo(v) >?0?&& j >= l);? ? ? ?if?(i >= j)?break;? ? ? ?swap(arr, i, j);? ?}? ?swap(arr, l, j);? ?return?j;}

算法改進(jìn)——三路快速排序

改進(jìn)快速排序的第三種方法是使用三路快速排序，其將序列分為切分為三個部分，分別對應(yīng)小于、等于和大于切分元素的序列元素，再對小于和大于部分進(jìn)行遞歸排序。

Python3 版本

def?sort_next(lst, l, r):? ?if?r <= l:? ? ? ?return? ?v = lst[l]? ?lt = l ?# lst[l+1...lt] < v? ?i = l +?1??# lst[lt+1...i] = v? ?gt = r +?1??# lst[i+1...h] > v? ?while?i < gt:? ? ? ?if?lst[i] < v:? ? ? ? ? ?lst[lt +?1], lst[i] = lst[i], lst[lt +?1]? ? ? ? ? ?i +=?1? ? ? ? ? ?lt +=?1? ? ? ?elif?lst[i] > v:? ? ? ? ? ?lst[gt -?1], lst[i] = lst[i], lst[gt -?1]? ? ? ? ? ?gt -=?1? ? ? ?else:? ? ? ? ? ?i +=?1? ?lst[l], lst[lt] = lst[lt], lst[l]? ?sort_next(lst, l, lt -?1) ?#將前半部分 lst[l...lt-1] 排序? ?sort_next(lst, gt, r) ?#將后半部分 lst[gt...r] 排序

Java 版本

public?static?void?newSort(Comparable[] arr,?int?l,?int?r)?{? ?if?(l >= r)?return;? ?int?lt = l, i = l +?1, gt = r +?1;? ?Comparable v = arr[l];? ?while?(i < gt) {? ? ? ?int?cmp = arr[i].compareTo(v);? ? ? ?if?(cmp <?0) swap(arr, ++lt, i++);? ? ? ?else?if?(cmp >?0) swap(arr, --gt, i);? ? ? ?else?i++;? ?}? ?swap(arr, l, lt);? ?newSort(arr, l, lt -?1);?//將左半部分 arr[l...p-1] 排序? ?newSort(arr, gt, r);?//將右半部分 arr[p+1...r] 排序}

快速排序特點

源碼地址

https://github.com/tyrotalk/Algorithms-in-Action/tree/master/02-Sorting-Advance/Code-Python/merge_sort

https://github.com/tyrotalk/Algorithms-in-Action/tree/master/02-Sorting-Advance/Code-Java/mergeSort

https://github.com/tyrotalk/Algorithms-in-Action/tree/master/02-Sorting-Advance/Code-Python/quick_sort

https://github.com/tyrotalk/Algorithms-in-Action/tree/master/02-Sorting-Advance/Code-Java/quickSort

生成海報

免責(zé)聲明：本網(wǎng)站內(nèi)容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準(zhǔn)確性及可靠性，但不保證有關(guān)資料的準(zhǔn)確性及可靠性，讀者在使用前請進(jìn)一步核實，并對任何自主決定的行為負(fù)責(zé)。本網(wǎng)站對有關(guān)資料所引致的錯誤、不確或遺漏，概不負(fù)任何法律責(zé)任。任何單位或個人認(rèn)為本網(wǎng)站中的網(wǎng)頁或鏈接內(nèi)容可能涉嫌侵犯其知識產(chǎn)權(quán)或存在不實內(nèi)容時，應(yīng)及時向本網(wǎng)站提出書面權(quán)利通知或不實情況說明，并提供身份證明、權(quán)屬證明及詳細(xì)侵權(quán)或不實情況證明。本網(wǎng)站在收到上述法律文件后，將會依法盡快聯(lián)系相關(guān)文章源頭核實，溝通刪除相關(guān)內(nèi)容或斷開相關(guān)鏈接。