歸并排序和快速排序用的都是分治的思想,用遞歸的編程技巧來(lái)實(shí)現(xiàn).咱們先來(lái)看歸并排序.
歸并排序
歸并排序的核心思想就是,如果要排序一個(gè)數(shù)組,我們先從中間把數(shù)組分成兩部分,分別對(duì)兩部分排序,然后把排好序的兩部分再合并.
歸并排序的代碼:
merge(A[p...r], A[p...q], A[q+1...r]) {
? var i := p，j := q+1，k := 0 // 初始化變量 i, j, k
? var tmp := new array[0...r-p] // 申請(qǐng)一個(gè)大小跟 A[p...r] 一樣的臨時(shí)數(shù)組
? while i<=q AND j<=r do {
? ? if A[i] <= A[j] {
? ? ? tmp[k++] = A[i++] // i++ 等于 i:=i+1
? ? } else {
? ? ? tmp[k++] = A[j++]
? ? }
? }
? // 判斷哪個(gè)子數(shù)組中有剩余的數(shù)據(jù)
? var start := i菇夸，end := q
? if j<=r then start := j, end:=r
? // 將剩余的數(shù)據(jù)拷貝到臨時(shí)數(shù)組 tmp
? while start <= end do {
? ? tmp[k++] = A[start++]
? }
? // 將 tmp 中的數(shù)組拷貝回 A[p...r]
? for i:=0 to r-p do {
? ? A[p+i] = tmp[i]
? }
}
歸并排序的性能分析:
1,歸并排序是穩(wěn)定的排序算法
2.歸并排序的時(shí)間復(fù)雜度非常穩(wěn)定,不管是最好情況,還是最壞情況,平均情況,時(shí)間復(fù)雜度都是O(nlogn)
3.歸并排序的空間復(fù)雜度是O(n)
快速排序
快速排序的思想:如果要排序數(shù)組中下標(biāo)從p到r的一組數(shù)據(jù),我們選擇p到r中的任意一點(diǎn)數(shù)據(jù)作為pivot(分區(qū)點(diǎn)).我們遍歷 p 到 r 之間的數(shù)據(jù)沮榜，將小于 pivot 的放到左邊贰谣，將大于 pivot 的放到右邊胀葱，將 pivot 放到中間誓禁。經(jīng)過(guò)這一步驟之后雅任，數(shù)組 p 到 r 之間數(shù)據(jù)就被分成了三個(gè)部分,前面 p 到 q-1 之間都是小于 pivot 的风范，中間是 pivot，后面的 q+1 到 r 之間是大于 pivot的
實(shí)現(xiàn)代碼:
// 快速排序沪么，A 是數(shù)組硼婿，n 表示數(shù)組的大小
quick_sort(A, n) {
? quick_sort_c(A, 0, n-1)
}
// 快速排序遞歸函數(shù)，p,r 為下標(biāo)
quick_sort_c(A, p, r) {
? if p >= r then return
? q = partition(A, p, r) // 獲取分區(qū)點(diǎn)
? quick_sort_c(A, p, q-1)
? quick_sort_c(A, q+1, r)
}
如果這樣實(shí)現(xiàn)的話,空間復(fù)雜度就不是O(1),那么快排就不是原地排序算法了,如果讓他是原地排序,可以這樣.
partition(A, p, r) {
? pivot := A[r]
? i := p
? for j := p to r-1 do {
? ? if A[j] < pivot {
? ? ? swap A[i] with A[j]
? ? ? i := i+1
? ? }
? }
? swap A[i] with A[r]
? return I
歸并排序和快速排序的區(qū)別
1,快排是原地,不穩(wěn)定的排序算法,時(shí)間復(fù)雜度為O(nlogn)
