【排序算法】归并排序和快速排序

[slogeor]

[slogeor]

归并排序

/**
 * @description 归并排序，分解操作
 * @param {Array} arr 原始数组
 */
function mergeSort(arr = []) {
  // 边界条件
  if (arr.length < 2) return arr;

  var len = arr.length;
  var mid = Math.floor(len / 2);
  // 归并排序借助递归，先写递归代码
  var arr1 = arr.slice(0, mid);
  var arr2 = arr.slice(mid, len);
  return merge(mergeSort(arr1), mergeSort(arr2));
}

/**
 * @description 归并排序，合并操作
 * @param {Array} a1 有效的子数组
 * @param {Array} a2 有效的子数组
 * @returns {Array} result 排序后数组
 */
function merge(a1 = [], a2 = []) {
  console.log('---merge---')
  var result = [];
  var a1Len = a1.length;
  var a2Len = a2.length;
  // 指向 a1
  var i1 = 0;
  // 指向 a2
  var i2 = 0;

  while (i1 < a1Len && i2 < a2Len) {
    if (a1[i1] > a2[i2]) {
      result.push(a2[i2]);
      i2++;
    } else {
      result.push(a1[i1]);
      i1++;
    }
  }

  while (i1 < a1Len) {
    result.push(a1[i1]);
    i1++;
  }

  while (i2 < a2Len) {
    result.push(a2[i2]);
    i2++;
  }
  return result;
}

mergeSort([11, 8, 3, 9, 7, 1, 2, 5]);
// 1, 2, 3, 5, 7, 8, 9, 11
// 输出 7 次 merge

mergeSort([ 1, 2, 3, 5, 7, 8, 9, 11 ]);
// 1, 2, 3, 5, 7, 8, 9, 11
// 输出 7 次 merge

时间复杂度分析

最好时间复杂度：O(nlong)
最坏时间复杂度：O(nlong)
最坏时间复杂度：O(nlong)

空间复杂度分析

O(n)，合并操作，需要申请数组存放数据

稳定性分析

稳定排序算法

归并排序操作示意图

图片引用：极客时间-数据结构与算法之美

[slogeor]

快速排序

/**
 * @description 快速排序算法: 空间复杂度 O(1)
 * @param {Array} arr
 * @returns {Array} arr
 */
function quickSort(arr = []) {
  // 边界条件
  if (arr.length < 2) return arr;
  var len = arr.length;

  // 分区点
  var pivot = len - 1;

  var i = 0;
  var j = 0;
  for (; j < len; j++) {
    if (arr[j] < arr[pivot]) {
      // 数据交换
      if (i !== j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
      i++
    }
  }
  return quickSort(arr.slice(0, i)).concat(arr[pivot]).concat(quickSort(arr.slice(i, len - 1)));
}
quickSort([1, 11, 3, 16, 7, 12, 5, 14, 9, 10])

时间复杂度分析

最好时间复杂度：O(nlong)
最坏时间复杂度：O(n^2)
最坏时间复杂度：O(nlong)

空间复杂度分析

O(1)

稳定性分析

不稳定排序算法

快速排序操作示意图

图片引用：极客时间-数据结构与算法之美

[slogeor]

提供一般不考虑空间占用的快速排序算法

/**
 * @description 快速排序算法
 * @param {Array} arr
 * @returns {Array} arr
 */
function quickSort(arr = []) {
  console.log('quickSort');
  // 边界条件考虑
  if (arr.length < 2) return arr;
  var len = arr.length;

  // 一般取数组最后一个节点作为分区点
  var pivot = len - 1;

  var arr1 = [];
  var arr2 = [];
  for (var k = 0; k < len - 1; k++) {
    if (arr[k] < arr[pivot]) {
      arr1.push(arr[k]);
    } else {
      arr2.push(arr[k]);
    }
  }

  return quickSort(arr1).concat(arr[pivot]).concat(quickSort(arr2));
}

quickSort([1, 11, 3, 16, 7, 12, 5, 14, 9, 10])