一、冒泡排序 原理：相鄰兩元素之間兩兩比較，比較出大值進行賦值互換，再依次與相鄰的元素比較，層層遞進。#互換元素位置，相互賦值。 時間複雜度：最好O(n)，最差O(n^2) 1、比較相鄰的兩個元素，如果前一個比後一個大，則交換位置。2、比較完第一輪的時候，最後一個元素是最大的元素。3、這時候最後一個 ...
一、冒泡排序
原理：相鄰兩元素之間兩兩比較，比較出大值進行賦值互換，再依次與相鄰的元素比較，層層遞進。#互換元素位置，相互賦值。
時間複雜度：最好O(n)，最差O(n^2)
1、比較相鄰的兩個元素，如果前一個比後一個大，則交換位置。
2、比較完第一輪的時候，最後一個元素是最大的元素。
3、這時候最後一個元素是最大的，所以最後一個元素就不需要參與比較大小。
const 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]){
var temp = 0;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
console.log(bubbleSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]解析
兩個迴圈，當i=0的時候，裡面的迴圈完整執行，從j=0執行到j=7，結果是將最大的數排到了最後。當i=1的時候，裡面的迴圈再次完整執行，由於最大的數已經在最後了，沒有必要去比較數組的最後兩項，這也是j<arr.length-1-i的巧妙之處。
二、選擇排序
原理：先定義一個元素的最大值或最小值，拿每個元素與最值比較，取大值放到數組最右端，或者最小值放到數組最左端，層層比較。#互換元素下標位置，再賦值。
時間複雜度：O(n^2)
const selectionSort = (arr)=>{
let minIndex,temp;
for(let i = 0 ; i < arr.length ; i++){
minIndex = i;
for(let j = i + 1 ; j < arr.length ; j++){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
console.log(selectionSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]解析
首先從原始數組中找到最小的元素，並把該元素放在數組的最前面，然後再從剩下的元素中尋找最小的元素，放在之前最小元素的後面，直到排序完畢。
minIndex始終保存著最小值的位置的索引，隨著i的自增，遍歷的數組長度越來越短，直到完成排序。
三、歸併排序
歸併排序（MERGE-SORT）是利用歸併的思想實現的排序方法，
該演算法採用經典的分治（divide-and-conquer）策略
（分治法將問題分(divide)成一些小的問題然後遞歸求解，
而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。
歸併排序採用的是分治的思想，首先是“分”，將一個數組反覆二分為兩個小數組，直到每個數組只有一個元素；其次是“治”，從最小數組開始，兩兩按大小順序合併，直到併為原始數組大小，下麵是圖解：
“分”就是將原始數組逐次二分，直到每個數組只剩一個元素，一個元素的數組自然是有序的，所以就可以開始“治”的過程了。
時間複雜度分析：分的過程需要三步：log8 = 3，而每一步都需要遍歷一次8個元素，所以8個元素共需要運行 8log8 次指令，那麼對於 n 個元素，時間複雜度為 O(nlogn)。
“治”實際上是將已經有序的數組合併為更大的有序數組。那怎麼做呢?就是創建一個新數組，比較left[0]和right[0] ，那個比較小就將那個的值放進新數組，然後再繼續比較left[0]和right[1]，或者是left[1]和right[0]。可以看出數組left，right都只需遍歷一遍，所以對兩個有序數組的排序的時間複雜度為O(n)。
一、遞歸分解
二、合併為有序數組
const mergeSort = (arr)=>{
let len = arr.length;
if(len < 2){
return arr;
}
let mid = Math.floor(len/2);
//拆分成兩個子數組
let left = arr.slice(0,mid);
let right = arr.slice(mid,len);
//遞歸拆分
let mergeSortLeft = mergeSort(left);
let mergeSortRight = mergeSort(right);
//組合
return merge(mergeSortLeft,mergeSortRight)
}
const merge = (left,right)=>{
const arr1 = [];
while(left.length && right.length){
// 註意: 判斷的條件是小於或等於，如果只是小於，那麼排序將不穩定.
if(left[0]<=right[0]){
//每次都要刪除left或者right的第一個元素，將其加入arr1中
arr1.push(left.shift());
}else{
arr1.push(right.shift());
}
}
//將剩下的元素加上
while(left.length) arr1.push(left.shift());
while(right.length) arr1.push(right.shift());
return arr1;
}
console.log(mergeSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]參考： https://www.cnblogs.com/lyt0207/p/12489144.html
四、快速排序
"快速排序"的思想很簡單，整個排序過程只需要三步：
（1）在數據集之中，選擇一個元素作為"基準"（pivot）。
（2）所有小於"基準"的元素，都移到"基準"的左邊；所有大於"基準"的元素，都移到"基準"的右邊。
（3）對"基準"左邊和右邊的兩個子集，不斷重覆第一步和第二步，直到所有子集只剩下一個元素為止。
//首先，定義一個quickSort函數，它的參數是一個數組。
const quickSort = (arr)=>{
//然後，檢查數組的元素個數，如果小於等於1，就返回。
if(arr.length <= 1){
return arr;
}
//接著，選擇"基準"（pivot），並將其與原數組分離，再定義兩個空數組，用來存放一左一右的兩個子集。
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex,1)[0];
var left = [];
var right = [];
//然後，開始遍曆數組，小於"基準"的元素放入左邊的子集，大於基準的元素放入右邊的子集。
for(let 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));
}
console.log(quickSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]
