[[415242]]

本文轉(zhuǎn)載自微信公眾號「roseduan寫字的地方」，作者roseduan。轉(zhuǎn)載本文請聯(lián)系roseduan寫字的地方公眾號。

這篇文章再來看看幾種在實踐當(dāng)中更加常用、也更加復(fù)雜一點的排序算法，分別是希爾排序、堆排序、快速排序、歸并排序。

1、希爾排序

希爾排序其實是對插入排序的一種優(yōu)化，回想一下，插入排序的流程是：將數(shù)據(jù)分為了已排序區(qū)間和未排序區(qū)間，依次遍歷未排序區(qū)間的值，將其插入到已排序區(qū)間合適的位置。

插入排序的一個最大的缺點是：每次只能移動一位，這樣在一些極端的情況下會非常低效;例如數(shù)據(jù) 2 3 5 7 9 0，如果將 0 移動至元素頭部，需要遍歷整個數(shù)組。

希爾排序的優(yōu)化點就在于此，它的核心思想是將數(shù)據(jù)中的元素分為了多個組，每一組分別進(jìn)行插入排序。

舉一個簡單的例子：有數(shù)據(jù) 35 33 42 10 14 19 27 44，首先將數(shù)據(jù)以其長度的 1/2 (也就是 4)為步長，分為了四個組，分別是 {35,14}、{33,19}、{42,27}、{10,44}。

然后對每一組分別進(jìn)行插入排序，排序后的結(jié)果如下：

然后步長縮小一半，變?yōu)?2 ，將數(shù)組分為了兩個組，分別是 {14,27,35,42}、{19,10,33,44}：

然后再分別對這兩個組進(jìn)行插入排序，結(jié)果就是 14 10 27 19 35 33 42 44。

最后，步長再縮小一半，變?yōu)?1，將數(shù)組分為了一個組(其實就是數(shù)組本身)，并再進(jìn)行插入排序，這樣希爾排序的流程便完成了。

可以看到，希爾排序?qū)?shù)組分為了多個組，其實是為了盡可能的將數(shù)據(jù)變得局部有序，代碼如下：

func ShellSort(data []int) { 
   length := len(data) 
   step := length / 2 
   for step >= 1 { 
      for i := 0; i < length-step; i++ { 
         j, k := i+step, data[i+step] 
         for ; j > step-1 && data[j-step] > k; j -= step { 
            data[j] = data[j-step] 
         } 
         data[j] = k 
      } 
      step /= 2 
   } 
} 

希爾排序?qū)嶋H應(yīng)用并不是很多，它的相關(guān)復(fù)雜度如下：

 

Time Complexity
Best	O(nlog n)
Worst	O(n2)
Average	O(nlog n)
Space Complexity	O(1)
Stability	no

2、堆排序

要理解堆排序，必須得先明白什么是二叉堆。二叉堆(以下簡稱堆)是一種很優(yōu)雅的數(shù)據(jù)結(jié)構(gòu)，它是一種特殊的二叉樹，滿足二叉樹的兩個特性便可以叫做堆：

• 是一個完全二叉樹
• 堆中任意一個節(jié)點的值都必須大于等于(或者小于等于)其子樹中的所有節(jié)點值

對于節(jié)點大于等于子樹中節(jié)點值的堆，叫做大頂堆，反之則叫做小頂堆，以下是兩個堆的例子：

從定義和上圖中可以看到，堆的一個特點是，堆頂元素就是堆中最大(或最小)的元素。

堆其實可以使用數(shù)組來存儲，堆頂元素就是數(shù)組的第一個元素，并且對于任意下標(biāo)為 i 的節(jié)點，其左子節(jié)點是 2 * i + 1，右子節(jié)點是 2 * i + 2，有了這個對應(yīng)關(guān)系，堆在數(shù)組中的存儲就是這樣的：

理解了什么是堆之后，接下來進(jìn)入正題，看看如何基于堆實現(xiàn)排序。堆排序的步驟一般有兩個，分別是構(gòu)造堆和排序，下面依次介紹。

構(gòu)造堆

構(gòu)造堆指的是將無序的數(shù)組構(gòu)造成堆(這里使用大頂堆進(jìn)行講解)，使其符合堆的特征，舉一個例子，對于一個完全無序的數(shù)組，其原始狀態(tài)和存儲結(jié)構(gòu)如下圖：

