摘自wiki和http://bubkoo.com/2014/01/17/sort-algorithm/archives/
什么是算法
https://zh.wikipedia.org/zh-hans/%E7%AE%97%E6%B3%95
排序演示 https://visualgo.net/zh/sorting
以下是高德納在他的著作《計算機(jī)程序設(shè)計藝術(shù)》里對算法的特征歸納：
輸入：一個算法必須有零個或以上輸入量擎淤。
輸出：一個算法應(yīng)有一個或以上輸出量险绘，輸出量是算法計算的結(jié)果。
明確性：算法的描述必須無歧義劈榨，以保證算法的實(shí)際執(zhí)行結(jié)果是精確地匹配要求或期望，通常要求實(shí)際運(yùn)行結(jié)果是確定的。
有限性：依據(jù)圖靈的定義衫樊，一個算法是能夠被任何圖靈完備系統(tǒng)模擬的一串運(yùn)算了罪，而圖靈機(jī)只有有限個狀態(tài)锭环、有限個輸入符號和有限個轉(zhuǎn)移函數(shù)（指令）。而一些定義更規(guī)定算法必須在有限個步驟內(nèi)完成任務(wù)泊藕。
有效性：又稱可行性田藐。能夠?qū)崿F(xiàn)，算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)
什么是數(shù)據(jù)結(jié)構(gòu)
就是數(shù)據(jù)的結(jié)構(gòu)吱七。
一般來說是這樣的：
我們要解決一個跟數(shù)據(jù)相關(guān)的問題
分析這個問題汽久，想出對應(yīng)的數(shù)據(jù)結(jié)構(gòu)
分析數(shù)據(jù)結(jié)構(gòu)，想出算法
數(shù)據(jù)結(jié)構(gòu)和算法是互相依存踊餐、不可分開的
你學(xué)習(xí)完排序算法景醇，就能了解常見的數(shù)據(jù)結(jié)構(gòu)
大分類
分治法：把一個問題分區(qū)成互相獨(dú)立的多個部分分別求解的思路。這種求解思路帶來的好處之一是便于進(jìn)行并行計算吝岭。
動態(tài)規(guī)劃法：當(dāng)問題的整體最優(yōu)解就是由局部最優(yōu)解組成的時候三痰，經(jīng)常采用的一種方法。
貪婪算法：常見的近似求解思路窜管。當(dāng)問題的整體最優(yōu)解不是（或無法證明是）由局部最優(yōu)解組成散劫，且對解的最優(yōu)性沒有要求的時候，可以采用的一種方法幕帆。
線性規(guī)劃法：見詞條获搏。
簡并法：把一個問題通過邏輯或數(shù)學(xué)推理，簡化成與之等價或者近似的失乾、相對簡單的模型常熙，進(jìn)而求解的方法。
我們前端主要使用分治法——分而治之碱茁。
快速排序
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）裸卫。
步驟為：
從數(shù)列中挑出一個元素，稱為"基準(zhǔn)"（pivot）纽竣，
重新排序數(shù)列墓贿，所有比基準(zhǔn)值小的元素擺放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素擺在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）蜓氨。在這個分區(qū)結(jié)束之后聋袋，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作语盈。
遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序舱馅。
遞歸到最底部時，數(shù)列的大小是零或一刀荒，也就是已經(jīng)排序好了代嗤。這個算法一定會結(jié)束棘钞，因?yàn)樵诿看蔚牡╥teration）中，它至少會把一個元素擺到它最后的位置去干毅。
Array.prototype.quick_sort = 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.quick_sort().concat(mid.concat(right.quick_sort()));
};
var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
arr = arr.quick_sort();
for (i = 0; i < arr.length; i++)
document.body.innerHTML += arr[i] + " ";
document.body.innerHTML += "<br>";
冒泡排序
冒泡排序算法的運(yùn)作如下：
比較相鄰的元素宜猜。如果第一個比第二個大，就交換他們兩個硝逢。
對每一對相鄰元素作同樣的工作姨拥，從開始第一對到結(jié)尾的最后一對。這步做完后渠鸽，最后的元素會是最大的數(shù)叫乌。
針對所有的元素重復(fù)以上的步驟，除了最后一個徽缚。
持續(xù)每次對越來越少的元素重復(fù)上面的步驟憨奸，直到?jīng)]有任何一對數(shù)字需要比較。
Array.prototype.quick_sort = 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.quick_sort().concat(mid.concat(right.quick_sort()));
};
var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
arr = arr.quick_sort();
for (i = 0; i < arr.length; i++)
document.body.innerHTML += arr[i] + " ";
document.body.innerHTML += "<br>";
插入排序
一般來說凿试，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)排宰。具體算法描述如下：
從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序
取出下一個元素那婉，在已經(jīng)排序的元素序列中從后向前掃描
如果該元素（已排序）大于新元素板甘，將該元素移到下一位置
重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置后
重復(fù)步驟2~5
function insertionSort(array) {
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
var length = array.length,
i,
j;
for (i = 1; i < length; i++) {
for (j = i; j > 0; j--) {
if (array[j - 1] > array[j]) {
swap(array, j - 1, j);
} else {
break;
}
}
}
return array;
}
下面這種方式可以減少交換次數(shù)：
function insertionSort(array) {
var length = array.length,
i,
j,
temp;
for (i = 1; i < length; i++) {
temp = array[i];
for (j = i; j >= 0; j--) {
if (array[j - 1] > temp) {
array[j] = array[j - 1];
} else {
array[j] = temp;
break;
}
}
}
return array;
}
桶排序
設(shè)置一個定量的數(shù)組當(dāng)作空桶子详炬。
尋訪序列盐类，并且把項(xiàng)目一個一個放到對應(yīng)的桶子去。
對每個不是空的桶子進(jìn)行排序痕寓。
從不是空的桶子里把項(xiàng)目再放回原來的序列中傲醉。
首先用最笨的方法，每一個桶只能放相同的數(shù)字呻率，最大桶的數(shù)量為數(shù)組中的正數(shù)最大值加上負(fù)數(shù)最小值的絕對值。
function bucketSort(array) {
var bucket = [], // 正數(shù)桶
negativeBucket = [], // 負(fù)數(shù)桶
result = [],
l = array.length,
i,
j,
k,
abs;
// 入桶
for (i = 0; i < l; i++) {
if (array[i] < 0) {
abs = Math.abs(array[i]);
if (!negativeBucket[abs]) {
negativeBucket[abs] = [];
}
negativeBucket[abs].push(array[i]);
} else {
if (!bucket[array[i]]) {
bucket[array[i]] = [];
}
bucket[array[i]].push(array[i]);
}
}
// 出桶
l = negativeBucket.length;
for (i = l - 1; i >= 0; i--) {
if (negativeBucket[i]) {
k = negativeBucket[i].length;
for (j = 0; j < k; j++) {
result.push(negativeBucket[i][j]);
}
}
}
l = bucket.length;
for (i = 0; i < l; i++) {
if (bucket[i]) {
k = bucket[i].length;
for (j = 0; j < k; j++) {
result.push(bucket[i][j]);
}
}
}
return result;
}
下面這種方式就是文中舉例分析的那樣呻引，每個桶存放一定范圍的數(shù)字礼仗，用 step 參數(shù)來設(shè)置該范圍，取 step 為 1 就退化成前一種實(shí)現(xiàn)方式逻悠。關(guān)鍵部位代碼有注釋元践，慢慢看，邏輯稍微有點(diǎn)復(fù)雜童谒。
/*
* @array 將要排序的數(shù)組
*
* @step 劃分桶的步長单旁，比如 step = 5，表示每個桶存放的數(shù)字的范圍是 5饥伊，像 -4<sub>1象浑、0</sub>5蔫饰、6~11
*/
function bucketSort(array, step) {
var result = [],
bucket = [],
bucketCount,
l = array.length,
i,
j,
k,
s,
max = array[0],
min = array[0],
temp;
for (i = 1; i < l; i++) {
if (array[i] > max) {
max = array[i]
}
if (array[i] < min) {
min = array[i];
}
}
min = min - 1;
bucketCount = Math.ceil((max - min) / step); // 需要桶的數(shù)量
for (i = 0; i < l; i++) {
temp = array[i];
for (j = 0; j < bucketCount; j++) {
if (temp > (min + step * j) && temp <= (min + step * (j + 1))) { // 判斷放入哪個桶
if (!bucket[j]) {
bucket[j] = [];
}
// 通過插入排序?qū)?shù)字插入到桶中的合適位置
s = bucket[j].length;
if (s > 0) {
for (k = s - 1; k >= 0; k--) {
if (bucket[j][k] > temp) {
bucket[j][k + 1] = bucket[j][k];
} else {
break;
}
}
bucket[j][k + 1] = temp;
} else {
bucket[j].push(temp);
}
}
}
}
for (i = 0; i < bucketCount; i++) { // 循環(huán)取出桶中數(shù)據(jù)
if (bucket[i]) {
k = bucket[i].length;
for (j = 0; j < k; j++) {
result.push(bucket[i][j]);
}
}
}
return result;
}
