js 快速排序 All In One

快速排序 / Quick Sort

"use strict";

/**

 *

 * @author xgqfrms

 * @license MIT

 * @copyright xgqfrms

 * @created 2020-08-01

 * @modified

 *

 * @description 快速排序 quicksort

 * @difficulty Medium

 * @complexity O(n*log(n))

 * @augments

 * @example

 * @link https://github.com/xgqfrms/leetcode/issues/7#issuecomment-669991209

 * @solutions

 *

 */

const log = console.log;

function quickSort(arr) {

  if (arr.length <= 1) {

    return arr;

  }

  // 中间index

  var pivotIndex = Math.floor(arr.length / 2);

  // 中间值，参考值

  var pivot = arr.splice(pivotIndex, 1)[0];

  var left = [];

  var right = [];

  for (var i = 0; i < arr.length; i++) {

    if (arr[i] < pivot) {

      left.push(arr[i]);

    } else {

      right.push(arr[i]);

    }

  }

  // 递归

  return quickSort(left).concat([pivot], quickSort(right));

};

const arr = [12, 7, 5, 23, 18, 37, 1, 9, 17];

const test = quickSort(arr);

log(`arr =\n`, arr)

log(`test =\n`, test)

/*

arr =

 [

  12, 7, 5, 23,

  37, 1, 9, 17

]

test =

 [

   1,  5,  7,  9, 12,

  17, 18, 23, 37

]

*/

/**

 *

 * @author xgqfrms

 * @license MIT

 * @copyright xgqfrms

 * @created 2020-10-01

 * @modified

 *

 * @description 快速排序 quicksort

 * @difficulty Medium

 * @complexity O(n*log(n))

 * @augments

 * @example

 * @link https://www.cnblogs.com/xgqfrms/p/13857663.html

 * @solutions

 *

 */

const log = console.log;

function quickSort(arr) {

  if (arr.length <= 1) {

    return arr;

  }

  // 中间 index

  let pivotIndex = Math.floor(arr.length / 2);

  // 截取中间值， splice 改变原数组长度,   slice 不改变原数组长度

  const pivot = arr.splice(pivotIndex, 1)[0];

  const left = [];

  const right = [];

  for (let i = 0; i < arr.length; i++) {

    if (arr[i] < pivot) {

      left.push(arr[i]);

    } else {

      right.push(arr[i]);

    }

  }

  // 递归

  return quickSort(left).concat([pivot], quickSort(right));

};

const arr = [12, 7, 5, 23, 18, 37, 1, 9, 17];

const test = quickSort(arr);

log(`arr =\n`, arr)

log(`test =\n`, test)

refs

https://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html

https://github.com/xgqfrms/leetcode/issues/7#issuecomment-669991209

---

---

xgqfrms 2012-2020

www.cnblogs.com 发布文章使用：只允许注册用户才可以访问！

---