一、冒泡排序

// 冒泡排序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);  // 保持不变