聊一聊排序算法

兩月前花了些時間，将大學裡學過的排序算法都複習了一遍，代碼放在 github 上，沒有整理。今天翻了翻代碼，重新 review 了一遍，也順便做了點記錄。

下面花了不少篇幅，将基礎排序、希爾、歸并、快排、堆排序等都介紹了一通，懶得思考的同學可以略過代碼直接看文字，文章對排序的基本思路都做了介紹。

本文的代碼可以在這裡找到：https://github.com/barretlee/algorithms

三種基本排序

插入排序和選擇排序是兩種最基本的排序算法，思路完全不一樣，但是細思一番，還是挺有意思的：

insertion sort

，插入排序，思路簡單來說就是把自己插入到已排好序的清單中去，交換也是頗為頻繁的。

function insertion(input) {
  for(var i = 1, len = input.length; i < len; i++) {
    for(var j = i; j > 0; j--) {
      if(input[j] < input[j - 1]) {
        input[j] = [input[j - 1], input[j - 1] = input[j]][0];
      }
    }
  }
  return input;
}

selection sort

，選擇排序，選擇排序隻對最後一個被選中的元素排序。它會往後找到包括自己在内最小的一個元素，替換自己。簡單來說就是把第 i 小的元素放到第 i 個序位上。

function selection(input) {
  for(var i = 0, len = input.length; i < len - 1; i++) {
    var min = i;
    for(var j = i + 1; j < len; j++) {
      if(input[j] < input[min]) {
        min = j;
      }
    }
    input[i] = [input[min], input[min] = input[i]][0];
  }
  return input;
}

而冒泡排序，就更簡單了，從第一個元素開始，往後比較，遇到比自己小的元素就交換位置，交換的次數最多，自然也是性能最差的。

function bubble(input) {
  for(var i = 0, len = input.length; i < len - 1; i++) {
    for(var j = i + 1; j < len; j++) {
      if(input[j] < input[i]) {
        input[j] = [input[i], input[i] = input[j]][0];
      }
    }
  }
  return input;
}

針對随機性排列不同（比如完全随機，順序，倒序，半順序等狀态）的資料，三種效果也是不一樣的，可以思考下。

希爾排序

上面提到了三種最基本的排序算法，這裡要提到的希爾排序，有點不好了解。

代碼：/chapters/chapter-2-sorting/2.1-elementary-sorts/shell.js

function shell(input) {
  var h = 1;
  var len = input.length;
  while(h < Math.floor(len / 3)) {
    h = h * 3 + 1;
  }
  while(h >= 1) {
    for(var i = h; i < len; i++)  {
      for(var j = i; j >= h; j -= h) {
        if(input[j] < input[j - h]) {
          input[j] = [input[j - h], input[j - h] = input[j]][0];
        }
      }
    }
    h = Math.floor(h / 3);
  }
  return input;
}

算法複雜不代表需要很多的代碼去實作，因為代碼表達的是過程，通過循環等方式可以很迅速實作一個過程，而算法是處理問題的方法，把它表達清楚可能就得費不少唇舌，甚至還得配上一些圖輔助閱讀。

希爾排序，大概的思路就是不斷地從整體上調整資料的順序，将比較大的資料盡量往後挪，比較小的資料盡量往前挪。資料的搬移也不是一步完成，每一次搬移都會将資料分塊，分塊的目的是盡可能的搬移距離比較遠的資料，進而減少比較操作和交換操作。

歸并排序

基本排序和希爾排序是都是從頭到尾去周遊資料，不可避免的帶來很多交換操作。歸并排序是一種用空間換時間的排序算法，一個數組截斷成兩個子數組，子資料排好序後合并到一起。

代碼：/chapters/chapter-2-sorting/2.2-mergesort/merge.js

function merge(input1, input2) {
  var i = 0, j = 0;
  var output = [];
  while(i < input1.length || j < input2.length) {
    if(i == input1.length) {
      output.push(input2[j++]);
      continue;
    }
    if(j == input2.length) {
      output.push(input1[i++]);
      continue;
    }
    if(input1[i] < input2[j]) {
      output.push(input1[i++]);
    } else {
      output.push(input2[j++]);
    }
  }
  return output;
}

上面是一個簡單的合并算法，将兩個有序資料合并為一個。有人應該會想到，既然一個數組可以打散成兩個進行排序，那被打算的子數組是不是也可以繼續被打散呢？

答案是肯定的。這是一種典型的分治思想，遞歸歸并。

代碼：/chapters/chapter-2-sorting/2.2-mergesort/mergeRecursiveTop2Bottom.js

