René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"快排模板","articleBody":"### 快速排序\r\n\r\n算法\r\n\r\n1. 选择基准（provit）\r\n2. 根据基准，将原数组拆分为left，right两个数组\r\n3. 分别对left，right做快排\r\n\r\n时间开销 `O(nlogn)`, 空间开销看选择基准的算法\r\n\r\n```javascript\r\n/**\r\n * 快速排序\r\n * @param {*} arr 待排数组\r\n * @param {*} left 排序区间左侧\r\n * @param {*} right 排序区间右测\r\n */\r\nfunction quickSort(arr, left, right) {\r\n  if (right - left \u003c 1) {\r\n    return\r\n  }\r\n  let provit = partition(arr, left, right);\r\n  quickSort(arr, left, provit, left)\r\n  quickSort(arr, provit + 1, right)\r\n}\r\n\r\n// 原地分割，空间O(1)\r\nfunction partition(arr, left, right) {\r\n  // 简单的挑选第一个数作为基准\r\n  let provit = left\r\n  let provitValue = arr[left]\r\n  swap(arr, right, provit) // 将基准放到最后\r\n  let curProvit = left\r\n  for (let i = left; i \u003c right; i++) {\r\n    if (arr[i] \u003c provitValue) { // 将数组根据provit分割\r\n      swap(arr, curProvit, i)\r\n      curProvit = curProvit + 1\r\n    }\r\n  }\r\n  swap(arr, curProvit, right)\r\n  return curProvit\r\n}\r\n\r\nfunction swap(arr, a, b) {\r\n  let term = arr[a]\r\n  arr[a] = arr[b]\r\n  arr[b] = term\r\n}\r\n```","author":{"url":"https://github.com/feikerwu","@type":"Person","name":"feikerwu"},"datePublished":"2020-02-27T06:41:19.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/3/algorithm-camp/issues/3"}