冒泡排序

基本思想

依次比较相邻的两个数，如果不符合排序规则，则调换两个数的位置。这样一遍下来，能够保证最大（或最小）的数排在最后一位。
再对最后一个以外的数组，重复前面的过程，直到全部排序完。

由于每进行一次这个过程，在该次比较的最后一个位置上，正确的数会自己冒出来，就像是冒泡一样，故名冒泡算法。

function bubbleSort(arr) {
  var len = arr.length
  var i, j, stop, temp
    // 外层循环控制总的循环次数
  for (i = 0; i < len - 1; i++) {
    // 内层循环进行两两比较
    for (j = 0; (stop = len - 1 - i), j < stop; j++) {
      // 比较大小
      if (arr[j] > arr[j + 1]) {
        temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

选择排序

选择排序（Selection Sort）与冒泡排序类似，也是依此对相邻的数进行两两比较。不同在于，它不是每比较一次就调换位置，而是一轮比较完毕，找到最大值（或最小值）之后，将其放在正确的位置，其他数的位置不变。

function selectionSort(arr) {
  var len = arr.length
  var i, j, min, temp
    // 外层循环控制总的循环次数
  for (i = 0; i < len; i++) {
    // 认为当前的值为最小
    min = i
    // 内层循环与 min 比较
    for (j = i + 1; j < len; j++) {
      // 大小比较
      if (arr[min] > arr[j]) {
        min = j
      }
    }
    // 最后再判断一下
    if (i !== min) {
      temp = arr[i]
      arr[i] = arr[min]
      arr[min] = temp
    }
  }
  return arr
}

插入排序

插入排序（Insertion sort）比前面两种排序方法都更有效率。它将数组分成”已排序”和”未排序”两部分，一开始的时候，”已排序”的部分只有一个元素，然后将它后面一个元素从”未排序”部分插入”已排序”部分，从而”已排序”部分增加一个元素，”未排序”部分减少一个元素。以此类推，完成全部排序。

function insertionSort(arr) {
  var len = arr.length
  var value, i, j
  for (i = 0; i < len; i++) {
    // 记录未排序的第一位
    value = arr[i]
    // 依次和已排序的的每一位进行比较
    for (j = i - 1; j > -1 && arr[j] > value; j--) {
      arr[j + 1] = arr[j]
    }
    arr[j + 1] = value
  }
  return arr
}

合并排序

它的思想是，将两个已排序的数组合并，要比从头开始排序所有元素来得快，因此，可以将数组拆开，分成 n 个只有一个元素的数组，然后不断地两两合并，直到全部排序完成。

以数组 [3, 2, 4, 5, 1] 为例，进行从小到大排序。

将数组分成 [3, 2, 4] 和 [5, 1]两部分。
将 [3, 2, 4] 分成 [3, 2] 和 [4] 两部分。
将 [3, 2] 分成 [3] 和 [2] 两部分，然后合并成 [2, 3]。
将 [2, 3] 和 [4] 合并成 [2, 3, 4]。
将 [5, 1] 分成 [5] 和 [1] 两部分，然后合并成 [1, 5]。
将 [2, 3, 4] 和 [1, 5] 合并成 [1, 2, ,3, 4, 5]。

实现 merge 函数

function merge(left, right) {
    let result = [],
        il = 0,
        ir = 0;
    while (il < left.length && ir < right.length) {
        if (left[il] < right[ir]) {
            result.push(left[il++]);
        } else {
            result.push(right[ir++]);
        }
    }
    return result.concat(left.slice(il)).concat(right.slice(ir));
}

这个函数用于将两个已升序的数组合并成一个新数组，原理很简单将两个数组中最小的部分放到 result 中，直到有一个数组遍历完，最后返回合并的新数组。

实现 mergeSort 函数

function mergeSort(myArray) {
    if (myArray.length < 2) return myArray;
    let middle = Math.floor(myArray.length / 2),
        left = myArray.slice(0, middle),
        right = myArray.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

快速排序

公认最快的排序算法之一，基本思想很简单：先确认一个“支点”（pivot），将所有小于“支点”的值都放在该点的左侧，大于“支点”的值都放在该点的右侧，然后对左右两侧不断重复这个过程，直到所有排序完成。

确定“支点”（pivot）。虽然数组中任意一个值都能作为“支点”，但通常是取数组的中间值。
建立两端的指针。左侧的指针指向数组的第一个元素，右侧的指针指向数组的最后一个元素。
左侧指针的当前值与“支点”进行比较，如果小于“支点”则指针向后移动一位，否则指针停在原地。
右侧指针的当前值与“支点”进行比较，如果大于“支点”则指针向前移动一位，否则指针停在原地。
左侧指针的位置与右侧指针的位置进行比较，如果前者大于等于后者，则本次排序结束；否则，左侧指针的值与右侧指针的值相交换。
对左右两侧重复第 2 至 5 步。

以对数组 [3, 2, 4, 5, 1] 进行从小到大排序为例。

选择中间值“4”作为“支点”。
第一个元素3小于4，左侧指针向后移动一位；第二个元素2小于4，左侧指针向后移动一位；第三个元素4等于4，左侧指针停在这个位置（数组的第2位）。
倒数第一个元素1小于4，右侧指针停在这个位置（数组的第4位）。
左侧指针的位置（2）小于右侧指针的位置（4），两个位置的值互换，数组变成[3, 2, 1, 5, 4]。
左侧指针向后移动一位，第四个元素5大于4，左侧指针停在这个位置（数组的第3位）。
右侧指针向前移动一位，第四个元素5大于4，右侧指针移动向前移动一位，第三个元素1小于4，右侧指针停在这个位置（数组的第3位）。
左侧指针的位置（3）大于右侧指针的位置（2），本次排序结束。
对 [3, 2, 1]和[5, 4]两部分各自不断重复上述步骤，直到排序完成。

实现 swap 函数

function swap(myArray, firstIndex, secondIndex) {
    const temp = myArray[firstIndex];
    myArray[firstIndex] = myArray[secondIndex];
    myArray[secondIndex] = temp;
}

实现 partition 函数，用于完成一轮排序

function partition(myArray, left, right) {
    let pivot = myArray[Math.floor((right + left) / 2)],
        i = left,
        j = right;
    while (i <= j) {
        while (myArray[i] < pivot) {
            i++;
        }
        while (myArray[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(myArray, i, j);
            i++;
            j--;
        }
    }
    return i;
}

实现 quicSort 函数

function quickSort(myArray, left, right) {
    if (myArray.length < 2) return myArray;
    left = (typeof left !== "number" ? 0 : left);
    right = (typeof right !== "number" ? myArray.length - 1 : right);
    let index = partition(myArray, left, right);
    if (left < index - 1) {
        quickSort(myArray, left, index - 1);
    }
    if (index < right) {
        quickSort(myArray, index, right);
    }
    return myArray;
}

参考：

[1] 排序算法

Programing learning note

javascript 实现五种排序算法

冒泡排序

选择排序

插入排序

合并排序

快速排序