《算法导论》读书笔记-几种常见的排序算法

[Hugo-seth]

《算法导论》前四章介绍了几种简单的排序算法，这里用 js 整理成代码。由于高数没学好，所以关于复杂度的分析实在是看不太懂 😓

首先说明：排序的数据结构都是 js 的数组，index 是从 0 开始到 length - 1

• 插入排序

  插入排序：从 index i = 1 开始，循环与 index < i比较，将数据插入到合适位置。代码如下：

function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
       let j = i - 1;
       while (j >= 0 && arr[j + 1] < arr[j]) {
          [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
          j--;
       }
    }
    return arr;
}

• 冒泡排序

  冒泡排序：反复比较相邻的两个数，如果左边大于右边，则交换位置。代码如下：

function bubbleSort(arr) {
    let length = arr.length;
    for (let i = 0; i < length; i++) {
       for (let j = i; j < length - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) {
             [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
          }
       }
    }
    return arr;
}

• 选择排序

  选择排序：先将数组中最小的数交换到 arr[0]，再将第二小的数交换到 arr[1]，如此反复。代码如下：

function selectSort(arr) {
    let length = arr.length;
    let currentMin, currentMinIndex;
    for (let i = 0; i < length - 1; i++) {
       currentMin = arr[i];
       currentMinIndex = i;
       for (let j = i; j < length; j++) {
          if (currentMin > arr[j]) {
             currentMin = arr[j];
             currentMinIndex = j;
          }
          if (j === length - 1 && currentMinIndex !== i) {
             [arr[i], arr[currentMinIndex]] = [arr[currentMinIndex], arr[i]]
          }
       }
    }
    return arr;
}

• 归并排序

  归并排序：将原数组递归拆分成长度为一的最小数组，再两两组合排序，生成最终顺序数组（觉得讲的不是很清楚，结合书上章节及插图会好理解的多）。代码如下：

function mergeSort(arr) {
    let len = arr.length
    if (len < 2) {
      return arr
    }
    let middle = Math.floor(len / 2),
      left = arr.slice(0, middle),
      right = arr.slice(middle)

    return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
    let result = []

    while (left.length && right.length) {
      if (left[0] <= right[0]) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    }

    while (left.length) {
      result.push(left.shift())
    }

    while(right.length) {
      result.push(right.shift())
    }

    return result
}