排序算法

date
Feb 3, 2022
slug
sort
status
Published
tags
算法
summary
了解各种算法。
type
Post
  • 冒泡排序: 双层 for 循环实现 相邻元素对比
  • 选择排序: 每次循环 找到最小值 进行赋值
  • 插入排序: 使用 额外索引 进行位置插入
  • 希尔排序: 递减 → 分组 → 插入排序
  • 快速排序:前后冒泡 → 基准 → 划分 → 循环
  • 归并排序:分治法 → 占用额外空间O(n)
  • 计数排序:要求输入的数据必须是 确定范围的整数
// 冒泡排序: 双层 for 循环实现响铃元素对比
function bubbleSort(list) {
  const length = list.length
  for (let k = 0; k < length; k++) {
    /**
     * 当 k 循环一次就代表最大的元素已经在最后面了,
     * 所以就没有必要再去访问最后一个元素
     */
    for (let j = 0; j < length - k; j++) {
      // 相邻元素比较, 如顺序错误则调换
      if (list[j] > list[j + 1]) {
        let temp = list[j]
        list[j] = list[j + 1]
        list[j + 1] = temp
      }
    }
  }
  return list
}

// 选择排序: 每次循环找到最小值进行赋值
function selectionSort(list) {
  const length = list.length
  let minIndex, temp
  for (let i = 0; i < length; i++) {
    /**
     * 外层循环的每一项与内层循环每一项对比,
     * 找出内层循环中最小于外层项的值
     * 找到后赋值最小项索引, 内层循环结束后调换顺序
     */
    minIndex = i
    for (let j = i + 1; j < length; j++) {
      if (list[j] < list[minIndex]) {
        minIndex = j
      }
    }
    temp = list[minIndex]
    list[minIndex] = list[i]
    list[i] = temp
  }
  return list
}



// 插入排序: 使用额外索引进行位置插入
function insertionSort(list) {
  for (let index = 0; index < list.length; index++) {
    /**
     * 核心: 操作 preIndex 来决定插入的位置, 以及插入的值
     * 上一个如果大于当前则交换位置,
     * 并对 preIndex--, 当减到 -1 或 当前索引的值小于当前值时, 则用当前索引值赋值
     * 赋值时是根据当前移动的索引 +-1 控制的, 当前 for 循环的索引是要插入时的值
     */
    // 当前值一定要缓存下来, 因为当 while 操作时 list 项的顺序会发生变化, 真正赋值时则会出问题
    const current = list[index];
    let preIndex = index - 1
    while (preIndex >= 0 && list[preIndex] > current) {
      list[preIndex + 1] = list[preIndex]
      preIndex--
    }
    list[preIndex + 1] = current
  }
  return list
}

// 希尔排序 -> 递减分组插入对比
function shellSort(arr) {
  const len = arr.length;
  let temp, gap = len, isStop = false;
  // 当间隔小于 0 时条件不成立
  while (gap > 0 && !isStop) {
    value = Math.floor(gap/3)
		// 为了保证能最后用 1 间隔进行收尾排序
    if (value === 1 || value === 0) {
      isStop = true
      gap = 1
    } else {
      gap = value
    }
    // 循环整个数组, 但按照动态间隔数作为起始循环
    for (let i = gap; i < len; i++) {
      // 暂存间隔起始的每一项
        temp = arr[i];
        // 获取对比索引 = 累加间隔 - 固定间隔
        let j = i - gap;
        // 当对比索引 >= 0 时且 当前对比索引值 > 累加索引值时
        while (j >= 0 && arr[j] > temp) {
          // 当前对比索引与累加索引互换
          // 不要写成 arr[i] = arr[j],
          // 因为 i 是固定的, 而真正要变化的数据是需要下一次要替换或者比较的值,
          // 这样才可以有效的实现递归的向后对比
          arr[j+gap] = arr[j];
          // 当前对比索引 - 固定间隔 = 下一次要对比对比索引
          // 如果下一次的索引 < 0, 或者下一次对比的索引值小于累加索引值时
          // 则结束此次 while 循环
          j -= gap
        }
        // j + gap 的索引 = 有走 while 循环 ? i : 对比后的插入索引
        arr[j + gap] = temp;
    }
  }
  return arr;
}

// 快速排序:从数列调出一位为基准,再从基准的即基础上分为左右进行递归

function quickSort(list, low, high) {
  // 当 low >= high 时意味着, 对比区域内排序已完毕, 则终止
  if (low < high) {
    // 找到选定排序后索引
    const pivot = partition(list, low, high)
    // 以选定索引为划分俩个小大区域
    quickSort(list, low, pivot - 1)
    quickSort(list, pivot + 1, high)
  }
  return list
}

function partition(list, low, high) {
  // 默认从 low 下标开始
  const pivot = list[low]
  while (low < high) {
    // 先从后面往前匹配, 如果当前对比值有比后面的数值大则互换, 无则找到低为止
    while (low < high && pivot < list[high]) {
      --high
    }
    list[low] = list[high]
    // 反之亦然
    while (low < high && pivot > list[low]) {
      ++low
    }
    list[high] = list[low]
  }
  // 当 low < high 时也就意味着 low 和 high 相同了
  list[high] = pivot
  return high
}

// 归并排序
function mergeSort(arr) {
  var len = arr.length;
  if(len < 2) {
      return arr;
  }
  var middle = Math.floor(len / 2),
      left = arr.slice(0, middle),
      right = arr.slice(middle);
	// 妙啊~, 不停的递归,最终会得到俩个有序的值,在对有序的值进行 merge 便是有序的数组
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
  var 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;
}
 
 

© jianxiaoBai 2021 - 2022