大家好，我是IT修真院武漢分院第八期的學員莊引猜谚，一枚正直純潔善良的WEB前端程序員败砂。
今天給大家分享一下，修真院官網(wǎng)JS任務11魏铅，深度思考中的知識點——常見的幾種排序方法昌犹？
1.背景介紹
在計算機科學與數(shù)學中，一個排序算法（英語：Sorting algorithm）是一種能將一串資料依照特定排序方式進行排列的一種算法览芳。 最常用到的排序方式是數(shù)值順序以及字典順序斜姥。有效的排序算法在一些算法（例如搜尋算法與合并算法）中是重要的， 如此這些算法才能得到正確解答。 排序算法也用在處理文字資料以及產生人類可讀的輸出結果铸敏。 基本上缚忧，排序算法的輸出必須遵守下列兩個原則：
輸出結果為遞增序列（遞增是針對所需的排序順序而言）
輸出結果是原輸入的一種排列、或是重組
雖然排序算法是一個簡單的問題杈笔，但是從計算機科學發(fā)展以來闪水，在此問題上已經有大量的研究。 更多的新算法仍在不斷的被發(fā)明蒙具。
2.知識剖析
查找和排序算法是算法的入門知識，其經典思想可以用于很多算法當中。因為其實現(xiàn)代碼較短裁着，應用較常見投储。 所以在面試中經常會問到排序算法及其相關的問題。但萬變不離其宗篱昔，只要熟悉了思想每强，靈活運用也不是難事。 一般在面試中最澈当考的是快速排序和歸并排序舀射，并且經常有面試官要求現(xiàn)場寫出這兩種排序的代碼。 對這兩種排序的代碼一定要信手拈來才行怀伦。還有插入排序脆烟、冒泡排序、堆排序房待、基數(shù)排序邢羔、桶排序等。
常見的幾種算法：
①冒泡算法
②選擇排序
③插入排序
④快速排序
3.常見問題
問題一:各種排序算法用JavaScript 如何實現(xiàn)?
問題二:各種排序算法的優(yōu)劣及其應用?
4.解決方案
問題一:各種排序算法用JavaScript 如何實現(xiàn)?
問題二:各種排序算法的優(yōu)劣及其應用?
4.解決方案
冒泡排序
冒泡排序（英語：Bubble Sort）是一種簡單的排序算法桑孩。它重復地走訪過要排序的數(shù)列拜鹤，一次比較兩個元素， 如果他們的順序錯誤就把他們交換過來流椒。走訪數(shù)列的工作是重復地進行直到沒有元素再需要交換敏簿， 也就是說該數(shù)列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數(shù)列的頂端宣虾。
冒泡排序演算法的運作如下：
比較相鄰的元素惯裕。如果第一個比第二個大，就交換他們兩個绣硝。
對每一對相鄰元素作同樣的工作蜻势，從開始第一對到結尾的最后一對。這步做完后鹉胖，最后的元素會是最大的數(shù)握玛。
針對所有的元素重復以上的步驟够傍，除了最后一個。
持續(xù)每次對越來越少的元素重復上面的步驟挠铲，直到沒有任何一對數(shù)字需要比較冕屯。
代碼實現(xiàn):
Array.prototype.bubbleSort = function () {
var i, j, temp;
for (i = 0; i < this.length - 1; i++)
for (j = 0; j < this.length - 1 - i; j++)
if (this[j] > this[j + 1]) {
temp = this[j];
this[j] = this[j + 1];
this[j + 1] = temp;
}
return this;
};
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];//定義一個數(shù)組
num.bubbleSort();//數(shù)組調用冒泡排序算法
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下市殷。 首先在未排序序列中找到最秀底（大）元素，存放到排序序列的起始位置醋寝，然后搞挣，再從剩余未排序元素中繼續(xù)尋找最小（大）元素音羞， 然后放到已排序序列的末尾囱桨。以此類推，直到所有元素均排序完畢嗅绰。 選擇排序的思想其實和冒泡排序有點類似舍肠，都是在一次排序后把最小的元素放到最前面。但是過程不同窘面， 冒泡排序是通過相鄰的比較和交換翠语。而選擇排序是通過對整體的選擇。
Array.prototype.selectionSort = function() {
var i, j, min;
var temp;
for (i = 0; i < this.length - 1; i++) {
min = i;
for (j = i + 1; j < this.length; j++)
if (this[min] > this[j])
min = j;
temp = this[min];
this[min] = this[i];
this[i] = temp;
}
return this;
};
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]; //定義一個數(shù)組
num.selectionSort(); //數(shù)組定義選擇排序算法
插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法财边。它的 工作原理是通過構建有序序列肌括，對于未排序數(shù)據(jù)， 在已排序序列中從后向前掃描酣难，找到相應位置并插入谍夭。插入排序在實現(xiàn)上，通常采用in-place排序 （即只需用到O(1)的額外空間的排序）憨募，因而在從后向前掃描過程中紧索，需要反復把已排序元素逐步向后挪位， 為最新元素提供插入空間菜谣。
1.從第一個元素開始珠漂，該元素可以認為已經被排序
2.取出下一個元素，在已經排序的元素序列中從后向前掃描
3.如果該元素（已排序）大于新元素尾膊，將該元素移到下一位置
4.將新元素插入到該位置后
Array.prototype.insertionSort = function () {
for (var i = 1; i < this.length; i++) {
var temp = this[i];
var j = i - 1;
//如果將賦值放到下一行的for循環(huán)內, 會導致在第13行出現(xiàn)j未聲明的錯誤
for (; j >= 0 && this[j] > temp; j--) {
this[j + 1] = this[j];
}
this[j + 1] = temp;
}
return this;
}
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]; //定義一個數(shù)組
num.insertionSort(); //數(shù)組調用插入排序算法
快速排序
快速排序（英語：Quicksort）甘磨，又稱劃分交換排序（partition-exchange sort）， 一種排序算法眯停， 最早由東尼·霍爾提出。在平均狀況下卿泽，排序n個項目要Ο(n log n)次比較莺债。在最壞狀況下則需要Ο(n2)次比較滋觉， 但這種狀況并不常見。事實上齐邦，快速排序通常明顯比其他Ο(n log n)演算法更快椎侠， 因為它的內部循環(huán)（inner loop）可以在大部分的架構上很有效率地被實現(xiàn)出來。 快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）措拇。
步驟為：
從數(shù)列中挑出一個元素我纪，稱為"基準"（pivot），
重新排序數(shù)列丐吓，所有比基準值小的元素擺放在基準前面浅悉，所有比基準值大的元素擺在基準后面（相同的數(shù)可以到任一邊）。在這個分割結束之后券犁，該基準就處于數(shù)列的中間位置术健。這個稱為分割（partition）操作。
遞歸地（recursively）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序粘衬。
遞歸到最底部時荞估，數(shù)列的大小是零或一，也就是已經排序好了稚新。這個演算法一定會結束勘伺，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去褂删。
Array.prototype.quickSort = function () {
var len = this.length;
if (len <= 1)
return this.slice(0);
var left = [];
var right = [];
var mid = [this[0]];
for (var i = 1; i < len; i++)
if (this[i] < mid[0])
left.push(this[i]);
else
right.push(this[i]);
return left.quickSort().concat(mid.concat(right.quickSort()));
};
var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
arr = arr.quickSort();
5.編碼實戰(zhàn)
6.擴展思考
各種排序算法的時間復雜度和空間復雜度
算法優(yōu)劣評價術語
穩(wěn)定性:
穩(wěn)定：如果 a 原本在 b 前面飞醉，而 a = b，排序之后 a 仍然在 b 的前面笤妙；
不穩(wěn)定：如果 a 原本在 b 的前面冒掌，而 a = b，排序之后 a 可能會出現(xiàn)在 b 的后面蹲盘；
排序方式:
內排序：所有排序操作都在內存中完成股毫，占用常數(shù)內存，不占用額外內存召衔。
外排序：由于數(shù)據(jù)太大铃诬，因此把數(shù)據(jù)放在磁盤中，而排序通過磁盤和內存的數(shù)據(jù)傳輸才能進行苍凛，占用額外內存趣席。
復雜度:
時間復雜度: 一個算法執(zhí)行所耗費的時間。
空間復雜度: 運行完一個程序所需內存的大小醇蝴。
7.參考文獻
參考一：JavaScript 排序算法匯總
8.更多討論
還有那些經典排序算法?
常用的排序算法宣肚？_騰訊視頻
PPT鏈接：常用的排序算法
技能樹.IT修真院
“我們相信人人都可以成為一個工程師，現(xiàn)在開始悠栓，找個師兄霉涨，帶你入門按价，掌控自己學習的節(jié)奏，學習的路上不再迷皿仙”楼镐。
這里是技能樹.IT修真院，成千上萬的師兄在這里找到了自己的學習路線往枷，學習透明化框产，成長可見化，師兄1對1免費指導错洁”蓿快來與我一起學習吧 ！
http://www.jnshu.com/login/1/86157900
