javaScript實作歸并排序

歸并排序是一個O(nlogn)的算法，其基本思想就是一個分治的政策，先進行劃分，然後再進行合并，下面舉個例子。有這樣一組資料：

   {5,4,1,22,12,32,45,21}

  如果對它進行歸并排序的話，首先将它從中間分開，這樣，它就被分成了兩個數組：

   {5,4,1,22}與 {12,32,45,21}

  對這兩個數組，也分别進行這樣的操作，逐漸的劃分，直到不能再劃分為止(每個子數組隻剩下一個元素)，這樣，劃分的過程就結束了。

劃分的過程如下圖所示：

  接下來，我們進行歸并操作，依照上圖，劃分過程是從上到下進行的，而歸并的過程是從下往上進行的，例如上圖中,最下層{5},{4}這兩個數組，如果按升序排列，将他們合并後的數組就是{4,5}。{1}，{22}這兩個子數組合并後是{1,22}。而{4,5}與{1,22}，這兩個數組同屬一個分支，他們也需要進行合并，由于這兩個子數組本身就是有序的，是以合并的過程就是，每次從待合并的兩個子數組中選取一個最小的元素，然後把這個元素放到合并後的數組中，前面兩個數組合并後就是{1,4,5,22}。依次類推，直到合并到最上層結束，這是資料的排序已經完成了。

歸并的過程如下圖所示。這個過程是從下往上的。

   它是一個在效率上高于一般排序的算法.一般排序:冒泡, 插入, 選擇排序的時間複雜度為O(N^2), 而歸并排序的時間複雜度為O(N*LOG N)，如果N(及排序項的數目)是10000.那麼N^2就是100000000, 而N * LOG N則是40000. 也就是如果這個數量的資料.如果用歸并排序需要40S的時間,那麼用插入排序則需要28個小時.

歸并排序算法的核心:

   核心思想就是分治算法.先進行劃分,再進行排序歸并.歸并兩個有序的數組.即歸并兩個有序的數組A和B,然後就有了包含這兩個新數組的數組C.

  即一次拿出A和B的數組項進行比較.小的就插入到新容器C中.直到一方已經插入完畢.如果另一方還有剩餘那麼就表示剩餘的是有序的而且比較大的.那麼就直接連接配接到C數組容易的後面即可.

代碼:

<script>

</script>