排序算法

手写快速排序？

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    // 选择一个基准值（pivot），这里选择数组的最后一个元素
    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));
}

// 示例使用
const array = [3, 6, 8, 10, 1, 2, 1];
const sortedArray = quickSort(array);
console.log(sortedArray); // 输出: [1, 1, 2, 3, 6, 8, 10]

手写归并排序

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    // 找到中间索引，将数组分成两半
    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    // 递归地对左右两半进行排序
    return merge(mergeSort(left), mergeSort(right));
}

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]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    // 如果左边或右边还有剩余元素，将它们添加到结果数组中
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// 示例使用
const array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const sortedArray = mergeSort(array);
console.log(sortedArray); // 输出: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

冒泡排序

/**
 * 1. 从第一个元素开始，比较相邻的两个元素，前者大就交换位置
 * 2. 每次遍历结束，都能找到一个最大值
 * 3. 如果还有没排序的元素继续1
 * 
 */
const swap = (array, a, b) => [ array[ b ], array[ a ] ] = [ array[ a ], array[ b ] ]
const bubbleSort = (array) => {
  const length = array.length
  for (let i = 0; i < length - 1; i++) {
    for (let j = 0; j < length - 1 - i; j++) {
      if (array[ j ] > array[ j + 1 ]) {
        swap(array, j, j + 1)
      }
    }
  }

  return array
}

console.log(bubbleSort([ -1, 10, 10, 2 ]))

选择排序

/**
 * 1. 取出未排序的第一个元素，遍历该元素之后的部分并进行比较。第一次就是取第一个元素
 * 2. 如果有更小的就交换位置
 */

 const swap = (array, a, b) => [ array[ b ], array[ a ] ] = [ array[ a ], array[ b ] ]
 
const selectSort = (array) => {
  const length = array.length

  for (let i = 0; i < length; i++) {
    let minIndex = i

    for (let j = i + 1; j < length; j++) {
      if (array[ j ] < array[ minIndex ]) {
        minIndex = j
      }
    }

    if (minIndex !== i) {
      swap(array, i, minIndex)
    }
  }

  return array
}

console.log(selectSort([ -1, 10, 10, 2 ]))

插入排序

const insertSort = (array) => {
  for (let i = 1, length = array.length; i < length; i++) {
    let j = i - 1
    const curValue = array[ i ]

    while (j >= 0 && array[ j ] > curValue) {
      array[ j + 1 ] = array[ j ]
      j--
    }

    array[ j + 1 ] = curValue
  }

  return array
}

console.log(insertSort([ -1, 10, 10, 2 ]))