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