在學(xué)習(xí)了極客時間的數(shù)據(jù)結(jié)構(gòu)之后巍耗，根據(jù)排序的原理秋麸，我用JS重新實(shí)現(xiàn)了一遍，配圖來自極客時間的配圖炬太，因?yàn)槲覍?shí)在找不出比他寫的更好的了灸蟆。
學(xué)習(xí)方法：
講排序之前，先說一下學(xué)習(xí)方法，那就是debug模式，在JS中噩死，直接在循環(huán)里添加debugger，打開F12斋枢，F(xiàn)5刷新一下，就可以看到數(shù)組的變化情況了知给，對學(xué)習(xí)非常有幫助瓤帚，我就是這樣學(xué)的，在Java中涩赢，則是Eclipse進(jìn)入Debug模式戈次，我還是喜歡JS，因?yàn)楦庇^筒扒。
冒泡排序
原理：
冒泡排序是最簡單的怯邪，只需要通過兩次遍歷，兩兩交換花墩，就可以實(shí)現(xiàn)排序悬秉。
代碼：
let arr = [145, 248, 31, 45, 9, 11, 145, 300];
//冒泡排序
function arrSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {//遍歷澄步，這里，arr.length-1搂捧，是因?yàn)樽詈笠淮尾挥醚h(huán)了驮俗。
for (let j = 0; j < arr.length - i ; j++) {//雙重遍歷懂缕，遍歷i之后的數(shù)允跑，例如有8個元素，i在第一項(xiàng)搪柑，那么遍歷后面7項(xiàng)聋丝。
if(arr[j] < arr[j-1]){//如果右邊，小于左邊工碾，那么交換位置弱睦。
let temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
return arr;
}
console.log(arrSort(arr));
空間復(fù)雜度：因?yàn)橹簧婕暗浇粨Q，只需要常量級的臨時空間渊额，所以空間復(fù)雜度為O(1)
時間復(fù)雜度：最好O(n)况木，最壞O(n2)，平均O(n2)
使用場景：數(shù)據(jù)量小于1000
穩(wěn)定性：穩(wěn)定
插入排序
原理：
1旬迹、從第二個元素開始火惊，遍歷它之前的元素。
2奔垦、如果他之前的元素屹耐，大于他，那么交換椿猎。并繼續(xù)往前遍歷之前比它大的元素惶岭。
代碼實(shí)現(xiàn)：
//插入排序
let arr = [145, 248, 31, 45, 9, 11, 145, 300];
function arrSort(array) {
for(let i = 1; i < array.length; i++) {//遍歷一波數(shù)組,從數(shù)組第二項(xiàng)開始遍歷
let key = array[i];//這里必須要定義，因?yàn)檠h(huán)結(jié)束犯眠，會用到按灶。
let j = i - 1;//定義j為i-1,在第一次遍歷，是從數(shù)組第一項(xiàng)開始
while(j >= 0 && array[j] > key) {//如果j的值大于i的值筐咧，也就是左邊的大于右邊的鸯旁，j>=0，防止j--變負(fù)數(shù)嗜浮。
array[j + 1] = array[j];//例如第二項(xiàng)和第三項(xiàng)248和31羡亩，那么變成，248危融，248
j--;//如果248>31執(zhí)行成功了畏铆，變成了248,248,那么依次判斷左邊，是否有小于 的吉殃。
}
array[j + 1] = key;//把第一項(xiàng)賦值成最小的那個辞居。
}
return array;
}
console.log(arrSort(arr));
空間復(fù)雜度：因?yàn)椴恍枰~外的存儲空間楷怒，所以空間復(fù)雜度為O(1)
時間復(fù)雜度：最好O(n)，最壞O(n2)瓦灶，平均O(n2)
使用場景：數(shù)據(jù)量小于1000
穩(wěn)定性：穩(wěn)定
選擇排序
原理：跟冒泡排序差不多鸠删，也是兩兩交換，不過這兩兩交換贼陶，是第一位和第五位交換刃泡，而不是第四位和第五位。
代碼：
//選擇排序
let arr = [145, 248, 31, 45, 9, 11, 145, 300];
function arrSort(arr){
for(let i = 0; i < arr.length - 1; i++){//遍歷數(shù)組
let min = arr[i];//防止arr[i]發(fā)生變化
for(let j = i + 1; j < arr.length; j++){//雙重遍歷碉怔，查找最小的數(shù)進(jìn)行交換烘贴，跟冒泡不一樣的地方在于，選擇排序撮胧，假如第4位更小桨踪，則是1，4位交換芹啥，不是3锻离，4位交換
if(min > arr[j]){
let temp = min;
min = arr[j];
arr[j] = temp;
}
}
arr[i] = min;
}
return arr;
}
console.log(arrSort(arr));
空間復(fù)雜度：空間復(fù)雜度為O(1)
時間復(fù)雜度：最好O(n2)，最壞O(n2)墓怀，平均O(n2)
使用場景：數(shù)據(jù)量小于1000
穩(wěn)定性：不穩(wěn)定汽纠，因?yàn)闀龅街貜?fù)的數(shù)。
歸并排序
原理：歸并排序使用了非常好的分治思想捺疼，把一個數(shù)組疏虫，分成兩部分，排序之后啤呼，較小的那個值取出來放在第一個位置卧秘，再合并。
代碼：
//分治排序
let arr = [145, 248, 31, 45, 9, 11, 145, 300];
function merge(left, right) {
let result = [];
while(left.length > 0 && right.length > 0) {//如果兩邊數(shù)組都有值
if(left[0] < right[0]) {//左邊小于右邊
result.push(left.shift());//給result數(shù)組添加值官扣，并在left刪掉值
}
else {
result.push(right.shift());//給result數(shù)組添加值翅敌，并在right刪掉值
}
}
/* 當(dāng)左右數(shù)組長度不等.將比較完后剩下的數(shù)組項(xiàng)鏈接起來即可 */
return [...result,...left,...right];//這里用es6的語法，只是一個簡寫惕蹄，百度一眼就會蚯涮。...left...right是因?yàn)槿f一長度不相等，會少數(shù)卖陵，所以會加這兩個遭顶。
}
function mergeSort(arr){
if(arr.length==1){//如果數(shù)組長度為1則返回?cái)?shù)組
return arr
};
let mid=Math.floor(arr.length/2);//分成兩部分
let left_arr=arr.slice(0,mid);//數(shù)組分成兩份后，塞進(jìn)去泪蔫。假如說數(shù)組有8個元素棒旗，分成兩部分，左邊(0,4)
let right_arr=arr.slice(mid);//右邊(4到后面所有)
return merge(mergeSort(left_arr),mergeSort(right_arr));//遞歸
}
console.log(mergeSort(arr));
空間復(fù)雜度：因?yàn)椴皇窃嘏判蛄萌伲枰渌目臻g铣揉，所以空間復(fù)雜度為O(n)
時間復(fù)雜度：最好O(nlogn)饶深，最壞O(nlogn)，平均O(nlogn)
使用場景：數(shù)據(jù)量大于1000
穩(wěn)定性：穩(wěn)定逛拱。
快速排序
原理：和歸并排序一樣敌厘，也是利用了分治思想，但是快排是選擇一個中間數(shù)朽合，然后比它小的放左邊俱两，比它大的放右邊。
代碼：
//快速排序
let arr = [145, 248, 31, 45, 9, 11, 145, 300];
function arrSort(arr){
if (arr.length <= 1){
return arr
};
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex,1)[0];//取出中間的數(shù)字旁舰，比如第一次就取出9
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if(arr[i] < pivot) {//第一次運(yùn)算锋华，如果小于9就進(jìn)入左數(shù)組嗡官，大于就進(jìn)入右數(shù)組
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return arrSort(left).concat([pivot],arrSort(right));//遞歸箭窜，再把左數(shù)組分成兩半進(jìn)行排序，右數(shù)組同理衍腥。
}
console.log(arrSort(arr));
空間復(fù)雜度：最好O(logn) 最差O(n)
時間復(fù)雜度：最好O(nlogn)磺樱，最壞O(n2) ，平均O(nlogn)
使用場景：數(shù)據(jù)量大于1000
穩(wěn)定性：不穩(wěn)定婆咸。
我們用快排比歸并用的多竹捉，原因就在于歸并他不是原地排序，空間復(fù)雜度比較高尚骄。
希爾排序
原理：
希爾排序是根據(jù)增量（中間隔一段距離）块差，實(shí)現(xiàn)跳躍式的移動，使得排序的效率提高倔丈。在最后一輪中憨闰，增量必須等于1，另外需五，由于是跳躍式的移動鹉动，希爾排序并不是一種穩(wěn)定的排序算法。
舉一個小小的例子：
一個數(shù)組有8個元素宏邮，8%2==4泽示，第一輪中間隔4個，4%2==2蜜氨，第二輪中間隔2個……
第一輪械筛，第一項(xiàng)和第五項(xiàng)，第二項(xiàng)和第六項(xiàng)飒炎，第三項(xiàng)和第七項(xiàng)埋哟，第四項(xiàng)和第八項(xiàng)。
第二輪厌丑，第一項(xiàng)和第三項(xiàng)定欧，第二項(xiàng)和第四項(xiàng)渔呵，第三項(xiàng)和第五項(xiàng)，第四項(xiàng)和第六項(xiàng)砍鸠，第五項(xiàng)和第七項(xiàng)……
//希爾排序
let arr = [145, 248, 31, 45, 9, 11, 145, 300];
function arrSort(arr){
let gap =Math.floor(arr.length/2);
while(gap>=1){
for(let i = gap;i<arr.length;i++){
let j,temp=arr[i];
for(j=i-gap;j>=0&&temp<arr[j];j=j-gap){
arr[j+gap]=arr[j];
}
arr[j+gap]=temp;
}
gap=Math.floor(gap/2);
}
return arr;
}
console.log(arrSort(arr));
空間復(fù)雜度：O(1)
時間復(fù)雜度：最好O(nlog2n)，最壞O(nlog2n)爷辱，平均O(nlogn)
使用場景：數(shù)據(jù)量大于1000
穩(wěn)定性：不穩(wěn)定录豺。
此外，還有桶排序饭弓，計(jì)數(shù)排序双饥，堆排序，基數(shù)排序等弟断，作者還在研究當(dāng)中咏花。
