红豆稀饭
0%

leetcode-快速排序

发表于 更新于 阅读次数： Valine：

概述

数组的排序一直是个比较常用且基础的算法问题，虽然各个语言框架类库都会有内置的排序方法API调用，但是明白其中的原理对我们的编程思维有很大的好处。排序方法有很多种，其中最广为人知的就是快速排序算法，接下来我们手动实现一个快速排序。

原理

快速排序的主要思想是通过划分将待排序的数据分成前后两个部分，第一部分的数据总是比第二部分小，然后再递归调用函数将两个部分继续划分排序，最终所有数据达到有序状态。

首先定义两个指针l、r，分别代表左右指针，函数randomSort(nums, l, r)对nums数组里[l,r]进行排序，每次调用randomPartition对nums数组里面[l,r]部分进行划分，并返回分界的下标position，然后重复上述步骤调用randomSort(nums, l, position - 1)和randomPartition(nums, position + 1, r)。

核心是randomPartition划分函数的实现，划分函数开始需要一个分界值（主元pivot）,然后进行划分。主元的选取有很多种方式，我们采用随机数的方式，对当前划分区间[l, r]里的数等概率随机一个作为我们的主元，再将主元放到区间末尾，进行划分

步骤

实现步骤大概如下:

  • 实现swap函数
  • 实现partition函数
  • 实现 randomPartition函数
  • 实现 randomSort函数
  • 实现主函数sort，并递归调用randomSort

代码实现

实现swap函数

1
2
3
4
5
const swap = (nums, i, j) => {
  const temp = nums[i]
  nums[i] = nums[j]
  nums[j] = temp
}

实现partition函数

1
2
3
4
5
6
7
8
9
10
11
12
const partition = (nums, l, r) => {
  const pivot = nums[r]
  let i = l - 1
  for(let j = l; j <= r - 1; j ++) {
    if(nums[j] <= pivot) {
      i += 1
      swap(nums, i, j)
    }
  }
  swap(nums, i + 1, r)
  return i + 1
}

实现randomPartition函数

1
2
3
4
5
6
const randomPartition = (nums, l, r) => {
  // 随机一个作为我们的主元pivot
  const i = Math.floor(Math.random() * (r - l + 1)) + l
  swap(nums, r, i)
  return partition(nums, l, r)
}

实现randomSort函数

1
2
3
4
5
6
7
const randomSort = (nums, l, r) => {
  if(l < r) {
    const position = randomPartition(nums, l, r)
    randomSort(nums, l, position - 1)
    randomSort(nums, position + 1, r)
  }
}

实现sort函数

1
2
3
4
const sort = (nums) => {
  randomSort(nums, 0, nums.length - 1)
  return nums
}

最终代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
const swap = (nums, i, j) => {
  const temp = nums[i]
  nums[i] = nums[j]
  nums[j] = temp
}

const partition = (nums, l, r) => {
  const pivot = nums[r]
  let i = l - 1
  for(let j = l; j <= r - 1; j ++) {
    if(nums[j] <= pivot) {
      i += 1
      swap(nums, i, j)
    }
  }
  swap(nums, i + 1, r)
  return i + 1
}

const randomPartition = (nums, l, r) => {
  // 随机一个作为我们的主元pivot
  const i = Math.floor(Math.random() * (r - l + 1)) + l
  swap(nums, r, i)
  return partition(nums, l, r)
}

const randomSort = (nums, l, r) => {
  if(l < r) {
    const position = randomPartition(nums, l, r)
    randomSort(nums, l, position - 1)
    randomSort(nums, position + 1, r)
  }
}

const sortArray = (nums) => {
  randomSort(nums, 0, nums.length - 1)
  return nums
}