建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
做編程，排序是個(gè)必然的需求。前端也不例外，雖然不多，但是你肯定會(huì)遇到。
創(chuàng)新互聯(lián)公司專(zhuān)注于舒蘭網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供舒蘭營(yíng)銷(xiāo)型網(wǎng)站建設(shè)，舒蘭網(wǎng)站制作、舒蘭網(wǎng)頁(yè)設(shè)計(jì)、舒蘭網(wǎng)站官網(wǎng)定制、小程序開(kāi)發(fā)服務(wù)，打造舒蘭網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供舒蘭網(wǎng)站排名全網(wǎng)營(yíng)銷(xiāo)落地服務(wù)。
不過(guò)說(shuō)到排序，最容易想到的就是冒泡排序，選擇排序，插入排序了。
冒泡排序
依次比較相鄰的兩個(gè)元素，如果后一個(gè)小于前一個(gè)，則交換，這樣從頭到尾一次，就將***的放到了末尾。
從頭到尾再來(lái)一次，由于每進(jìn)行一輪，***的都已經(jīng)是***的了，因此后一輪需要比較次數(shù)可以比上一次少一個(gè)。雖然你還是可以讓他從頭到尾來(lái)比較，但是后面的比較是沒(méi)有意義的無(wú)用功，為了效率，你應(yīng)該對(duì)代碼進(jìn)行優(yōu)化。
圖片演示如下：
代碼實(shí)現(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]) { // 相鄰元素兩兩對(duì)比
var temp = arr[j+1]; // 元素交換
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
選擇排序
選擇排序我覺(jué)得是最簡(jiǎn)單的了，大一學(xué)VB的時(shí)候，就只記住了這個(gè)排序方法，原理非常簡(jiǎn)單：每次都找一個(gè)***或者最小的排在開(kāi)始即可。
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。
- 重復(fù)第二步，直到所有元素均排序完畢。
動(dòng)圖演示：
代碼演示：
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;
}
插入排序
插入排序也比較簡(jiǎn)單。就像打撲克一樣，依次將拿到的元素插入到正確的位置即可。
- 將***待排序序列***個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到***一個(gè)元素當(dāng)成是未排序序列。
- 從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面。）
動(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;
}
簡(jiǎn)單的代價(jià)是低效
上面三種都是非常簡(jiǎn)單的排序方法，簡(jiǎn)單的同時(shí)呢，效率也會(huì)比較低，還是拿這本書(shū)里的對(duì)比圖來(lái)說(shuō)明：
時(shí)間復(fù)雜度都高達(dá)O(n^2),而它們后面的一些排序算法時(shí)間復(fù)雜度基本都只有O(n log n)。
我的強(qiáng)迫癥又犯了，我想要高效率一點(diǎn)的排序方法。
歸并排序
簡(jiǎn)單把這本書(shū)的內(nèi)容過(guò)了一遍，當(dāng)時(shí)就理解了這個(gè)歸并排序，因此這里就談一下這個(gè)歸并排序吧。
基本原理是分治法，就是分開(kāi)并且遞歸來(lái)排序。
步驟如下：
- 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列；
- 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；
- 比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置；
- 重復(fù)步驟 3 直到某一指針達(dá)到序列尾；
- 將另一序列剩下的所有元素直接復(fù)制到合并序列尾。
動(dòng)圖演示：
代碼示例：
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;
}既然是個(gè)愛(ài)折騰的人，折騰了總得看看效果吧。
效率測(cè)試
由于我學(xué)這個(gè)來(lái)進(jìn)行排序不是對(duì)簡(jiǎn)單數(shù)組，數(shù)組內(nèi)都是對(duì)象，要對(duì)對(duì)象的某個(gè)屬性進(jìn)行排序，還要考慮升降序。
因此我的代碼實(shí)現(xiàn)如下：
/** * [歸并排序] * @param {[Array]} arr [要排序的數(shù)組] * @param {[String]} prop [排序字段，用于數(shù)組成員是對(duì)象時(shí)，按照其某個(gè)屬性進(jìn)行排序，簡(jiǎn)單數(shù)組直接排序忽略此參數(shù)] * @param {[String]} order [排序方式 省略或asc為升序 否則降序] * @return {[Array]} [排序后數(shù)組，新數(shù)組，并非在原數(shù)組上的修改] */
var mergeSort = (function() {
// 合并
var _merge = function(left, right, prop) {
var result = [];
// 對(duì)數(shù)組內(nèi)成員的某個(gè)屬性排序
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 _;
}
};
})();需要對(duì)哪個(gè)屬性進(jìn)行排序是不確定，可以隨意指定，因此寫(xiě)成了參數(shù)。有由于不想讓這些東西在每次循環(huán)都進(jìn)行判斷，因此代碼有點(diǎn)冗余。
關(guān)于降序的問(wèn)題，也沒(méi)有加入?yún)?shù)中，而是簡(jiǎn)單的升序后再逆序輸出。原因是不想讓每次循環(huán)遞歸里都去判斷條件，所以簡(jiǎn)單處理了。
下面就是見(jiàn)證效率的時(shí)候了，一段數(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/
實(shí)際測(cè)試來(lái)啦：
// 效率測(cè)試
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倍的效率之差還是比較滿(mǎn)意的。
雖然1000條數(shù)據(jù)讓前端排序的可能性不大，但是幾十上百條的情況還是有的。另外由于node，JavaScript也能運(yùn)行的服務(wù)端了，這個(gè)效率的提升也還是有用武之地的。
一點(diǎn)疑問(wèn)
歸并排序里面使用了遞歸，在《數(shù)據(jù)結(jié)構(gòu)與算法 JavaScript 描述》中，作者給出了自下而上的迭代方法。但是對(duì)于遞歸法，作者卻認(rèn)為：
However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而，在 JavaScript 中這種方式不太可行，因?yàn)檫@個(gè)算法的遞歸深度對(duì)它來(lái)講太深了。
gitbook上這本書(shū)的作者對(duì)此有疑問(wèn)，我也有疑問(wèn)。
歸并中雖然用了遞歸，但是他是放在return后的呀。關(guān)于在renturn后的遞歸是有尾遞歸優(yōu)化的呀。
關(guān)于尾遞歸優(yōu)化是指：本來(lái)外層函數(shù)內(nèi)部再調(diào)用一個(gè)函數(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ù)后，沒(méi)有必要再記住外層函數(shù)內(nèi)的所有信息。
上面是我的理解的描述，不知道算不算準(zhǔn)確。chrome下已經(jīng)可以開(kāi)啟尾遞歸優(yōu)化的功能了，我覺(jué)得這個(gè)遞歸是不該影響他在JavaScript下的使用的。
***
有興趣的話，推薦讀讀這本書(shū)，進(jìn)行排序的時(shí)候，可以考慮一些更高效的方法。
不過(guò)需要注意的是，這些高效率的排序方法，一般都需要相對(duì)較多的額外內(nèi)存空間，需要權(quán)衡一下。
另外，非常小規(guī)模的數(shù)據(jù)就沒(méi)有必要了。一是影響太小，而是我們?nèi)说男蕟?wèn)題，一分鐘能從頭寫(xiě)個(gè)冒泡、選擇、插入的排序方法，而換成是歸并排序呢？
本文名稱(chēng)：JavaScript排序，不只是冒泡
本文地址：http://www.dlmjj.cn/article/dhejdec.html