要使其變成大頂堆，我們可以這樣做：從第一個非葉子節(jié)點開始，依次將其和子節(jié)點的值進(jìn)行比較，如果小于子節(jié)點的值，交換節(jié)點順序，然后再依次比較下去，直到葉子節(jié)點。

這樣就能夠始終滿足堆的特性，任意節(jié)點的值總是大于其子樹中所有節(jié)點的值。

排序

堆構(gòu)建完成之后就是排序了，前面提到了堆有一個很重要的特性，那就是堆頂元素就是最大的元素，我們遍歷數(shù)組的長度，每次都取堆頂?shù)脑?下標(biāo)為 0 的元素)，將其和數(shù)組最后的元素交換位置，然后重新將剩下的數(shù)據(jù)組織成堆，繼續(xù)取堆頂?shù)淖畲笤兀源祟愅啤?/p>

將兩個步驟結(jié)合起來，就是堆排序的完整實現(xiàn)了，代碼如下：

// 堆排序 
func HeapSort(data []int) { 
   // 構(gòu)建堆 
   length := len(data) 
   for i := (length - 2) / 2; i >= 0; i-- { 
      heapify(data, length, i) 
   } 
 
   // 排序 
   for length > 0 { 
      length-- 
      data[length], data[0] = data[0], data[length] 
      heapify(data, length, 0) 
   } 
} 
 
func heapify(data []int, size, i int) { 
   for { 
      max := i 
      if 2*i+1 < size && data[2*i+1] > data[max] { 
         max = 2*i + 1 
      } 
      if 2*i+2 < size && data[2*i+2] > data[max] { 
         max = 2*i + 2 
      } 
      if i == max { 
         break 
      } 
      data[i], data[max] = data[max], data[i] 
      i = max 
   } 
} 

相關(guān)復(fù)雜度如下： 

Time Complexity
Best	O(nlog n)
Worst	O(nlog n)
Average	O(nlog n)
Space Complexity	O(1)
Stability	No

歸并排序

歸并排序基于分治思想。

分治，顧名思義就是分而治之，它是一種解決問題的思路，將原始問題分解為多個相同或相似的子問題，然后將子問題解決，并將子問題的求得的解進(jìn)行合并，這樣原問題就能夠得到解決了。

分治思想是很多復(fù)雜算法的基礎(chǔ)，例如歸并排序、快速排序、二分查找等等。

言歸正傳，再來看歸并排序，它的概念理解起來非常簡單，如果我們要對一組數(shù)據(jù)進(jìn)行排序，我們可以將這個數(shù)組分為兩個子數(shù)組，子數(shù)組再進(jìn)行分組，這樣子數(shù)組排序之后，將結(jié)果合并起來，就能夠得到原始數(shù)據(jù)排序的結(jié)果。

下面這張圖展示了將一個問題分解為多個子問題的過程：

子問題得到解決之后，需要將結(jié)果合并，合并的過程如下圖：

代碼實現(xiàn)如下：

//歸并排序 
func MergeSort(data []int) { 
   mergeSortHelper(data, 0, len(data)-1) 
} 
 
func mergeSortHelper(data []int, lo, hi int) { 
   if lo < hi { 
      mid := lo + (hi-lo)/2 
      mergeSortHelper(data, lo, mid) 
      mergeSortHelper(data, mid+1, hi) 
      merge(data, lo, mid, hi) 
   } 
} 
 
func merge(data []int, lo, mid, hi int) { 
   temp := make([]int, hi-lo+1) 
   i, j, k := lo, mid+1, 0 
   for i <= mid && j <= hi { 
      if data[i] < data[j] { 
         temp[k] = data[i] 
         i++ 
      } else { 
         temp[k] = data[j] 
         j++ 
      } 
      k++ 
   } 
   copy(temp[k:], data[i:mid+1]) 
   copy(temp[k:], data[j:hi+1]) 
   copy(data[lo:hi+1], temp[:]) 
} 

相關(guān)復(fù)雜度如下：

 

Time Complexity
Best	O(n*log n)
Worst	O(n*log n)
Average	O(n*log n)
Space Complexity	O(n)
Stability	Yes

3、快速排序

快速排序通常叫做“快排”，它應(yīng)該是應(yīng)用最廣泛的一個排序算法了，很多編程語言內(nèi)置的排序方法，都或多或少使用到了快速排序，因為快速排序的時間復(fù)雜度可以達(dá)到 O(nlogn)，并且是原地排序，前面介紹的幾種排序算法都無法將這兩個優(yōu)點結(jié)合起來。

