8 种排序算法的代码实现

找工作之际，重新学习了常见的排序算法，像看似无害的冒泡排序其实也有很多种优化方案，还有简单粗暴的选择排序，模拟抓牌的插入排序，弥补插入排序缺陷的希尔排序，使用了分治思想的归并排序，有点难搞的快速排序，模拟树状结构的堆排序，以及不按套路出牌的基数排序等。

冒泡排序

常规冒泡排序

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

二次优化后的冒泡排序

function bubbleSort2(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) return;
  let lastIndex = arr.length - 1;
  for (let i = 0; i < arr.length - 1; i++) {
    //一、外圈优化标志位，有交换则更改为false
    let flag = true;
    //二、内圈优化，对于已经有序的跳过比较
    let pos = lastIndex;
    for (let j = 0; j < pos; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        flag = false;
        //记录最后一个交换的位置，其后已经有序
        lastIndex = j;
      }
    }
    //循环后仍然为true，说明上一圈已经有序
    if (flag) break;
  }
  return arr;
}

三次优化后的冒泡排序，减少 flag 标志位

function bubbleSort3(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) return;
  let i = arr.length - 1;
  while (i > 0) {
    //初始值为0，当没有交换时，直接结束外圈循环
    let lastIndex = 0;
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        //记录最后一个交换的位置，其后已经有序
        lastIndex = j;
      }
    }
    //对于已经有序的，可以减少外圈循环次数
    i = lastIndex;
  }
  return arr;
}

关于冒泡排序的总结，如果最小的数在数组的最后，那么优化与不优化效率一样

选择排序

function selectSort(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) return;
  for (let i = 0; i < arr.length - 1; i++) {
    let minPos = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minPos]) {
        minPos = j;
      }
    }
    [arr[i], arr[minPos]] = [arr[minPos], arr[i]];
  }
  return arr;
}

插入排序

常规插入排序

function insertSort(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) return;
  for (let i = 1; i < arr.length; i++) {
    let j = i;
    let temp = arr[i];
    while (j && arr[j - 1] > temp) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = temp;
  }
  return arr;
}

二分查找优化的插入排序

function binarySearch(arr, max, value) {
  let min = 0;
  //在min大于max返回的min必是大于value的下标
  while (min <= max) {
    let mid = Math.floor((min + max) / 2);
    //此处的等于是保证插入排序的稳定性
    if (arr[mid] <= value) {
      min = mid + 1;
    } else {
      max = mid - 1;
    }
  }
  return min;
}
function insertSort(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) return;
  for (let i = 1; i < arr.length; i++) {
    let j = i;
    let temp = arr[i];
    let pos = binarySearch(arr, i - 1, arr[i]);
    //下标及之后数组中的值，都要向后移动一位
    while (j > pos) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = temp;
  }
  return arr;
}

希尔排序

function hillSort(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) return;
  for (
    let gap = Math.floor(arr.length / 2);
    gap >= 1;
    gap = Math.floor(gap / 2)
  ) {
    for (let i = gap; i < arr.length; i++) {
      let j = i;
      let temp = arr[i];
      while (j - gap >= 0 && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
  }
  return arr;
}

希尔排序解决了，最小的数在后面需要进行 length-1 次比较 e 情况

归并排序

function mergeSort(arr) {
  let length = arr.length;
  if (!Array.isArray(arr) || length < 1) return;
  if (length == 1) return arr;
  let mid = length >> 1,
    leftArr = arr.slice(0, mid),
    rightArr = arr.slice(mid, length);
  return merge(mergeSort(leftArr), mergeSort(rightArr));
}

function merge(leftArr, rightArr) {
  let result = [],
    lPos = 0,
    rPos = 0;
  while (lPos < leftArr.length && rPos < rightArr.length) {
    if (leftArr[lPos] < rightArr[rPos]) {
      result.push(leftArr[lPos++]);
    } else {
      result.push(rightArr[rPos++]);
    }
  }
  while (lPos < leftArr.length) {
    result.push(leftArr[lPos++]);
  }
  while (rPos < rightArr.length) {
    result.push(rightArr[rPos++]);
  }
  return result;
}

快速排序

function quickSort(arr, start = 0, end = arr.length - 1) {
  if (start >= end) return arr;
  let pivot = partition(arr, start, end);
  quickSort(arr, start, pivot - 1);
  quickSort(arr, pivot + 1, end);
  return arr;
}
function partition(arr, start, end) {
  let temp = arr[start];
  while (start < end) {
    //注意，有等号
    while (arr[end] >= temp && start < end) {
      end--;
    }
    arr[start] = arr[end];
    //注意，没有等号
    while (arr[start] < temp && start < end) {
      start++;
    }
    arr[end] = arr[start];
  }
  arr[start] = temp;
  return start;
}

快速排序，[2, 1, 1, 3] 可证明不稳定性
排序学累了，看一段民族舞吧

堆排序

function heapSort(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) return;
  let size = arr.length;
  //构建大顶堆，从最后一个非叶子节点开始
  for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {
    heapify(arr, i, size);
  }
  for (let i = size - 1; i > 0; i--) {
    //把堆顶最大的节点与待排序节点中最后的节点交换
    [arr[0], arr[i]] = [arr[i], arr[0]];
    //重新调整为大顶堆，已排序的节点不参与比较，所以i代表的size减小
    heapify(arr, 0, i);
  }
  return arr;
}

function heapify(arr, index, size) {
  //larger存父节点与两个子节点中最大的下标，剩下的左右子节点下标
  let larger = index,
    leftPos = index * 2 + 1,
    rightPos = index * 2 + 2;
  if (leftPos < size && arr[leftPos] > arr[larger]) {
    larger = leftPos;
  }
  if (rightPos < size && arr[rightPos] > arr[larger]) {
    larger = rightPos;
  }
  if (index != larger) {
    [arr[index], arr[larger]] = [arr[larger], arr[index]];
    heapify(arr, larger, size);
  }
}

基数排序

function radixSort(array) {
  let length = array.length;
  // 如果不是数组或者数组长度小于等于1，直接返回，不需要排序
  if (!Array.isArray(array) || length <= 1) return;
  let bucket = [],
    max = array[0],
    loop;
  // 确定排序数组中的最大值
  for (let i = 1; i < length; i++) {
    if (array[i] > max) {
      max = array[i];
    }
  }
  // 确定最大值的位数
  loop = (max + "").length;
  // 初始化桶
  for (let i = 0; i < 10; i++) {
    bucket[i] = [];
  }
  for (let i = 0; i < loop; i++) {
    for (let j = 0; j < length; j++) {
      let str = array[j] + "";
      if (str.length >= i + 1) {
        let k = parseInt(str[str.length - 1 - i]); // 获取当前位的值，作为插入的索引
        bucket[k].push(array[j]);
      } else {
        // 处理位数不够的情况，高位默认为 0
        bucket[0].push(array[j]);
      }
    }
    array.splice(0, length); // 清空旧的数组
    // 使用桶重新初始化数组
    for (let i = 0; i < 10; i++) {
      let t = bucket[i].length;
      for (let j = 0; j < t; j++) {
        array.push(bucket[i][j]);
      }
    }
  }
  return array;
}

下次更新说明一下各种排序的时间复杂度，空间复杂度和稳定性，还有简单说一说什么场景使用哪种排序方式。

参考：
算法知识总结–CavsZhouyou/Front-End-Interview-Notebook
优雅的 JavaScript 排序算法（ES6）–RayJune/Elegant-JavaScript-Sorting-Algorithms