面試官：堆排序是怎么排的？

大家好，我是道哥。今天我們來聊重要的堆排序。堆排序在面試中是?？嫉膬?nèi)容，而且，堆也常用于處理各種海量數(shù)據(jù)面試題。

我們先看看究竟什么是堆？以大頂堆為例：

對(duì)于一棵完全二叉樹而言，當(dāng)每個(gè)結(jié)點(diǎn)不小于其子結(jié)點(diǎn)時(shí)，便可稱之為堆(大頂堆)，比如：

接下來，我們來圖解堆排序，并用程序來實(shí)現(xiàn)堆排序。在這個(gè)過程中，希望大家感受到堆之美。

圖解堆排序

一. 構(gòu)建堆

第1步：

如上圖，最后一個(gè)非葉子結(jié)點(diǎn)是10，發(fā)現(xiàn)10比70小，所以70必須上浮，得到的結(jié)果為：

第2步：

如上圖，倒數(shù)第二個(gè)非葉子結(jié)點(diǎn)為40，在40，60，80這三個(gè)數(shù)中，80最大，所以80必須上浮，得到的結(jié)果如下：

第3步：

如上圖，倒數(shù)第三個(gè)非葉子結(jié)點(diǎn)為20，而20比70小，所以70必須上浮，20下沉后，發(fā)現(xiàn)比下面的10還大，所以沒有必要沉底，得到的結(jié)果為：

第4步：

如上圖，倒數(shù)第四個(gè)非葉子結(jié)點(diǎn)為30，在30，70，80中，80最大，所以80要上浮，30下沉。然而，30比60和40都小，所以要繼續(xù)下沉，得到的結(jié)果是：

到此為止，可以看到，一個(gè)大頂堆已經(jīng)形成，可以看到，最大的80已經(jīng)被選擇出來了。

二. 調(diào)整堆

我們把堆頂?shù)淖畲笾?0調(diào)整到最后，保存下來，得到的結(jié)果是：

接下來的工作就是對(duì)上面紅框中的的7個(gè)結(jié)點(diǎn)進(jìn)行調(diào)整，使之形成新的堆。

很顯然，根據(jù)之前調(diào)整的過程可知，兩個(gè)藍(lán)色框中的結(jié)點(diǎn)，已經(jīng)分別成堆了，所以這次的調(diào)整就簡(jiǎn)單多了，直接瞄準(zhǔn)待調(diào)整的10即可。

之前已經(jīng)把8個(gè)結(jié)點(diǎn)調(diào)整成堆，那么調(diào)整上面紅色框中的7個(gè)結(jié)點(diǎn)成堆便不在話下。于是，這7個(gè)結(jié)點(diǎn)中最大的70被調(diào)到了堆頂，如下：

80是最大的值，放在最后。堆頂?shù)?0是第二大的值，放在倒數(shù)第二的位置，所以跟40進(jìn)行交換，得到的結(jié)果為：

可見，通過2次從堆頂摘下最大元素，分別把80和70選出來了。接下來，用相同的方法，把60選出來，依此循環(huán)，最后得到的二叉樹為：

終于，實(shí)現(xiàn)了排序，這就是所謂的堆排序，其平均時(shí)間復(fù)雜度為O(N*logN), 比冒泡排序好多啦。

堆排序?qū)崿F(xiàn)

接下來，我們用代碼來實(shí)現(xiàn)堆排序，如下：

#include<iostream>using namespace std;
void print(int a[], int n){  int i;  for(i = 0; i < n; i++)  {    cout << a[i] << " ";  }
  cout << endl;} void heapAdjust(int a[], int low, int high){  int pivotKey = a[low - 1];  int i;  for(i = 2 * low; i <= high; i *= 2)   {    if(i < high && a[i - 1] < a[i])    {      i++; //i指向較大值    }
    if(pivotKey >= a[i - 1])    {      break;    }      a[low - 1] = a[i - 1];    low = i;   }  a[low - 1] = pivotKey; } void heapSort(int a[], int n){  int i, tmp;  for(i = n/2; i > 0; i--)   {    heapAdjust(a, i, n);    print(a, n);  }
  for(i = n; i > 1; i--)  {    tmp = a[i -1];    a[i - 1] = a[0];    a[0] = tmp;    heapAdjust(a, 1, i - 1);     print(a, n);  }}
int main(){  int a[] = {30, 20, 40, 10, 0, 60, 80, 70};  int n = sizeof(a) / sizeof(a[0]);  heapSort(a, n);  print(a, n);  return 0;}

最終的排序結(jié)果如下：

0 10 20 30 40 60 70 80