數(shù)組排序在日常編程中用到的其實(shí)還是比較多的，比如把一組數(shù)據(jù)按時(shí)間排序，按首字母排序，按大小排序等等，那么就讓我們一起來(lái)了解下常見(jiàn)的數(shù)組排序方法有哪些。
一說(shuō)到數(shù)組排序，很多人腦子里第一時(shí)間蹦出來(lái)的可能就是sort()方法。那我們就從這個(gè)原生的排序方法sort()開(kāi)始講起。
語(yǔ)法：arrayObject.sort(sortby)
這里的sortby是一個(gè)參數(shù)，規(guī)定排序的順序，必須是函數(shù)。
sort()的返回值是對(duì)該數(shù)組的引用，這里要注意的是，該排序方法會(huì)在原數(shù)組上直接進(jìn)行排序，并不會(huì)生成一個(gè)排好序的新數(shù)組。
還要注意的是：如果沒(méi)有使用參數(shù)sortby，那么排序的時(shí)候?qū)?huì)按字母的順序?qū)?shù)組中的元素進(jìn)行排序，說(shuō)精確點(diǎn)是按照字符編碼的順序進(jìn)行排序。如果要實(shí)現(xiàn)這一點(diǎn)，首先應(yīng)該把數(shù)組的元素都轉(zhuǎn)化成字符串，以便進(jìn)行比較。
如果想按照其他標(biāo)準(zhǔn)排序，那么就要傳入?yún)?shù)sortby，即提供比較函數(shù)。該函數(shù)要比較兩個(gè)值，然后返回一個(gè)用于說(shuō)明這兩個(gè)值的相對(duì)順序的數(shù)字。比較參數(shù)應(yīng)該具有兩個(gè)參數(shù)a和b，其返回值如下：
若a小于b，在排序后的數(shù)組中，a應(yīng)該出現(xiàn)在b之前，則返回一個(gè)小于0的值
若a=b，則返回0
若a大于b，則返回一個(gè)大于0的值
我們先來(lái)看兩個(gè)例子，第一個(gè)不傳入?yún)?shù)sortby，代碼如下：
var arr = ["Zhangsan", "Lisi", "Wangwu", "Hanmei", "Chendu"];
var res = arr.sort();
console.log(res);
// 打印結(jié)果為["Chendu", "Hanmei", "Lisi", "Wangwu", "Zhangsan"]
那么如果數(shù)組元素是數(shù)字呢？看如下代碼：
var arr = [524, 684, 5, 69, 15];
var res = arr.sort();
console.log(res);
// 打印結(jié)果為[15, 5, 524, 684, 69]
由上面的代碼可以看到，如果數(shù)組元素為數(shù)字的話，排序并不會(huì)按大小順序排，而是會(huì)按數(shù)字的第一個(gè)字符排序。
如果我們想要這組數(shù)字按從小到大，或者從大到小的順序排列的話，那么我們就需要傳入?yún)?shù)sortby，即上文所說(shuō)的比較函數(shù)。
function sortNum(a, b) {
return a - b;
}
var arr = [524, 684, 5, 69, 15];
var res = arr.sort(sortNum);
console.log(res);
// 打印結(jié)果為[5, 15, 69, 524, 684]
上面代碼中的sortNum就是一個(gè)比較函數(shù)，我們傳入a,b兩個(gè)值，然后返回a-b的值，跟據(jù)返回值進(jìn)行大小排序，如果想要從大到小排序，只需要return b-a即可。
這里額外提一下reverse()這個(gè)方法，這個(gè)方法用于顛倒數(shù)組中元素的順序。這里要注意，只是顛倒，并不是按從大到小的順序，因此我認(rèn)為它算不上是排序方法。
語(yǔ)法：arrayObject.reverse()
demo代碼如下：
var arr = [524, 684, 5, 69, 15];
var res = arr.reverse();
console.log(res);
// 打印結(jié)果為[15, 69, 5, 684, 524]
除了我們常用的sort()方法，其實(shí)還有其他很多方法可以實(shí)現(xiàn)排序：
冒泡排序
快速排序
插入排序
希爾排序
選擇排序（坑未填）
歸并排序（坑未填）
堆排序（坑未填）
一、冒泡排序
冒泡排序就是遍歷數(shù)組里面的元素，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤，就把它們交換過(guò)來(lái)，直到?jīng)]有需要交換的兩個(gè)元素為止。它是一種穩(wěn)定排序算法。
冒泡排序算法的運(yùn)作如下：（從后往前）
比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
——引用自百度百科《冒泡排序》
function bubbleSort(arr) {
for(var i = 0; i < arr.length; i++) {
for(var j = 0; j < arr.length; j++) {
if(arr[i] < arr[j]) {
var temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
return arr;
}
var arr = [524, 684, 5, 69, 15];
bubbleSort(arr);? ? // 結(jié)果為[5, 15, 69, 524, 684]
上面的代碼就是一個(gè)很好理解的冒泡排序?qū)懛ǎ捎脙蓚€(gè)for循環(huán)，當(dāng)i=0的時(shí)候，將arr[0]與數(shù)組里面的每一項(xiàng)比較，如果arr[0]小于某一項(xiàng)，則替換它們的位置，以此類推。
二、快速排序
快速排序是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
快速排序的過(guò)程大致分三步：
在數(shù)據(jù)集之中，選擇一個(gè)元素作為"基準(zhǔn)"（pivot）。
所有小于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的左邊；所有大于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的右邊。
對(duì)"基準(zhǔn)"左邊和右邊的兩個(gè)子集，不斷重復(fù)第一步和第二步，直到所有子集只剩下一個(gè)元素為止。
——引用自阮一峰博客《快速排序的JavaScript實(shí)現(xiàn)》
封裝代碼如下：
function quickSort(arr) {
if(arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
// splice()返回的是被刪除元素組成的數(shù)組
var lef = [];
var rig = [];
for(var i = 0; i < arr.length; i++) {
if(arr[i] < pivot) {
lef.push(arr[i]);
}
else {
rig.push(arr[i]);
}
}
return quickSort(lef).concat(pivot, quickSort(rig)); // 遞歸
}
var arr = [524, 684, 5, 69, 15];
quickSort(arr);? ? // 結(jié)果為[5, 15, 69, 524, 684]
三、插入排序
已知一個(gè)已有序的數(shù)據(jù)序列，需要插入一個(gè)數(shù)據(jù)，要求插入數(shù)據(jù)后這個(gè)序列依然有序，那么這個(gè)時(shí)候就需要使用插入排序。
插入排序把要排序的數(shù)組分成兩部分：第一部分包含了這個(gè)數(shù)組的所有元素，但將最后一個(gè)元素除外（讓數(shù)組多一個(gè)空間才有插入的位置），而第二部分就只包含這一個(gè)元素（即待插入元素）。在第一部分排序完成后，再將這個(gè)最后元素插入到已排好序的第一部分中。
用生活中比較好理解的事物就是斗地主，你手里的牌已經(jīng)排好序了，摸一張新牌，要將其插入進(jìn)去，小的牌會(huì)往前插，大的牌會(huì)往后插。
封裝代碼如下：
function insertSort(arr) {
for(var i = 1; i < arr.length; i++) {
if(arr[i] < arr[i - 1]) {
var temp = arr[i];
var j = i -1;
arr[i] = arr[j];
while(j >= 0 && temp < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
}
var arr = [524, 684, 5, 69, 15];
insertSort(arr);
console.log(arr);? ? // 結(jié)果為[5, 15, 69, 92, 524, 684]
如果你是需要在現(xiàn)有的已排好序的數(shù)組中插入新的元素，并且新數(shù)組也依然排好序，那么上面的代碼就需要修改一下：
function insertSort(arr, a) {
for(var i = 1; i < arr.length; i++) {
if(arr[i] >= a) {
for(var j = arr.length; j > i; j--) {
arr[j] = arr[j - 1];
}
arr[i] = a;
break;
}
}
return arr;
}
var arr = [5, 15, 69, 524, 684];
insertSort(arr, 92);? ? // 結(jié)果為[5, 15, 69, 92, 524, 684]
對(duì)于小型數(shù)組的排列，插入排序要比前兩種排序方法性能更好。
四、希爾排序
希爾排序是插入排序的一種，也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。
希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。
——引用自百度百科《希爾排序》
封裝代碼如下：
function shellSort(arr) {
var gap = Math.ceil(arr.length / 2);
while(gap > 0) {
for(var k = 0; k < gap; k++) {
var tagArr = [];
tagArr.push(arr[k]);
for(var i = k + gap; i < arr.length; i = i + gap) {
var temp = arr[i];
tagArr.push(temp);
for(var j = i - gap; j > -1; j = j - gap) {
if(arr[j] > temp) {
arr[j + gap] = arr[j];
}
else {
break;
}
}
arr[j + gap] = temp;
}
}
gap = parseInt(gap / 2);
}
return arr;
}
var arr = [524, 684, 5, 69, 15];
shellSort(arr);? ? // 結(jié)果為[5, 15, 69, 92, 524, 684]
