默認情況下，sort() 會將元素轉換為字符串，然后按照 Unicode 編碼的順序進行排序：

const fruits = ['apple', 'banana', 'cherry', 'date'];
fruits.sort();
console.log(fruits); // 輸出: ["apple", "banana", "cherry", "date"]

直接使用默認排序對數字進行排序可能會得到不符合預期的結果，因為它會按字符串比較
為了正確排序數字或實現自定義排序規則，可以向 sort() 傳遞一個比較函數
比較函數接收兩個參數（通常稱為 a 和 b），并返回一個數值：

• 如果返回值 小于 0：a 會被排在 b 前面
• 如果返回值 等于 0：a 和 b 的相對位置不變
• 如果返回值 大于 0：b 會被排在 a 前面

//升序
arr.sort((a,b)=>{return a-b
})

基礎排序

冒泡排序

我們分最好、最壞和平均來看：

• 最好時間復雜度：它對應的是數組本身有序這種情況。在這種情況下，我們只需要作比較（n-1 次），而不需要做交換。時間復雜度為 O(n)
• 最壞時間復雜度： 它對應的是數組完全逆序這種情況。在這種情況下，每一輪內層循環都要執行，重復的總次數是 n(n-1)/2 次，因此時間復雜度是 O(n^2)
• 平均時間復雜度：這個東西比較難搞，它涉及到一些概率論的知識。實際面試的時候也不會有面試官摁著你讓你算這個，這里記住平均時間復雜度是 O(n^2) 即可。

function bubbleSort(arr) {let len = arr.length;for (let i = 0; i < len; i++) {for(let j=0;j<len-i-1;j++){if(arr[j]>arr[j+1]){[arr[j],arr[j+1]] = [arr[j+1],arr[j]]}}}console.log(arr);}

//改進版 最好的時間復雜度 O(n)function bubbleSort2(arr) {let len = arr.length;for (let i = 0; i < len; i++) {//增加標志位let flag = false;for(let j=0;j<len-i-1;j++){if(arr[j]>arr[j+1]){flag = true;[arr[j],arr[j+1]] = [arr[j+1],arr[j]]}}//一次交換都沒發生,說明數組是有序的if(!flag){break;}}console.log(arr);}

選擇排序

選擇排序的三個時間復雜度都對應兩層循環消耗的時間量級： O(n^2)。

function selectionSort(arr) {let len = arr.length;for(let i=0;i<len;i++){for(let j=i+1;j<len;j++){if(arr[i]>arr[j]){[arr[i],arr[j]] = [arr[j],arr[i]]}}}console.log(arr);}

插入排序

插入排序的核心,找到元素在它前面的那個序列中的正確位置
正確地定位當前元素在有序序列里的位置、不斷擴大有序數組的范圍，最終達到完全排序的目的。

• 最好時間復雜度：它對應的數組本身就有序這種情況。此時內層循環只走一次，整體復雜度取決于外層循環，時間復雜度就是一層循環對應的 O(n)。

• 最壞時間復雜度：它對應的是數組完全逆序這種情況。此時內層循環每次都要移動有序序列里的所有元素，因此時間復雜度對應的就是兩層循環的 O(n^2)

• 平均時間復雜度：O(n^2)

function insertionSort(arr) {let len = arr.length;let temp ; //保存當前變量for(let i=1;i<len;i++){temp = arr[i];let j = i;//j來幫助temp找到自己的位置while(j>0 && temp < arr[j-1]){arr[j] = arr[j-1];j--;}arr[j] = temp;}console.log(arr);}

進階排序算法

分治思想

分解子問題
求解子問題
合并子問題的解

歸并排序

歸并排序的時間復雜度就是 O(nlog(n))

• 分解子問題：將需要被排序的數組從中間分割為兩半，然后再將分割出來的每個子數組各分割為兩半，重復以上操作，直到單個子數組只有一個元素為止。
• 求解每個子問題：從粒度最小的子數組開始，兩兩合并、確保每次合并出來的數組都是有序的。（這里的“子問題”指的就是對每個子數組進行排序）。
• 合并子問題的解，得出大問題的解：當數組被合并至原有的規模時，就得到了一個完全排序的數組

function mergeSort(arr) {const len = arr.length;if (len < 2) {return arr;}//計算分割點const middle = Math.floor(len / 2);//分割數組const leftArr = mergeSort(arr.slice(0, middle));const rightArr = mergeSort(arr.slice(middle, len));//合并兩個有序數組return merge(leftArr, rightArr);}
//兩個有序數組合并function merge(leftArr, rightArr) {let i = 0;let j = 0;//初始化結果數組const res = [];// 檢查 leftArr 和 rightArr 是否為 undefinedconst len1 = leftArr? leftArr.length : 0;const len2 = rightArr? rightArr.length : 0;while (i < len1 && j < len2) {if (leftArr[i] < rightArr[j]) {res.push(leftArr[i]);i++;} else {res.push(rightArr[j]);j++;}}//將剩余的數組元素添加到結果數組中while (i < len1) {res.push(leftArr[i]);i++;}while (j < len2) {res.push(rightArr[j]);j++;}return res;}

快速排序

快速排序在基本思想上和歸并排序是一致的，仍然堅持“分而治之”的原則不動搖。區別在于，快速排序并不會把真的數組分割開來再合并到一個新數組中去，而是直接在原有的數組內部進行排序。

快速排序會將原始的數組篩選成較小和較大的兩個子數組，然后遞歸地排序兩個子數組。

//快速排序 o(nlogn)function quickSort(arr,left=0,right=arr.length-1){//定義遞歸邊界,若數組只有一個元素不用排序if(arr.length > 1){//下一次劃分左右數組的索引位置const lineIndex = partition(arr,left,right);//對左子數組進行快排if(left<lineIndex-1){quickSort(arr,left,lineIndex-1);}//對右子數組進行快排if(lineIndex<right){quickSort(arr,lineIndex,right);}}return arr;}