基本排序算法

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]