一些排序算法

记得有一个明星程序员说，做一个 web developer 是不用学习数学的。那么自然也不用学习算法了。作为一个前端，在实际工作中确实很少实现什么排序算法，因为在 JavaScript 的语言层面，就已经实现 sort 函数了。但是学习这些排序算法，依然有助于我们理解这些语言相关内置函数的原理。

人类从来不给自己设限，才是我们一直前进的动力。

冒泡排序

冒泡排序的基本思想很简单，通过两层循环，来逐渐交换相邻的位置，大的放在右边，小的放在左边，外层的第一次循环选出最大的数字，第二次选出第二大的数字，以此类推。代码如下：

function swap (sortArr, index1, index2) {
    var temp = sortArr[index1]
    sortArr[index1] = sortArr[index2]
    sortArr[index2] = temp
}

function arr2str (arr, delimiter) {
    return arr.join(delimiter)
}

var sortArr = [10, 8, 3, 2, 2, 4, 9, 5, 4, 3];

function bubbleSort (sortArr) {
    // 外层的迭代从元素最大索引值开始
    for (var outer = sortArr.length - 1; outer > 1; outer--) {
        for (var inner = 0; inner < outer; inner++) {// 
            if (sortArr[inner] > sortArr[inner + 1]) {
                swap(sortArr, inner, inner + 1)
            }
        }
        console.log(arr2str(sortArr, ' '))
    }
    return sortArr
}

console.group('冒泡排序')
console.log(sortArr.join(' '))
console.log(bubbleSort(sortArr.slice()).join(' '))
console.groupEnd()

2020-12-29 更新：

let count = 0;
let swapCount = 0;
// 这个是选择排序，只是数组位置交换的过于频繁了
function bubbleSort2(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      count++;
      if (arr[i] > arr[j]) {
        swapCount++;
        [arr[i], arr[j]] = [arr[j], arr[i]]; // 把最小的放在左边
      }
    }
  }

  return arr;
}
// 这个实现是正宗的冒泡排序，相邻的 2 个元素对比
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      count++;
      if (arr[j] > arr[j + 1]) {
        swapCount++;
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 把最小的放在左边
      }
    }
  }

  return arr;
}
// let arr = [10, 8, 3, 2, 2, 4, 9, 5, 4, 3];
let arr = [1, 3, 8, 2, 5, 9, 0, 4, 7, 6];
bubbleSort(arr);
console.log(arr, count, swapCount);

选择排序

选择排序的核心思想是从排序的元素中选择最小的元素，放在第一位；再从余下的元素中，选择最小的，再放到第二位，以此类推，直到排序成功。

核心代码如下：

function selectSort (arr) {
    var minIndex
    var temp
    
    for (var outer = 0; outer < arr.length - 1; outer++) {
        minIndex = outer // guess current is minest num
        for (var inner = outer + 1; inner < arr.length; inner++) {
            if (arr[inner] < arr[minIndex]) {
                minIndex = inner // save minest arrary item index to minIndex
            }
        }
        swap(arr, outer, minIndex)
        console.log(arr2str(arr))
    }
    return arr
}
console.group('选择排序')
console.log(selectSort(sortArr.slice()).join(' '))
console.groupEnd()

以下是 c++ 的实现：

// 泛型
template<typename T>
void selectionSort(T arr[], int n) {
    for (int i = 0; i < n; i++) {
        
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        swap(arr[i], arr[minIndex]);
    }
}

插入排序

插入排序的思想也非常简单，只是把这种思想转化为代码就要难一点。我们从一堆乱序的元素中选出一个放在已排序好元素中的合适位置，并将右侧的元素往右移动一个位置，我们具体看代码：

function insertSort (arr) {
    for (var outer = 1; outer < arr.length; outer++) {
        var temp = arr[outer] // save current iteration value
        var inner = outer
        while (inner > 0 && arr[inner - 1] > temp) {
            arr[inner] = arr[inner - 1]
            inner--
        }
        arr[inner] = temp // put the iteration in correct position
        console.log(arr2str(arr))
    }
    return arr
}
console.group('插入排序')
console.log(insertSort(sortArr).join(' '))
console.groupEnd()

短短几行代码，需要仔细看看。

下面我们来介绍一下希尔排序、归并排序和快速排序这几种高级排序算法。我清晰的记得一次电话面试中，tx 面试官让我说一下快速排序的核心思想。

希尔排序

在了解希尔排序之前，可以先看一下这个视频（需要翻墙）。希尔排序和插入排序的思想非常类似，只不过希尔排序定义了一个间隔位置，用来减少交换的次数。

希尔排序要解释清楚还是挺费劲的，如果看懂了上面的视频，那么理解起来也不难。核心代码如下。

function shellSort (arr) {
    var gaps = [5, 3, 1]

    for (var g = 0; g < gaps.length; g++) {
        for (var i = gaps[g]; i < arr.length; i++) {
            var temp = arr[i]
            // point code
            for (var j = i; j >= gaps[g] && arr[j - gaps[g]] > temp; j -= gaps[g]) {

                arr[j] = arr[j - gaps[g]] // point code

            }
            arr[j] = temp // point code
            console.log(arr2str(arr))
        }
    }
    return arr
}
console.group('希尔排序')
console.log(shellSort(sortArr).join(' '))
console.groupEnd()

对于初学者可能需要花一定的时间去理解上面的代码，可以再查查其它的相关文章。

归并排序

在理解归并排序前，我们还是先看一个视频。代码我就不贴出了，行数有点多。

2021-04-16 更新：递归版本的归并排序还是挺简单的，仔细琢磨琢磨。

var arr = [0, 4, 1, -3, 9, -3, 10];

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  let mid = (arr.length / 2) | 0;
  let left = arr.slice(0, mid);
  let right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let res = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      res.push(left.shift());
    } else {
      res.push(right.shift());
    }
  }
  res.push(...left, ...right);
  return res;
}

var res = mergeSort(arr);
console.log(res);

快速排序

在视频面前，文字显得不够直白，还是看视频吧。

function quickSort (arr) {
    if (!arr.length) return []
    var pivot = arr[0]
    var lessArr = []
    var bigArr = []

    for (var i = 1; i < arr.length; i++) {
        if (pivot >= arr[i]) {
            lessArr.push(arr[i])
        } else {
            bigArr.push(arr[i])
        }
    }

    // console.log(arr2str(arr))
    return quickSort(lessArr).concat(pivot, quickSort(bigArr))
}

console.group('快速排序')
console.log(quickSort(sortArr).join(' '))
console.groupEnd()

JavaScript 版本的快速排序实现如上，实现起来还是挺简洁的。

参考链接

https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/sort