JavaScript排序，不只是冒泡
做編程，排序是個必然的需求。前端也不例外，雖然不多，但是你肯定會遇到。
不過說到排序，最容易想到的就是冒泡排序，選擇排序，插入排序了。
冒泡排序
依次比較相鄰的兩個元素，如果后一個小于前一個，則交換，這樣從頭到尾一次，就將***的放到了末尾。
從頭到尾再來一次，由于每進行一輪，***的都已經是***的了，因此后一輪需要比較次數可以比上一次少一個。雖然你還是可以讓他從頭到尾來比較，但是后面的比較是沒有意義的無用功，為了效率，你應該對代碼進行優化。
圖片演示如下：
代碼實現：
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { // 相鄰元素兩兩對比
var temp = arr[j+1]; // 元素交換
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
選擇排序
選擇排序我覺得是最簡單的了，大一學VB的時候，就只記住了這個排序方法，原理非常簡單：每次都找一個***或者最小的排在開始即可。
- 首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置
- 再從剩余未排序元素中繼續尋找最?。ù螅┰?，然后放到已排序序列的末尾。
- 重復第二步，直到所有元素均排序完畢。
動圖演示：
代碼演示：
function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { // 尋找最小的數
minIndex = j; // 將最小數的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
插入排序
插入排序也比較簡單。就像打撲克一樣，依次將拿到的元素插入到正確的位置即可。
- 將***待排序序列***個元素看做一個有序序列，把第二個元素到***一個元素當成是未排序序列。
- 從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。）
動圖演示：
代碼示例：
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
簡單的代價是低效
上面三種都是非常簡單的排序方法，簡單的同時呢，效率也會比較低，還是拿這本書里的對比圖來說明：
時間復雜度都高達O(n^2),而它們后面的一些排序算法時間復雜度基本都只有O(n log n)。
我的強迫癥又犯了，我想要高效率一點的排序方法。
歸并排序
簡單把這本書的內容過了一遍，當時就理解了這個歸并排序，因此這里就談一下這個歸并排序吧。
基本原理是分治法，就是分開并且遞歸來排序。
步驟如下：
- 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列；
- 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；
- 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；
- 重復步驟 3 直到某一指針達到序列尾；
- 將另一序列剩下的所有元素直接復制到合并序列尾。
動圖演示：
代碼示例：
function mergeSort(arr) { // 采用自上而下的遞歸方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
既然是個愛折騰的人，折騰了總得看看效果吧。
效率測試
由于我學這個來進行排序不是對簡單數組，數組內都是對象，要對對象的某個屬性進行排序，還要考慮升降序。
因此我的代碼實現如下：
/** * [歸并排序] * @param {[Array]} arr [要排序的數組] * @param {[String]} prop [排序字段，用于數組成員是對象時，按照其某個屬性進行排序，簡單數組直接排序忽略此參數] * @param {[String]} order [排序方式 省略或asc為升序 否則降序] * @return {[Array]} [排序后數組，新數組，并非在原數組上的修改] */
var mergeSort = (function() {
// 合并
var _merge = function(left, right, prop) {
var result = [];
// 對數組內成員的某個屬性排序
if (prop) {
while (left.length && right.length) {
if (left[0][prop] <= right[0][prop]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
} else {
// 數組成員直接排序
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
};
var _mergeSort = function(arr, prop) { // 采用自上而下的遞歸方法
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return _merge(_mergeSort(left, prop), _mergeSort(right, prop), prop);
};
return function(arr, prop, order) {
var result = _mergeSort(arr, prop);
if (!order || order.toLowerCase() === 'asc') {
// 升序
return result;
} else {
// 降序
var _ = [];
result.forEach(function(item) {
_.unshift(item);
});
return _;
}
};
})();
需要對哪個屬性進行排序是不確定，可以隨意指定，因此寫成了參數。有由于不想讓這些東西在每次循環都進行判斷，因此代碼有點冗余。
關于降序的問題，也沒有加入參數中，而是簡單的升序后再逆序輸出。原因是不想讓每次循環遞歸里都去判斷條件，所以簡單處理了。
下面就是見證效率的時候了，一段數據模擬：
var getData = function() {
return Mock.mock({
"list|1000": [{
name: '@cname',
age: '@integer(0,500)'
}]
}).list;
};
上面使用Mock進行了模擬數據，關于Mock ： http://mockjs.com/
實際測試來啦：
// 效率測試
var arr = getData();
console.time('歸并排序');
mergeSort(arr, 'age');
console.timeEnd('歸并排序');
console.time('冒泡排序');
for (var i = 0, l = arr.length; i < l - 1; ++i) {
var temp;
for (var j = 0; j < l - i - 1; ++j) {
if (arr[j].age > arr[j + 1].age) {
temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
console.timeEnd('冒泡排序');
進行了五次，效果如下：
// 歸并排序: 6.592ms
// 冒泡排序: 25.959ms
// 歸并排序: 1.334ms
// 冒泡排序: 20.078ms
// 歸并排序: 1.085ms
// 冒泡排序: 16.420ms
// 歸并排序: 1.200ms
// 冒泡排序: 16.574ms
// 歸并排序: 2.593ms
// 冒泡排序: 12.653ms
***4倍，***近16倍的效率之差還是比較滿意的。
雖然1000條數據讓前端排序的可能性不大，但是幾十上百條的情況還是有的。另外由于node，JavaScript也能運行的服務端了，這個效率的提升也還是有用武之地的。
一點疑問
歸并排序里面使用了遞歸，在《數據結構與算法 JavaScript 描述》中，作者給出了自下而上的迭代方法。但是對于遞歸法，作者卻認為：
However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而，在 JavaScript 中這種方式不太可行，因為這個算法的遞歸深度對它來講太深了。
gitbook上這本書的作者對此有疑問，我也有疑問。
歸并中雖然用了遞歸，但是他是放在return后的呀。關于在renturn后的遞歸是有尾遞歸優化的呀。
關于尾遞歸優化是指：本來外層函數內部再調用一個函數的話，由于外層函數需要等待內層函數返回后才能返回結果，進入內層函數后，外層函數的信息，內存中是必須記住的，也就是調用堆棧。而內部函數放在return關鍵字后，就表示外層函數到此也就結束了，進入內層函數后，沒有必要再記住外層函數內的所有信息。
上面是我的理解的描述，不知道算不算準確。chrome下已經可以開啟尾遞歸優化的功能了，我覺得這個遞歸是不該影響他在JavaScript下的使用的。
***
有興趣的話，推薦讀讀這本書，進行排序的時候，可以考慮一些更高效的方法。
不過需要注意的是，這些高效率的排序方法，一般都需要相對較多的額外內存空間，需要權衡一下。
另外，非常小規模的數據就沒有必要了。一是影響太小，而是我們人的效率問題，一分鐘能從頭寫個冒泡、選擇、插入的排序方法，而換成是歸并排序呢？
