一、冒泡排序

// 冒泡排序var bubbleSort = function (arr) {const len = arr.length;for (let i = 0; i < len; i++) {let isSwap = false;for (let j = 0; j < len - 1; j++) {// 每一次遍歷都要比較相鄰元素的大小，如果滿足條件就交換位置if (arr[j] > arr[j + 1]) {[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];isSwap = true;}}// 如果遍歷完數組后沒有發生交換，說明已經排序好了，跳出循環，中斷剩余操作if (!isSwap) {break;}}return arr;
}console.log(bubbleSort([7, 3, 2, 21, 12, 1, 4, 9, 10]));

二、選擇排序

// 選擇排序var selectionSort = function (arr) {const len = arr.length;// 外循環的 i 指向需要替換的位置，而 i 之前是已經排序的數組for (let i = 0; i < len - 1; i++) {let minIndex = i;// 內循環是在未排序好的數組中找最小值的索引for (let j = i + 1; j < len; j++) {if (arr[minIndex] > arr[j]) {minIndex = j;}}// 找到最小值的索引后交換位置即可[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];}return arr;
}console.log(selectionSort([7, 3, 2, 21, 12, 1, 4, 9, 10]));

三、插入排序

// 插入排序var insertionSort = function (arr) {const len = arr.length;for (let i = 1; i < len; i++) {base = arr[i]; // 將未排序數組中的第一個元素作為基數let j = i - 1; // j 指向已排序好的數組的最后一個元素while (j >= 0 && arr[j] > base) {arr[j + 1] = arr[j]; // 如果以上滿足條件，元素 arr[j] 后移一位j--; // 向前遍歷}// 因為 j 在最后一次循環中減了一次，此時 j + 1 之后的元素都小于 base，所以 base 要插入的正確的位置是 j + 1arr[j + 1] = base;}return arr;
}console.log(insertionSort([7, 3, 2, 21, 12, 1, 4, 9, 10]));

四、快速排序

// 快速排序 O(n log n)// 分治
var partition = function (arr, left, right) {let i = left, j = right;let base = arr[left]; // 每次將 arr[left] 作為基數while (i < j) {// 在右邊數組找比基數小的數的索引while (i < j && arr[j] >= base) {j--;}while (i < j && arr[i] <= base) {i++;}// 交換位置[arr[i], arr[j]] = [arr[j], arr[i]];}// 此時 i 索引指向的就是基數應該處于的位置[arr[i], arr[left]] = [arr[left], arr[i]];console.log("arr:", arr);return i;
}// 遞歸
var quickSort = function (arr, left, right) {// 遞歸終止條件if (left >= right) {return;}// 遞歸操作// 找到基數所在的索引作為中間支點let pivot = partition(arr, left, right);// 左遞歸quickSort(arr, left, pivot - 1);// 右遞歸quickSort(arr, pivot + 1, right);
}
let arr = [7, 3, 2, 21, 12, 1, 4, 9, 10, 31, 64, 108, 13, 5];
let len = arr.length - 1;
quickSort(arr, 0, len);

五、歸并排序

// 歸并排序var mergeSort = function (arr) {// 遞歸終止條件if (arr.length <= 1) {return arr;}// 遞歸操作const mid = arr.length / 2;// 拆分數組const leftArr = mergeSort(arr.slice(0, mid));const rightArr = mergeSort(arr.slice(mid));return merge(leftArr, rightArr);
}// 歸并操作
var merge = function (leftArr, rightArr) {let left = 0, right = 0;let ans = [];// 按需歸并while (left < leftArr.length && right < rightArr.length) {if (leftArr[left] <= rightArr[right]) {ans.push(leftArr[left]);left++;} else {ans.push(rightArr[right]);right++;}}// 剩余元素直接追加return ans.concat(leftArr.slice(left)).concat(rightArr.slice(right));
}// ======== 測試 ========
const arr = [7, 3, 2, 21, 12, 1, 4, 9, 10, 108, 24, 35, 5, 8, 124];
console.log('排序后:', mergeSort(arr));
console.log('原數組是否改變:', arr);  // 保持不變