1. 冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，一次比较两个元素，如果它们的顺序错误就交换它们。遍历的过程会持续多次，每次遍历都会将未排序部分中的最大元素移动到末尾。
/**
* 冒泡排序
* 遍历数组，对于每个元素，与其后一个元素进行比较，如果前一个元素大于后一个元素，则交换它们的位置
*
* @param arr 要排序的数组
*/
function bubbleSort(arr) {
// 获取数组的长度
const n = arr.length;
// 遍历数组
for (let i = 0; i < n; i++) {
// 遍历数组中未排序的部分
for (let j = 0; j < n - i - 1; j++) {
// 如果前一个元素大于后一个元素，则交换它们的位置
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
}
// 定义要排序的数组
let arr = [64, 34, 25, 12, 22, 11, 90];
// 调用bubbleSort()函数对数组进行冒泡排序
bubbleSort(arr);
// 输出排序后的数组
console.log("冒泡排序结果:", arr);
2. 选择排序（Selection Sort）
选择排序是一种简单直观的排序算法，它首先在未排序的序列中找到最小（或最大）元素，然后将其放到序列的起始位置，接着从剩余的未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。重复这个过程，直到所有元素都排序完毕。
/**
* 选择排序
*遍历数组，找出最小元素的索引，将其与当前元素交换
* @param arr 要排序的数组
*/
function selectionSort(arr) {
// 获取数组的长度
const n = arr.length;
// 遍历数组
for (let i = 0; i < n; i++) {
// 找出最小元素的索引
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换当前元素与最小元素的位置
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
// 定义要排序的数组
let arr = [64, 34, 25, 12, 22, 11, 90];
// 调用selectionSort()函数对数组进行选择排序
selectionSort(arr);
// 输出排序后的数组
console.log("选择排序结果:", arr);
3. 插入排序（Insertion Sort）
插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序每次将一个待排序的元素插入到已排序序列的适当位置，直到全部元素排序完毕。
/**
* 插入排序
*
* @param arr 待排序的数组
*/
function insertionSort(arr) {
// 获取数组长度
const n = arr.length;
// 从第二个元素开始遍历
for (let i = 1; i < n; i++) {
// 将当前元素作为待插入的键值
let key = arr[i];
// 从当前元素的前一个元素开始向前遍历
let j = i - 1;
// 当遍历到的元素大于键值并且索引大于等于0时，将遍历到的元素后移一位
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// 将键值插入到正确的位置
arr[j + 1] = key;
}
}
let arr = [64, 34, 25, 12, 22, 11, 90];
insertionSort(arr);
console.log("插入排序结果:", arr);
4. 归并排序（Merge Sort）
归并排序是一种分治算法，它将待排序的列表分为两个子序列，分别对两个子序列进行递归排序，然后将两个有序子序列合并成一个有序序列。归并排序的关键在于合并操作，将两个有序序列合并成一个有序序列的过程。
/**
* 使用归并排序算法对数组进行排序
*
* @param arr 需要排序的数组
* @returns 排序后的数组
*/
function mergeSort(arr) {
// 如果数组长度小于等于1，则直接返回该数组
if (arr.length <= 1) {
return arr;
}
// 计算数组中间位置
const mid = Math.floor(arr.length / 2);
// 对左半部分进行归并排序
const left = mergeSort(arr.slice(0, mid));
// 对右半部分进行归并排序
const right = mergeSort(arr.slice(mid));
// 合并左右两部分排序后的数组
return merge(left, right);
}
/**
* 合并两个有序数组
*
* @param left 左侧有序数组
* @param right 右侧有序数组
* @returns 返回合并后的有序数组
*/
function merge(left, right) {
let result = [];
let i = 0;
let j = 0;
// 当左右两个数组都有元素时
while (i < left.length && j < right.length) {
// 将较小的元素添加到结果数组中
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
// 当左数组还有剩余元素时
while (i < left.length) {
result.push(left[i]);
i++;
}
// 当右数组还有剩余元素时
while (j < right.length) {
result.push(right[j]);
j++;
}
// 返回合并后的数组
return result;
}
/**
* 合并两个已排序好的数组，返回一个新数组，新数组也是已排序的
*
* @param left 左侧已排序数组
* @param right 右侧已排序数组
* @returns 返回合并后已排序的新数组
*/
function merge(left, right) {
// 创建一个空数组用于存储合并后的结果
let result = [];
// 定义左数组索引
let leftIndex = 0;
// 定义右数组索引
let rightIndex = 0;
// 当左右两个数组都还有元素时执行循环
while (leftIndex < left.length && rightIndex < right.length) {
// 如果左数组当前元素小于右数组当前元素
if (left[leftIndex] < right[rightIndex]) {
// 将左数组当前元素添加到结果数组中
result.push(left[leftIndex]);
// 左数组索引加1
leftIndex++;
} else {
// 否则将右数组当前元素添加到结果数组中
result.push(right[rightIndex]);
// 右数组索引加1
rightIndex++;
}
}
// 循环结束后，将左数组剩余的元素添加到结果数组中
// 使用slice方法从leftIndex开始截取左数组剩余的元素
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
let arr = [64, 34, 25, 12, 22, 11, 90];
arr = mergeSort(arr);
console.log("归并排序结果:", arr);
5. 快速排序（Quick Sort）
快速排序是一种分治算法，它选择一个基准元素，将列表分为两部分，使得左边的元素都小于基准元素，右边的元素都大于基准元素，然后对左右两部分递归地进行快速排序。快速排序的关键在于分区操作，将列表中的元素按照基准元素进行分区。
/**
* 快速排序函数
*
* @param arr 待排序数组
* @returns 排序后的数组
*/
function quickSort(arr) {
// 如果数组长度小于等于1，则直接返回数组
if (arr.length <= 1) {
return arr;
}
// 选取数组最后一个元素作为枢轴
const pivot = arr[arr.length - 1];
// 初始化左、右两个空数组
const left = [];
const right = [];
// 遍历数组，将小于枢轴的元素放入左数组，大于等于枢轴的元素放入右数组
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// 对左、右两个数组进行递归排序，并将排序结果和枢轴拼接起来返回
return quickSort(left).concat(pivot, quickSort(right));
}
let arr = [64, 34, 25, 12, 22, 11, 90];
arr = quickSort(arr);
console.log("快速排序结果:", arr);
6. 堆排序（Heap Sort）
堆排序利用了堆这种数据结构的特性，将待排序的列表构建成一个最大堆或最小堆，然后将堆顶元素与堆的最后一个元素交换，然后调整堆，使得剩余元素仍构成一个最大堆或最小堆，依次类推，直到所有元素都排序完毕。
/**
* 对给定的数组进行堆排序
*
* @param arr 待排序的数组
*/
function heapSort(arr) {
const n = arr.length; // 获取数组的长度
// 从最后一个非叶子节点开始，向上到根节点，逐个进行堆化
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 从堆顶开始，将最大值与堆尾元素交换，然后重新堆化剩下的元素
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]]; // 交换堆顶元素和当前元素
heapify(arr, i, 0); // 重新对剩下的元素进行堆化
}
}
/**
* 将数组 arr 中以索引 i 为根节点的子树堆化
*
* @param arr 数组
* @param n 数组长度
* @param i 当前节点索引
*/
function heapify(arr, n, i) {
let largest = i; // 初始化最大值为当前节点
const left = 2 * i + 1; // 左子节点索引
const right = 2 * i + 2; // 右子节点索引
// 如果左子节点大于当前最大值，则更新最大值
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点大于当前最大值，则更新最大值
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是当前节点，则交换它们，并继续堆化子树
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]]; // 交换节点
heapify(arr, n, largest); // 堆化子树
}
}
// 示例数组
let arr = [64, 34, 25, 12, 22, 11, 90];
// 对示例数组进行堆排序
heapSort(arr);
// 输出排序后的结果
console.log("堆排序结果:", arr); // 输出：[11, 12, 22, 25, 34, 64, 90]
