DIV CSS 佈局教程網

JavaScript 幾種經典排序算法的實現
編輯:JavaScript基礎知識     

排序算法的實現
我的 JS 水平一般,所以就用類似 Java 和 C 的方式來寫 JavaScript 排序算法了。這裡不講算法原理,僅做代碼實現,可能有 Bug,歡迎大家指正。

插入排序
插入排序(Insertion-Sort)是一種簡單直觀的算法。它的工作原理是通過構建有序序列:對未排序數據,在已排序序列中從後向前掃描,找到相應位置並插入。它通常采用 in-place 排序(只需 O(1) 額外空間),因此從後向前掃描時需反覆把已排序元素向後挪位,為新元素騰出插入空間。

實現如下:

 function insertSort(arr) { if (!arr) return; var len = arr.length; if (len == 0 || len == 1) return; for (var i = 1, len = arr.length; i < len; i ++) { var stand = arr[i]; for (var j = i - 1; j >= 0; j --) { if (arr[j] > stand) { arr[j + 1] = arr[j]; } else { arr[j + 1] = stand; break; } } } return arr; } 

時間複雜度為 O(n^2)。當然它有優化餘地,例如把查找插入位置的算法改為二分查找。

冒泡排序
經典算法,提到冒泡排序我就心痛——本科時必修論文寫的就是冒泡排序改進,結果寫完論文後都不能完整實現它,頗為尷尬。

 function bubbleSort(arr) { if (!arr) return; var len = arr.length; if (len == 0 || len == 1) return; for (var i = 0; i < len; i ++) { for (var j = 0; j < len - i - 1; j ++) { if (arr[j] > arr[j + 1]) { var tmp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = tmp; } } } return arr; } 

時間複雜度為 O(n^2)。

快速排序
非常經典,過程主要分三步:

  1. 從數列中挑出一個元素,稱為「基準」(pivot);
  2. 重新排序數列,比基準小的放前面,比基準大的放後面(相同的可到任一邊)。分區退出後,基準就處於中間位置,這稱為分區(partition)操作;
  3. 遞歸地對小於基準和大於基準的子數列排序。

實現如下:

 function quickSort(arr, bt, ed) { if (bt < ed) { var pivot = findPartition(arr, bt, ed); quickSort(arr, bt, pivot - 1); quickSort(arr, pivot + 1, ed); } } function findPartition(arr, bt, ed) { var stand = arr[bt]; while (bt < ed) { while (bt < ed && arr[ed] >= stand) { ed --; } if (bt < ed) { arr[bt ++] = arr[ed]; } while (bt < ed && arr[bt] <= stand) { bt ++; } if (bt < ed) { arr[ed --] = arr[bt]; } } arr[bt] = stand; return bt; } 

時間複雜度為 O(nlogn)。

歸並排序
也是經典算法,我藉著學 js 的機會復習了一遍。歸並排序的思想可參考相關資料,這裡只寫 js 實現。

 function mergeSort(arr, bt, ed) { if (bt < ed) { var mid = bt + parseInt((ed - bt) / 2); mergeSort(arr, bt, mid); mergeSort(arr, mid + 1, ed); mergeArray(arr, bt, mid, ed); } } function mergeArray(arr, bt, mid, ed) { var mArr = []; var i = bt, j = mid + 1; while (i <= mid && j <= ed) { if (arr[i] <= arr[j]) { mArr.push(arr[i++]); } else { mArr.push(arr[j ++]); } } if (i <= mid) { mArr = mArr.concat(arr.slice(i, mid + 1)); } if (j <= ed) { mArr = mArr.concat(arr.slice(j, ed + 1)); } for (var h = 0; h < mArr.length; h ++) { arr[bt + h] = mArr[h]; } } 

寫歸並排序時還有個小插曲:js 不能自動取整,後來用了 parseInt 方法,感覺萌萌噠。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved