JavaScript之排序算法篇（上）

前言

排序算法是《数据结构和算法》中比较基础的算法

常见的排序算法有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序

算法总览

冒泡排序

算法步骤

1. 从头开始，比较相邻的两个数，如果第一个数大于第二个数，就交换他们两个的位置
2. 然后从交换的位置开始，继续执行第1步的比较策略
3. 经过一轮循环之后，最大的数就会被放到最后
4. 重复上面的步骤，知道没有任何一对数字需要比较

动图演示

代码实现

// 冒泡排序
function bubbleSort(arr) {
    var len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                var temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

选择排序

算法步骤

1. 在未排序的序列中找到最小元素，放到排序序列的起始位置
2. 从剩下未排序的元素中继续寻找最小的元素，放到已排序序列的末尾
3. 重复第2步骤，到所有元素排列完毕

动图演示

代码实现

// 选择排序
function selectionSort(arr) {
  let len = arr.length;
  let minIndex;
  for (let i = 0; i < len - 1; i++) {
    minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    let temp = arr[j];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

插入排序

算法步骤

1. 将第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置，相等的话就排到相等元素的后面

动画演示

代码实现

// 插入排序
function insertionSort(arr) {
    let len = arr.length;
    let preIndex, current;
    for (let i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

希尔排序

算法步骤

1. 按照希尔排序的初稿，先设置增量gap为 len / 2，并进行分组排序
2. 设置增量gap为原来的一半，继续对分组进行排序
3. 重复以上的步骤，知道gap值为1

动画演示

代码实现

// 希尔排序
function shellSort(arr) {
    let len = arr.length;
    let gap = Math.floor(len / 2);
    while (gap > 0) {
        for (let i = gap; i < len; i++) {
            let j = i;
            let temp = arr[i];
            while (j > gap - 1 && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j = j - gap;
            }
            arr[j] = temp;
        }
        gap = Math.floor(gap / 2);
    }
    return arr;
}