介紹常見的排序演算法：冒泡排序、選擇排序、插入排序、歸併排序、快速排序及簡單的性能測試。 ...
JavaScrip 排序演算法（JavaScript Sorting Algorithms）
基礎構造函數
以下幾種排序演算法做為方法放在構造函數里。
function ArrayList () {
var array = [];
// 交換位置
var swap = function (index1, index2) {
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
}
this.insert = function (item) {
array.push(item);
};
this.toString = function () {
return array.join();
};
this.val = function () {
return array;
}
// 冒泡排序
this.bubbleSort = function () {
//etc
}
}1. 冒泡排序
冒泡排序比較任何兩個相鄰的項，如果第一個比第二個大，則交換它們。
複雜度 O(n^2)。
代碼
this.bubbleSort = function () {
console.time('Bubble Sort');
var length = array.length;
for (var i = 0; i < length; i++) {
for (var j = 0; j < length - 1 - i; j++) {
if (array[j] > array[j+1]) {
swap(j, j + 1);
}
}
}
console.timeEnd('Bubble Sort');
}圖解
2. 選擇排序
選擇排序演算法是一種原址比較排序演算法。選擇排序大致的思路是找到數據結構中的最小值並將其放置在第一位，接著找到第二小的值並將其放在第二位，以此類推。
複雜度：O(n^2)。
代碼
this.selectionSort = function () {
console.time('selectionSort');
var length = array.length,
indexMin;
for (var i = 0; i < length - 1; i++) {
indexMin = i;
for (var j = i; j < length; j++) {
if (array[indexMin] > array[j]) {
indexMin = j;
}
}
if (i !== indexMin) {
swap(i, indexMin);
}
}
console.timeEnd('selectionSort');
}圖解
3. 插入排序
插入排序每次排一個數組項，以此方式構建最後的排序數組。假定第一項已經排序了，接著，它和第二項進行比較，第二項是應該待在原位還是插到第一項之前呢？這樣，頭兩項就已正確排序，接著和第三項比較（它是該插入到第一、第二還是第三的位置呢？），以此類推。
排序小型數組時，此演算法比選擇排序和冒泡排序性能要好。
代碼
this.insertionSort = function () {
console.time('insertionSort');
var length = array.length,
j, temp;
for (var i = 1; i < length; i++) {
j = i;
temp = array[i];
while (j > 0 && array[j-1] > temp) {
array[j] = array[j-1];
j--;
}
array[j] = temp;
}
console.timeEnd('insertionSort');
}圖解
4. 歸併排序
歸併排序是一種分治演算法。其思想是將原始數組切分成較小的數組，直到每個小數組只有一個位置，接著將小數組歸併成較大的數組，直到最後只有一個排序完畢的大數組。
複雜度：O(n log^n)。
代碼
this.mergeSort = function () {
console.time('mergeSort');
array = mergeSortRec(array);
console.timeEnd('mergeSort');
}
var mergeSortRec = function (array) {
var length = array.length;
if (length === 1) {
return array;
}
var mid = Math.floor(length / 2),
left = array.slice(0, mid),
right = array.slice(mid, length);
return merge(mergeSortRec(left), mergeSortRec(right));
}
var merge = function (left, right) {
var result = [],
il = 0,
ir = 0;
while (il < left.length && ir < right.length) {
if (left[il] < right[ir]) {
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
while (il < left.length) {
result.push(left[il++]);
}
while (ir < right.length) {
result.push(right[ir++]);
}
return result;
}圖解
5. 快速排序
歸併排序一樣，快速排序也使用分治的方法，將原始數組分為較小的數組（但它沒有像歸併排序那樣將它們分割開）。
它的性能通常比其他的複雜度為O(n log^n)的排序演算法要好。
複雜度：O(n log^n)。
代碼
this.quickSort = function () {
console.time('quickSort');
quick(array, 0, array.length - 1);
console.timeEnd('quickSort');
}
var quick = function (array, left, right) {
var index;
if (array.length > 1) {
index = partition(array, left, right);
if (left < index - 1) {
quick(array, left, index - 1);
}
if (index < right) {
quick(array, index, right);
}
}
};
// 劃分過程
var partition = function (array, left, right) {
var pivot = array[Math.floor((right + left) / 2)],
i = left,
j = right;
while (i < j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swapQuickSort(array, i, j);
i++;
j--;
}
}
return i;
}
var swapQuickSort = function (array, index1, index2) {
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
}圖解
6. ECMAScript 排序
ECMAScript沒有定義用哪個排序演算法，所以瀏覽器廠商可以自行去實現演算法。例如，Mozilla Firefox使用歸併排序作為Array.prototype.sort的實現，而Chrome使用了一個快速排序（下麵我們會學習的）的變體。
this.esSort = function () {
console.time('esSort');
var tempArray = [];
tempArray = array.sort(function (a, b) {
return a - b;
});
console.timeEnd('esSort');
return tempArray;
}性能測試
環境
OS：WIN10 64位
瀏覽器：Google Chrome 60.0.3112.78
代碼
/**
* 創建隨機數組
* @param {[type]} size [description]
* @return {[type]} [description]
*/
function createNonSortedArray (size) {
var array = new ArrayList();
for (var i = size; i > 0; i--) {
var tempNum = Math.random() * i >>> 0;
array.insert(tempNum);
}
return array;
}
// 冒泡排序
(function () {
var array = createNonSortedArray(500);
array.bubbleSort(); // Bubble Sort: 2.625ms
console.log(array.val());
}());
// 選擇排序
(function () {
var array = createNonSortedArray(500);
array.selectionSort(); // selectionSort: 1.986083984375ms
console.log(array.val());
}());
// 插入排序
(function () {
var array = createNonSortedArray(500);
array.insertionSort(); // insertionSort: 1.825927734375ms
console.log(array.val());
}());
// 歸併排序
(function () {
var array = createNonSortedArray(500);
array.mergeSort(); // mergeSort: 0.76416015625ms
console.log(array.val());
}());
// 快速排序
(function () {
var array = createNonSortedArray(500);
array.quickSort(); // quickSort: 0.39111328125ms
console.log(array.val());
}());
// ES排序
(function () {
var array = createNonSortedArray(500);
array.esSort(); // esSort: 0.34130859375ms
console.log(array.val());
}());由此可見，一般情況我們只需要使用
JavaScript提供的Array.prototype.sort()方法即可，瀏覽器（或宿主環境）會在底層採用最優演算法幫我們實現排序。
來源/參考
- 《學習 javascript 數據結構》
- About the #sorting-algorithms series
- https://github.com/benoitvallon/computer-science-in-javascript/tree/master/sorting-algorithms-in-javascript