function mergeRecursiveTop2Bottom(input) {

  return sort(input, 0, input.length - 1);

  function sort(arr, start, end) {
    if(start >= end) {
      return;
    }
    var mid = ((end - start) >> 1) + start;
    sort(arr, start, mid);
    sort(arr, mid + 1, end);
    return merge(arr, start, mid, end);
  }

  function merge(arr, start, mid, end) {
    var i = start, j = mid + 1, tmp = [];
    for(var k = start; k <= end; k++) {
      tmp[k] = arr[k];
    }
    for(k = start; k <= end; k++) {
      if(i > mid) {
        arr[k] = tmp[j++];
        continue;
      }
      if(j > end) {
        arr[k] = tmp[i++];
        continue;
      }
      if(tmp[i] < tmp[j]) {
        arr[k] = tmp[i++];
      } else {
        arr[k] = tmp[j++];
      }
    }
    return arr;
  }
}

上面的算法是自頂向下的遞歸歸并，簡單來說就是解決很多小問題，那麼大問題也就自然而然的解決了；還有一種自底向上的歸并，這種歸并簡單來說，就是把一個大問題分解為多個小問題，多個小問題的答案就能得出大問題的答案。從解決問題的方式來看，兩種處理方式是互逆的。

function sort(arr) {
  for(var sz = 1, len = arr.length; sz < len; sz = sz * 2) {
    for(var start = 0; start < len - sz; start += sz * 2) {
      arr = merge(arr, start, start + sz - 1, Math.min(start + sz * 2 - 1, len - 1));
    }
  }
  return arr;
}
// merge 函數同上

不過自底向上的歸并，在代碼上稍微難了解一些，腦海重要有清晰的畫卷，知道程式跑到哪一步了，尤其還需要處理邊界問題。

快排

上面讨論了歸并排序，将一個數組拆分成兩個，然後合并處理，進而有了遞歸歸并的思考。

而本節提出了一種更加高效的排序方法，這種算法跟歸并排序是互補的，歸并排序大緻思路是

分-排序合

，而本節提出的快排采用的思路是

排序分-合

，把排序這種損耗比較大的操作前置了，是以效率更高。

代碼：/chapters/chapter-2-sorting/2.3-quicksort/quicksort.js

function quicksort(input) {
  sort(0, input.length - 1);
  return input;

  function sort(start, end) {
    if(start >= end) {
      return;
    }
    var mid = partition(start, end);
    sort(start, mid - 1);
    sort(mid + 1, end);
  }

  function partition(start, end) {
    var i = start, j = end + 1, k = input[start];
    while(true) {
      while(input[++i] < k) if( i === end) break;
      while(input[--j] > k) if( j === start) break;
      if(i >= j) break;
      input[i] = [input[j], input[j] = input[i]][0];
    }
    input[j] = [input[start], input[start] = input[j]][0];
    return j;
  }
}

這個算法寫起來，感覺相當酸爽，因為這個排序思路太棒，情不自禁地熱血沸騰。事實上，這個算法也是存在幾個疑點的：

代碼中的 mid 這個「哨兵」為啥要取第一個呢？
partition 函數當 end - start 很小的時候效率還高麼？

于是有了兩個想法：

使用 input 的中位數作為「哨兵」
當 end - start 比較小的時候，大約為 5~15，改為其他比較高效的算法

今天隻對第二個想法做了實踐，基本改造如下：

代碼：chapters/chapter-2-sorting/2.3-quicksort/quicksortImprove.js

var delta = 5;
function quicksortImprove(input) {
  sort(0, input.length - 1);
  return input;

  // sort 和 partition 函數同上

  function insertion(start, end) {
    for(var i = start + 1, len = end - start; i < end; i++) {
      for(var j = i; j > start; j--) {
        if(input[j] < input[j - 1]) {
          input[j] = [input[j - 1], input[j - 1] = input[j]][0];
        }
      }
    }
  }
}

優化後的快排

上面提到了快排和快排的改進算法。當待排序的資料中存在大量重複元素時，快排的效率會不太高，當遇到重複元素的時候，比較和交換都是贅餘的，重複元素越多，性能越差，為了解決這個問題，我們引入了第三個變量，來辨別重複元素區間，如下圖所示：

+---------------------------------+
|  <v  |  =v  |=========|   > v   |
+---------------------------------+
       ↑      ↑         ↑
      lt      i         gt

大緻的原理是：每次排序分組的時候，就會過濾掉重複元素，這樣，進入遞歸的元素就少了很多，是以而提高效率。

