排序算法：
冒泡排序：頻繁交換 镣奋，找出其中最大的放到最后一個(gè) 一次找到第二大的放大倒數(shù)第二個(gè)...最后完成
function bubbleSort(arr) {
for (let i = 0;i < arr.length - 1;i++) {
for (let j = 0;j < arr.length - 1 - i;j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
}
return arr;
}
選擇排序：
從開頭選擇一個(gè)基準(zhǔn)值 遍歷一趟選出比這個(gè)更小的值最后當(dāng)前位置與找出來的最終值交換。排列順序是從前到后
function xuanzeSort(arr) {
for (let i = 0, min, index;i < arr.length;i++) {
min = arr[i];
index = i;
for (let j = i + 1;j < arr.length;j++) {
if (min > arr[j]) {
min = arr[j];
index = j;
}
}
arr[index] = arr[i]
arr[i] = min;
}
return arr;
}
插入排序：
跟我們的打牌一樣： 從第一個(gè)開始 拿到這個(gè)值往前比較 找到比它小的值的時(shí)候停下來放在這里怀愧，簡單就是 找到合適的位置然后插入進(jìn)去
function charuSort(arr) {
let index, current;
for (let i = 1;i < arr.length;i++) {
index = i - 1;
current = arr[i]
while (current < arr[index] && index >= 0) {
arr[index + 1] = arr[index];
index--;
}
arr[index + 1] = current;
}
return arr;
}
快速排序
把數(shù)據(jù)分成兩組侨颈，選擇最中間的一個(gè)值 前后分成兩個(gè)，比中間這個(gè)值大的放后面 比這個(gè)值小的放在前面芯义。然后遞歸排列前后數(shù)組即可
var quickSort = function (arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0;i < arr.length;i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
希爾排序：是對插入排序的優(yōu)化肛搬。插入排序一次移動一位，而希爾排序是一次移動gap位毕贼。
希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)温赔，效率高，即可以達(dá)到線性排序的效率鬼癣。
但插入排序一般來說是低效的陶贼，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動一位。
為更加清晰地說明該排序待秃，貼一張其它地方轉(zhuǎn)載而來的圖片
這個(gè)代碼我看了好一段時(shí)間拜秧，都有點(diǎn)懵 難理解，最后弄個(gè)例子程序一步一步走才看懂了章郁。哎 我真笨
其實(shí)這個(gè)圖對我來說有點(diǎn)誤導(dǎo)性枉氮。
圖上看起來是一組一組的排好序的志衍，但是并不是。 而是設(shè)置一個(gè)值j = gap的時(shí)候聊替，就依次排楼肪，排到最后一個(gè) ，只是移動的間隔為gap惹悄。上圖上的分組是同時(shí)在進(jìn)行排序春叫。這樣排到后面的時(shí)候前面相應(yīng)間隔的數(shù)是已經(jīng)排好序了的。
//希爾排序
function shellSort(arr) {
let len = arr.length;
// gap 即為增量
for (let gap = Math.floor(len / 2);gap > 0;gap = Math.floor(gap / 2)) {
debugger
for (let i = gap;i < len;i++) {
let j = i;
let current = arr[i];
while (j - gap >= 0 && current < arr[j - gap]) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = current;
}
}
return arr;
}
let arr = [8, 5, 6, 1, 7, 3, 2, 4];
console.log(shellSort(arr));
希爾排序比直接插入排序優(yōu)點(diǎn)：
直接插入排序的問題：如果在后面來了一個(gè)特別小的元素泣港，需要全部移動暂殖，那么排序的效率特別低。
希爾排序優(yōu)點(diǎn)：如果在數(shù)組最后加入一個(gè)小元素当纱，他會被很快移到最前面呛每。
歸并排序
基本思想：先遞歸的分解數(shù)列，再合并數(shù)列
（1）將一個(gè)數(shù)組拆成A坡氯、B兩個(gè)小組晨横，兩個(gè)小組繼續(xù)拆，直到每個(gè)小組只有一個(gè)元素為止廉沮。
（2）按照拆分過程逐步合并小組颓遏，由于各小組初始只有一個(gè)元素，可以看做小組內(nèi)部是有序的滞时，合并小組可以被看做是合并兩個(gè)有序數(shù)組的過程叁幢。
（3）對左右兩個(gè)小數(shù)列重復(fù)第二步，直至各區(qū)間只有1個(gè)數(shù)坪稽。
代碼實(shí)現(xiàn)：
//輔助函數(shù)曼玩，傳入兩個(gè)數(shù)組，按大小順序插入新數(shù)組然后返回窒百。
function Merger(a, b) {
var n = a && a.length;
var m = b && b.length;
var c = [];
var i = 0, j = 0;
while (i < n && j < m) {
if (a[i] < b[j])
c.push(a[i++]);
else
c.push(b[j++]);
}
while (i < n)
c.push(a[i++]);
while (j < m)
c.push(b[j++]);
console.log("將數(shù)組", a, '和', b, '合并為', c)
return c;
}
//劃分?jǐn)?shù)組
function merge_sort(arr) {
console.log(arr)
if (arr.length == 1)
return arr
var mid = Math.floor(arr.length / 2)
var left = arr.slice(0, mid)
var right = arr.slice(mid)
return Merger(merge_sort(left), merge_sort(right)); //合并左右部分
}
let arr = [8, 5, 6, 1, 7, 3, 2, 4];
console.log(merge_sort(arr));
原文：歸并排序
堆排序
大佬鏈接：堆排序
前面步驟看懂了黍判，后面看代碼有點(diǎn)繞
//堆排序
// 交換兩個(gè)節(jié)點(diǎn)
function swap(A, i, j) {
let temp = A[i];
A[i] = A[j];
A[j] = temp;
}
// 將 i 結(jié)點(diǎn)以下的堆整理為大頂堆，注意這一步實(shí)現(xiàn)的基礎(chǔ)實(shí)際上是：
// 假設(shè) 結(jié)點(diǎn) i 以下的子堆已經(jīng)是一個(gè)大頂堆篙梢，shiftDown函數(shù)實(shí)現(xiàn)的
// 功能是實(shí)際上是：找到 結(jié)點(diǎn) i 在包括結(jié)點(diǎn) i 的堆中的正確位置顷帖。后面
// 將寫一個(gè) for 循環(huán)，從第一個(gè)非葉子結(jié)點(diǎn)開始渤滞，對每一個(gè)非葉子結(jié)點(diǎn)
// 都執(zhí)行 shiftDown操作贬墩，所以就滿足了結(jié)點(diǎn) i 以下的子堆已經(jīng)是一大
//頂堆
function shiftDown(A, i, length) {
let temp = A[i]; // 當(dāng)前父節(jié)點(diǎn)
// j<length 的目的是對結(jié)點(diǎn) i 以下的結(jié)點(diǎn)全部做順序調(diào)整
for (let j = 2 * i + 1;j < length;j = 2 * j + 1) {
temp = A[i]; // 將 A[i] 取出，整個(gè)過程相當(dāng)于找到 A[i] 應(yīng)處于的位置
if (j + 1 < length && A[j] < A[j + 1]) {
j++; // 找到兩個(gè)孩子中較大的一個(gè)妄呕，再與父節(jié)點(diǎn)比較
}
if (temp < A[j]) {
swap(A, i, j) // 如果父節(jié)點(diǎn)小于子節(jié)點(diǎn):交換陶舞；否則跳出
i = j; // 交換后，temp 的下標(biāo)變?yōu)?j
} else {
break;
}
}
}
// 堆排序
function heapSort(A) {
// 初始化大頂堆绪励，從第一個(gè)非葉子結(jié)點(diǎn)開始
debugger
for (let i = Math.floor(A.length / 2 - 1);i >= 0;i--) {
shiftDown(A, i, A.length);
}
// 排序肿孵，每一次for循環(huán)找出一個(gè)當(dāng)前最大值唠粥，數(shù)組長度減一
for (let i = Math.floor(A.length - 1);i > 0;i--) {
swap(A, 0, i); // 根節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)交換
shiftDown(A, 0, i); // 從根節(jié)點(diǎn)開始調(diào)整，并且最后一個(gè)結(jié)點(diǎn)已經(jīng)為當(dāng)
// 前最大值停做，不需要再參與比較晤愧，所以第三個(gè)參數(shù)
// 為 i，即比較到最后一個(gè)結(jié)點(diǎn)前一個(gè)即可
}
return A;
}
let arr = [8, 5, 6, 1, 7, 3, 2, 4];
console.log(heapSort(arr));
下面循環(huán)調(diào)用的shiftDown的時(shí)候 是從上到下雅宾，并把下面的非葉子節(jié)點(diǎn)的大小順序移動（养涮？葵硕？）
暫時(shí)不懂 有空再弄
堆排序是不同的選擇排序眉抬。
