myDocs

排序（冒泡排序、插入排序、选择排序、归并排序、快排）

来源：https://yuchengkai.cn/docs/cs/algorithm.html#排序

各类排序	平均时间复杂度	最好情况	最坏情况	空间复杂度
冒泡排序	O(n²)	O(n)	O(n²)	O(1)
选择排序	O(n²)	O(n²)	O(n²)	O(1)
插入排序	O(n²)	O(n)	O(n²)	O(1)
布尔排序	O(nlogn)	O(nlog²n)	O(nlog²n)	O(1)
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)
快速排序	O(nlogn)	O(nlogn)	O(n²)	O(logn)

1、冒泡排序

原理：从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一个元素，那么此时最后一个元素就是该数组中最大的数。下一轮重复以上操作，但是此时最后一个元素也就是最大数了，所以不需要再比较最后一个元素，只需要比较到length-1的位置。

//冒泡排序 复杂度: O(n * n)

function bubble(array) {
    checkArray(array);
    for (let i = array.length - 1; i > 0; i--) {
      // 从 0 到 `length - 1` 遍历
      for (let j = 0; j < i; j++) {
        if (array[j] > array[j + 1]) 
        swap(array, j, j + 1);
      }
    }
    return array;
}

function checkArray(array) {
    if (!array || array.length <= 2) return;
}

function swap(array, left, right) {
    let temp = array[right];
    array[right] = array[left];
    array[left] = temp;
}

2、插入排序

原理：第一个元素默认是已排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。

//插入排序 复杂度: O(n * n)

function insertion(array) {
    checkArray(array);
    for (let i = 1; i < array.length; i++) {
      for (let j = i - 1; j >= 0 && array[j] > array[j + 1]; j--)
        swap(array, j, j + 1);
    }
    return array;
}

function checkArray(array) {
    if (!array || array.length <= 2) return;
}

function swap(array, left, right) {
    let temp = array[right];
    array[right] = array[left];
    array[left] = temp;
}

3、选择排序

原理：遍历数组，设置最小值的索引为0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引1开始重复上述操作。

//选择排序 复杂度: O(n * n)

function selection(array) {
    checkArray(array);
    for (let i = 0; i < array.length - 1; i++) {
      let minIndex = i;
      for (let j = i + 1; j < array.length; j++) {
        minIndex = array[j] < array[minIndex] ? j : minIndex;
      }
      swap(array, i, minIndex);
    }
    return array;
}

function checkArray(array) {
    if (!array || array.length <= 2) return;
}

function swap(array, left, right) {
    let temp = array[right];
    array[right] = array[left];
    array[left] = temp;
}

原理：递归的将数组两两分开直到最多包含两个元素，然后将数组排序合并，最终合并为排序好的数组。假设我有一组数组[3,1,2,8,9,7,6]，中间数索引是3，先排序数组[3,1,2,8]。在这个左边数组上，继续拆分直到变成数组包含两个元素（如果数组长度是奇数的话，会有一个拆分数组只包含一个元素）。然后排序数组[3,1]和[2,8]，然后再[1,3,2,8]，这样左边数组就排序完成，然后按照以上思路排序右边数组，最后将数组 [1,2,3,8]和[6,7,9]排序。

//归并排序 复杂度： O(N * logN)

function sort(array) {
    checkArray(array);
    mergeSort(array, 0, array.length - 1);
    return array;
}
  
function mergeSort(array, left, right) {
    // 左右索引相同说明已经只有一个数
    if (left === right) return;
    // 等同于 `left + (right - left) / 2`
    // 相比 `(left + right) / 2` 来说更加安全，不会溢出
    // 使用位运算是因为位运算比四则运算快
    let mid = parseInt(left + ((right - left) >> 1));
    mergeSort(array, left, mid);
    mergeSort(array, mid + 1, right);
  
    let help = [];
    let i = 0;
    let p1 = left;
    let p2 = mid + 1;
    while (p1 <= mid && p2 <= right) {
      help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
    }
    while (p1 <= mid) {
      help[i++] = array[p1++];
    }
    while (p2 <= right) {
      help[i++] = array[p2++];
    }
    for (let i = 0; i < help.length; i++) {
      array[left + i] = help[i];
    }
    return array;
}

function checkArray(array) {
    if (!array || array.length <= 2) return;
}

5、快排

原理：随机选取一个数组中的值作为基准值，从左至右取值与基准值对比大小。比基准值小的放数组左边，大的放右边，对比完成后将基准值和第一个比基准值大的值交换位置。然后将数组以基准值的位置分为两部分，继续递归以上操作。

//快速排序 复杂度： O(N * logN)

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var s = Math.floor(arr.length / 2);
  var temp = arr.splice(s, 1);
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < temp) {
      left.push(arr[i]);
    }
    if (arr[i] >= temp) {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(temp, quickSort(right));
}

排序（冒泡排序、插入排序、选择排序、归并排序、快排）

1、冒泡排序

2、插入排序

3、选择排序

4、归并排序

5、快排