代碼：/chapters/chapter-2-sorting/2.3-quicksort/quick3way.js

function quick3way(input) {
  sort(0, input.length - 1);
  return input;

  function sort(start, end) {
    if(start >= end) return;

    var lt = start, gt = end, i = start + 1, v = input[start];
    while(i <= gt) {
      if(input[i] < v) {
        input[lt] = [input[i], input[i] = input[lt]][0];
        lt++; i++;
      } else if(input[i] > v) {
        input[gt] = [input[i], input[i] = input[gt]][0];
        gt--;
      } else {
        i++;
      }
    }
    sort(start, lt - 1);
    sort(gt + 1, end);
  }
}

優先隊列，堆排序

從最開始基本的冒泡、插入、選擇和希爾排序，到分治思想的延伸——歸并排序（自頂向下和自底向上），再到歸并排序的互補算法——快排，然後學習了新的資料結構——二叉堆，于是有了堆排序。

二叉堆是一種資料結構，他的每一個二叉樹點元素數值都會比下面兩個節點元素的數值要大，因為這種資料接口包含的資訊量很大，而得到這種資料結構的成本是很低的，建構一個二叉堆的算法并不複雜：

代碼：/chapters/chapter-2-sorting/2.4-priority-queues/priorityQueueAdd.js

function priorityQueueAdd(input) {
  var output = [];

  output[1] = input[0];
  for(var i = 1, len = input.length; i < len; i++) {
    output = swim(output, input[i]);
  }

  return output;

  function swim(arr, val) {
    arr.push(val);
    var k = arr.length - 1;
    while(k > 1 && arr[k >> 1] < arr[k]) {
      var p = k >> 1;
      arr[p] = [arr[k], arr[k] = arr[p]][0];
      k = p;
    }
    return arr;
  }
}

通過上浮的方式，不斷插入新元素，既可形成一個二叉堆。這種優先隊列最大的特點是，能夠拿到很快拿到最大元素（頂部），當這個最大元素被删除（優先級最高的事務被處理完成）時，還能快速高效地将剩下的元素重整為一個二叉堆：

代碼：/chapters/chapter-2-sorting/2.4-priority-queues/priorityQueueDelete.js

function priorityQueueDelete(input) {
  var output = [];

  input.splice(1, 1);
  output = sink(input);

  return output;

  function sink(arr) {
    arr.splice(1, 0, arr.pop());
    var k = 1, N = arr.length - 1;
    while(2 * k <= N) {
      var j = 2 * k;
      if(j < N && arr[j] < arr[j + 1]) j++;
      if(arr[k] >= arr[j]) break;
      arr[k] = [arr[j], arr[j] = arr[k]][0];
      k = j;
    }
    return arr;
  }
}

一個二叉堆能夠快速拿到最大元素，并且能夠立即重新調整為二叉堆，基于這個特性，就有了堆排序：

代碼：/chapters/chapter-2-sorting/2.4-priority-queues/heapSort.js

function heapSort(input) {
  return sort(input);

  function sort (arr){
    var N = arr.length - 1;
    for(var k = N >> 2; k >= 1; k--) {
      arr = sink(arr, k, N);
    }
    while(N > 1) {
      arr[1] = [arr[N], arr[N] = arr[1]][0];
      N--;
      arr = sink(arr, 1, N);
    }
    return arr;
  }
  function sink(arr, k, N) {
    while(2 * k <= N) {
      var j = 2 * k;
      if(j < N && arr[j] < arr[j + 1]) j++;
      if(arr[k] >= arr[j]) break;
      arr[k] = [arr[j], arr[j] = arr[k]][0];
      k = j;
    }
    return arr;
  }
}

光看代碼還是挺難了解的，腦海中必須有一個數組儲存的堆模型。for 循環構造了堆（從 N/2 開始，跳過了所有大小為 1 的堆），注意，這裡構造的并不是二叉堆，然後 while 循環将最大的元素 a[1] 和 a[n] 交換位置并修複堆，如此循環直到堆為空。

上面的排序用到的是 sink 方法，而 swim 方法也是可以用于排序算法之中的，這就是對應的下沉排序，感覺有點難了解。

小結

能夠從上往下看到這裡的，需要給你點個贊。算法的學習剛開始有點枯燥，也有點艱難，學着學着，慢慢的就能夠領悟其中的趣味。

後續我也會投入一部分精力深入研究算法，希望可以通過一定量的算法實踐大幅度提升自己的思維能力和動手能力。

聊一聊排序算法

三種基本排序

希爾排序

歸并排序

快排

優化後的快排

優先隊列，堆排序

小結

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method