René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"腾讯\u0026字节\u0026阿里：介绍一下快排原理以及时间复杂度，并实现一个快排","articleBody":"快排使用了分治策略的思想，所谓分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。\r\n\r\n快排的过程简单的说只有三步：\r\n\r\n- 首先从序列中选取一个数作为基准数\r\n- 将比这个数大的数全部放到它的右边，把小于或者等于它的数全部放到它的左边 （一次快排 `partition`）\r\n- 然后分别对基准的左右两边重复以上的操作，直到数组完全排序\r\n\r\n具体按以下步骤实现：\r\n\r\n- 1，创建两个指针分别指向数组的最左端以及最右端\r\n- 2，在数组中任意取出一个元素作为基准\r\n- 3，左指针开始向右移动，遇到比基准大的停止\r\n- 4，右指针开始向左移动，遇到比基准小的元素停止，交换左右指针所指向的元素\r\n- 5，重复3，4，直到左指针超过右指针，此时，比基准小的值就都会放在基准的左边，比基准大的值会出现在基准的右边\r\n- 6，然后分别对基准的左右两边重复以上的操作，直到数组完全排序\r\n\r\n注意这里的基准该如何选择喃？最简单的一种做法是每次都是选择最左边的元素作为基准：\r\n\r\n![](http://resource.muyiy.cn/image/20200627224355.gif)\r\n\r\n但这对几乎已经有序的序列来说，并不是最好的选择，它将会导致算法的最坏表现。还有一种做法，就是选择中间的数或通过 `Math.random()` 来随机选取一个数作为基准，下面的代码实现就是以随机数作为基准。\r\n\r\n**代码实现**\r\n\r\n```js\r\nlet quickSort = (arr) =\u003e {\r\n  quick(arr, 0 , arr.length - 1)\r\n}\r\n\r\nlet quick = (arr, left, right) =\u003e {\r\n  let index\r\n  if(left \u003c right) {\r\n    // 划分数组\r\n    index = partition(arr, left, right)\r\n    if(left \u003c index - 1) {\r\n      quick(arr, left, index - 1)\r\n    }\r\n    if(index \u003c right) {\r\n      quick(arr, index, right)\r\n    }\r\n  }\r\n}\r\n\r\n// 一次快排\r\nlet partition = (arr, left, right) =\u003e {\r\n  // 取中间项为基准\r\n  var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],\r\n      i = left,\r\n      j = right\r\n  // 开始调整\r\n  while(i \u003c= j) {\r\n    \r\n    // 左指针右移\r\n    while(arr[i] \u003c datum) {\r\n      i++\r\n    }\r\n    \r\n    // 右指针左移\r\n    while(arr[j] \u003e datum) {\r\n      j--\r\n    }\r\n    \r\n    // 交换\r\n    if(i \u003c= j) {\r\n      swap(arr, i, j)\r\n      i += 1\r\n      j -= 1\r\n    }\r\n  }\r\n  return i\r\n}\r\n\r\n// 交换\r\nlet swap = (arr, i , j) =\u003e {\r\n    let temp = arr[i]\r\n    arr[i] = arr[j]\r\n    arr[j] = temp\r\n}\r\n\r\n// 测试\r\nlet arr = [1, 3, 2, 5, 4]\r\nquickSort(arr)\r\nconsole.log(arr) // [1, 2, 3, 4, 5]\r\n// 第 2 个最大值\r\nconsole.log(arr[arr.length - 2])  // 4\r\n```\r\n\r\n快排是从小到大排序，所以第 `k` 个最大值在 `n-k` 位置上\r\n\r\n**复杂度分析**\r\n\r\n- 时间复杂度：O(nlogn)\r\n- 空间复杂度：O(nlogn)","author":{"url":"https://github.com/sisterAn","@type":"Person","name":"sisterAn"},"datePublished":"2020-06-23T15:44:10.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":7},"url":"https://github.com/70/JavaScript-Algorithms/issues/70"}