快排和歸并排序類似，都采用了分治思想，但是它的解決思路卻和歸并排序不太一樣。

如果要排序一個數(shù)組，我們可以從數(shù)組中選擇一個數(shù)據(jù)，做為分區(qū)點(pivot)，然后將小于分區(qū)點的放到分區(qū)點的左側(cè)，大于分區(qū)點的放到其右側(cè)，然后對于分區(qū)點左右兩邊的數(shù)據(jù)，繼續(xù)采用這種分區(qū)的方式，直到數(shù)組完全有序。

概念讀起來可能有點抽象，這里我畫了一張圖來幫助你理解整個排序的過程：

上圖展示了第一次分區(qū)的過程，假設(shè)要排序的數(shù)組的下標(biāo)是 p ~ r，我們?nèi)?shù)組的最后一個元素 5 做為分區(qū)點，然后比 5 小的數(shù)字 0 3 1 2 移動到 5 的左邊，比 5 大的數(shù)字 9 6 8 7 移動到 5 的右邊。

然后以數(shù)字 5 為分界點，其左邊的數(shù)字(下標(biāo)為 p ~ q - 1)，以及右邊的數(shù)字(下標(biāo)為 q + 1 ~ r)，分別再進(jìn)行同樣的分區(qū)操作，一直分下去，直到數(shù)組完全有序，如下圖：

下面的動圖展示了快速排序的完整過程(注意動圖中是選擇第一個元素做為分區(qū)點的)：

如果使用一個簡單的公式來表示快速排序，可以寫成這樣：

int q = partition(data, p, r); 
quick_sort(data, p, r) = quick_sort(data, p, q - 1) + quick_sort(data, q + 1, r); 

這里有一個 partition 分區(qū)函數(shù)，它的作用是選擇一個分區(qū)點，并且將小于分區(qū)點的數(shù)據(jù)放到其左邊，大于分區(qū)點的放到其右邊，然后返回分區(qū)點的下標(biāo)。

其實這個 partition 分區(qū)函數(shù)是快速排序?qū)崿F(xiàn)的關(guān)鍵，那究竟怎么實現(xiàn)這個函數(shù)呢?很容易想到的一種方式是：直接遍歷一次原數(shù)組，依次取出小于和大于分區(qū)點的數(shù)據(jù)，將其各自存放到一個臨時數(shù)組中，然后再依次拷貝回原數(shù)組中，過程如下圖：

這樣做雖然簡單，但是存在一個缺陷，那就是每次分區(qū)都會使用額外的存儲空間，這會導(dǎo)致快速排序的空間復(fù)雜度為 O(n)，那么就不是原地排序了。

所以快速排序使用了另一種方式來實現(xiàn)分區(qū)，并且沒有借助額外的存儲空間，它是怎么實現(xiàn)的呢?我還是畫了一張圖來幫助你理解：

聲明了兩個指針 i 和 j，從數(shù)組的最開始處向后移動，這里的移動規(guī)則有兩個：

• 一是如果 j 所在元素大于分區(qū)點，那么 j 向后移動一位，i 不變;
• 二是如果 j 所在元素小于分區(qū)點，那么交換 i 和 j 所在元素，然后 i 和 將 j 同時向后移動一位。

終止的條件是 j 移動至數(shù)組末尾，然后交換分區(qū)點和 i 所在的元素，i 就是分區(qū)點的下標(biāo)。

理解了這個過程之后，再來看快速排序的代碼實現(xiàn)，就會非常的簡單了，下面是一個示例：

func QuickSort(data []int) { 
  quickSortHelper(data, 0, len(data)-1) 
} 
 
func quickSortHelper(data []int, lo, hi int) { 
  if lo < hi { 
    mid := partition(data, lo, hi) 
    quickSortHelper(data, lo, mid-1) 
    quickSortHelper(data, mid+1, hi) 
  } 
} 
 
func partition(data []int, lo, hi int) int { 
  pivot, i, j := data[hi], lo, lo 
  for j < hi { 
    if data[j] < pivot { 
      data[j], data[i] = data[i], data[j] 
      i++ 
    } 
    j++ 
  } 
  data[i], data[hi] = data[hi], data[i] 
  return i 
} 

快速排序相關(guān)復(fù)雜度如下：

Time Complexity
Best	O(n*log n)
Worst	O(n2)
Average	O(n*log n)
Space Complexity	O(log n)
Stability	No

文中的全部代碼可在我的 Github 上查看：https://github.com/roseduan/Go-Algorithm