算法之基础排序算法

排序算法是《数据结构与算法》中最基础的算法之一。

在排序算法中，常见的基础排序算法主要有四种：冒泡排序、选择排序、插入排序、希尔排序。

下面分别介绍几种基础的排序算法。

冒泡排序#

算法步骤#

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻的元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对元素需要比较。

代码演示#

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = i + 1; j < len; j++) {
      if (arr[i] > arr[j]) {
        // 相邻元素两两对比，前一个元素比后一个元素大时
        // 元素交换（即小的交换到前面来）
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
  }
  return arr;
}

优化：减少内循环不必要的比较

function bubbleSort2(arr) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    // 优化：j < len - 1 - i; 后面的已经是排好的比较大的数了，不用再比较了
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 交换变量
      }
    }
  }
  return arr;
}

小结#

冒泡排序的平均时间复杂度：O(N^2)，在实际生产环境中不推荐使用。

选择排序#

算法步骤#

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序 1。

代码演示#

function selectionSort(arr) {
  let len = arr.length;
  let minIndex;
 
  for (let i = 0; i < len - 1; i++) {
    minIndex = i; // 寻找最小值，初始值为 i
 
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j; // 将最小值索引保存
      }
    }
 
    // 如果一样就不用交换，节省时间
    if (i !== minIndex) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // 交换变量
    }
  }
  return arr;
}

小结#

选择排序的平均时间复杂度：O(N^2)，在实际生产环境中不推荐使用。

插入排序#

算法步骤#

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从第二个元素开始，依次和前面的元素进行比较，如果发现元素比它大，交换位置，这样前二个的元素排序完成。
再第三个元素开始...以此类推，最后完成排序。

代码演示#

function insertionSort(arr) {
  const len = arr.length;
 
  for (let i = 0; i < len; i++) {
    for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
      [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]; // 交换变量
    }
  }
 
  return arr;
}

优化：内循环只交换一次

function insertionSort2(arr) {
  const len = arr.length;
 
  for (let i = 0; i < len; i++) {
    let cur = arr[i]; // 保存待插入的元素
    let j = i; // 保存元素 cur 应该插入的位置
 
    // 依次和前面的元素进行比较，如果它前一个元素比它大，这个元素往后挪一个位置，然后继续比较寻找
    // 直到找到前一个比它小的元素时，前面的元素不用往后挪了，待插入的元素就放在这个位置 j 上
    // 如果找不到，说明这个元素和前面的元素作比较是最小值，直接放到第一个位置，此时 j = 0
    while (j > 0 && arr[j - 1] > cur) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = cur;
  }
  return arr;
}

小结#

插入排序的平均时间复杂度：O(N^2)，在实际生产环境中不推荐使用。

希尔排序#

算法步骤#

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1。
按增量序列个数 k，对序列进行 k 趟排序。
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

代码演示#

function shellSort(arr) {
  let len = arr.length;
  let temp;
  let gap = 1;
 
  while (gap < len / 3) {
    // 动态定义间隔序列
    gap = gap * 3 + 1;
  }
 
  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
    for (let i = gap; i < len; i++) {
      temp = arr[i];
      let j;
      for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = temp;
    }
  }
  return arr;
}

小结#

希尔排序的平时时间复杂度为O(NlogN)，比其它三种基础排序算法效率要好，但是比起高级排序的归并排序和快排要稍微差点。