前端開發(fā)在工作中很少會(huì)遇到這些算法，但作為一個(gè)程序員的基本素質(zhì)需要了解巷挥。
畢竟担神，首先是個(gè)程序員穆刻，其次才是前端。
什么是算法
高德納《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》里對(duì)算法的歸納（符合以下5個(gè)定義的都叫算法）：
- 輸入：一個(gè)算法必須有零個(gè)或以上輸入量
- 輸出：一個(gè)算法應(yīng)有一個(gè)或以上輸出量
- 明確性：算法的描述必須無歧義寞缝，實(shí)際運(yùn)行結(jié)果是確定的
- 有限性：必須在有限個(gè)步驟內(nèi)結(jié)束
- 有效性：又稱可行性癌压。能夠被執(zhí)行者實(shí)現(xiàn)
權(quán)威書籍推薦《數(shù)據(jù)結(jié)構(gòu)與算法分析》: 數(shù)據(jù)結(jié)構(gòu)［算法分析／表?xiàng)ｊ?duì)列／樹／散列］／排序......
排序算法研究的是：N個(gè)正整數(shù)排序。
- 定義問題：
數(shù)組array含有N個(gè)正整數(shù)荆陆，
輸入量為 array滩届，
請(qǐng)將array中的數(shù)字從大到小排列，
輸出量為排序好的數(shù)組被啼。- 例如：
var array = [5,2,4,6,8];
function sort(){
//to do ...
}
sort(array) === [2,4,5,6,8];
結(jié)合算法可視化工具帜消，一目了然，方便總結(jié)浓体。
目錄
- 冒泡排序
- 選擇排序
- 插入排序
- 合并排序
- 快速排序
（默認(rèn)按從小到大排序泡挺。）
1. 冒泡排序
現(xiàn)實(shí)場(chǎng)景：教官雙手算法，較高的往后站命浴。每遍歷1次所有都將1個(gè)最大值往后放娄猫，直到遍歷所有成員贱除，排序結(jié)束。
冒泡排序.gif
js代碼：
function bubbleSort(myArray){
var len = myArray.length;
var i;
var j;
var stop;
for (i = 0; i < len - 1; i++){
for (j = 0, stop = len - 1 - i; j < stop; j++){
if (myArray[j] > myArray[j + 1]){
swap(myArray, j, j + 1);
}
}
}
return myArray;
}
function swap(myArray, p1, p2){
var temp = myArray[p1];
myArray[p1] = myArray[p2];
myArray[p2] = temp;
}
2. 選擇排序
現(xiàn)實(shí)場(chǎng)景：教官一指算法媳溺，最矮的到前面來月幌。每次選擇最小的與前面互換位置。
選擇排序.gif
js代碼：
function selectionSort(myArray){
var len = myArray.length,
min;
for (i=0; i < len; i++){
// 將當(dāng)前位置設(shè)為最小值
min = i;
// 檢查數(shù)組其余部分是否更小
for (j=i+1; j < len; j++){
if (myArray[j] < myArray[min]){
min = j;
}
}
// 如果當(dāng)前位置不是最小值悬蔽，將其換為最小值
if (i != min){
swap(myArray, i, min);
}
}
return myArray;
}
function swap(myArray, p1, p2){
var temp = myArray[p1];
myArray[p1] = myArray[p2];
myArray[p2] = temp;
}
3. 插入排序
現(xiàn)實(shí)場(chǎng)景：撲克牌起牌扯躺。
基本思路：
- 把數(shù)組分為[已排序]和[未排序]兩部分。
- 從[未排序]抽出第一個(gè)數(shù)蝎困，和[已排序]部分比較录语，插入到合適的位置。
插入排序.gif
js代碼：
function insertionSort(myArray) {
var len = myArray.length, // 數(shù)組的長(zhǎng)度
value, // 當(dāng)前比較的值
i, // 未排序部分的當(dāng)前位置
j; // 已排序部分的當(dāng)前位置
for (i=0; i < len; i++) {
value = myArray[i]; // 儲(chǔ)存當(dāng)前位置的值
/*
* 當(dāng)已排序部分的當(dāng)前元素大于value禾乘，
* 就將當(dāng)前元素向后移一位澎埠，再將前一位與value比較
*/
for (j=i-1; j > -1 && myArray[j] > value; j--) {
myArray[j+1] = myArray[j];
}
myArray[j+1] = value;
}
return myArray;
}
4. 合并排序(分而治之)
現(xiàn)實(shí)場(chǎng)景：領(lǐng)導(dǎo)任務(wù)拆分法。
基本思路：
- 不斷將數(shù)組對(duì)半分盖袭，直到每個(gè)數(shù)組只有一個(gè)失暂。
- 將分出來的部分重新合并。
- 合并的時(shí)候按順序排列鳄虱。
合并排序.gif
js代碼：
// 被拆分的數(shù)組重新合并
function merge(left, right) {
var result = [],
left_index = 0,
right_index = 0;
// 將兩個(gè)數(shù)組合并
// 合并的時(shí)候按從小到大的順序
while (left_index < left.length && right_index < right.length) {
if (left[left_index] < right[right_index]) {
result.push(left[left_index++]);
} else {
result.push(right[right_index++]);
}
}
// 和其他數(shù)組拼接
return result.concat(left.slice(left_index)).concat(right.slice(right_index));
}
function mergeSort(myArray) {
// 只有一個(gè)數(shù)的時(shí)候退出遞歸
if (myArray.length < 2) {
return myArray;
}
var middle = Math.floor(myArray.length / 2),
left = myArray.slice(0, middle),
right = myArray.slice(middle);
// 遞歸
// 不斷拆分只到一個(gè)數(shù)組只有一個(gè)數(shù)
return merge(mergeSort(left), mergeSort(right));
}
5. 快速排序
現(xiàn)實(shí)場(chǎng)景：自私的認(rèn)為，我前面的都比我矮凭峡，我后面的都比我高拙已，每個(gè)人都只找準(zhǔn)自己的位置。
基本思路：
- 以一個(gè)數(shù)為基準(zhǔn)(中間的數(shù))摧冀，比基準(zhǔn)小的放到左邊倍踪，比基準(zhǔn)大的放到右邊。
- 再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序（遞歸進(jìn)行）索昂。
- 不能再分后退出遞歸建车，并重新將數(shù)組合并。
合并排序.gif
js代碼：
var quickSort = function(myArray) {
// 當(dāng)被分的數(shù)組只剩一個(gè)時(shí)椒惨，退出遞歸
if (myArray.length <= 1) {
return myArray;
}
// 中間基準(zhǔn)值的index
var pivotIndex = Math.floor(myArray.length / 2);
// 基準(zhǔn)值
var pivot = myArray.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
// 小的放左邊缤至，大的放右邊
for (var i = 0; i < myArray.length; i++) {
if (myArray[i] < pivot) {
left.push(myArray[i]);
} else {
right.push(myArray[i]);
}
}
// 遞歸
// 把數(shù)組合并在一起
return quickSort(left).concat([pivot], quickSort(right));
};
