快速排序借用了分治的思想, 并且基于冒泡排序做了改进。 它将数组拆分为两个子数组, 其中一个子数组的所有元素都比另一个子数组的元素小, 然后对这两个子数组再重复进行上述操作, 直到数组不可拆分, 排序完成。
sortArray
:入口方法QuickSort
:递归方法,负责不停的划分,直到 p
q
指针对撞partition
: 划分函数,根据 pivot
划分区域,然后返回中点,中点右边的值均大于 pivot
,左边的值均小于 pivot
// 排序函数
function sortArray(arr){
return QuickSort(arr, 0, arr.length - 1)
}
// QuickSort
function QuickSort(arr, p, q){
// 此时排序已完成
if(p >= q) return arr
// 通过划分函数获得中点
let m = partition(arr, p, q)
// 接着视为两个区域进行递归
QuickSort(arr, p, m - 1)
QuickSort(arr, m + 1, q)
return arr
}
// 划分函数
function partition(arr, p, q){
// 重点是划分函数的实现
}
复制代码
按照基本思想进行
pivot
, 定义两个指针 i = p
, j = p + 1
j
指针找到 比 pivot
小的,移动 i
指针,将其与 i
换位j > q
之后跳出循环p
与 i
进行互换,返回 i
指针function partition(arr, p, q){
let pivot = arr[p]
let i = p
let j = p + 1
while(j <= q){
if(arr[j] < pivot){
i++
swap(arr, i, j)
}
j++
}
swap(arr, i, p)
return i
}
复制代码
arr = [15, 9, 31, 21, 44, 22, 33, 18, 2]
p = 0
q = arr.length - 1 = 8
pivot = arr[0]
i = 0
j = 1
开始比对9 < 15
i++; i = 1
swap(1, 1)
arr
不变31 > 15
, 21 > 15
, 44 > 15
, 22 > 15
, 33 > 15
, 18 > 15
(跳过)2 < 15
i++; i = 2
swap(2, 8)
[15, 9, 2, 21, 44, 22, 33, 18, 31]
i = 2, p = 0
swap(0, 2)
[2, 9, 15, 21, 44, 22, 33, 18, 31]
i = 2
, QuickSort(arr, 0, 1)
QuickSort(arr, 3, 8)
QuickSort(arr, 0, 1)
arr = [2, 9, 15, 21, 44, 22, 33, 18, 31]
p = 0
q = 1
i = 0
j = 2
swap(0, 0)
返回 i = 0
, QuickSort(arr, 0, -1)
(跳过) QuickSort(arr, 1, 1)
(跳过)QuickSort(arr, 3, 8)
=> partition(arr, 3, 8)
[..., 21, 44, 22, 33, 18, 31]
i = 3
j = 4
pivot = 21
44 > 21
, 22 > 21
, 33 > 21
(跳过)18 < 21
i = 4, j = 7
swap(4, 7)
[..., 21, 18, 22, 33, 44, 31]
31 > 21
(跳过),i = 4, p = 3
, swap(3, 4)
[..., 18, 21, 22, 33, 44, 31]
i = 4
QuickSort(arr, 3, 3)
(跳过)QuickSort(arr, 5, 8)
=> partition(arr, 5, 8)
[..., 22, 33, 44, 31]
i = 5, j = 6
pivot = 22
(跳过)i = 5
QuickSort(arr, 4, 4)
QuickSort(arr, 6, 8)
[..., 33, 44, 31]
i = 6, j = 7, pivot = 33
44 > 33
(跳过)31 < 33
i = 7, j = 8
swap(7, 8)
[..., 33, 31, 44]
i = 7, p = 6
swap(6, 7)
[..., 31, 33, 44]
i = 7
QuickSort(arr, 6, 6)
(跳过) QuickSort(arr, 8, 8)
(跳过)[2, 9, 15, 18, 21, 22, 31, 33, 44]
var partition = (arr, p, q) => {
// 取第一个数为基数
let pivot = arr[p]
// 从第二个数开始分区 (i, j) = (p + 1, q)
let i = p + 1
// 右边界
let j = q
// 相遇时退出循环
while (i < j){
// 找到第一个大于基数的位置
while (i < j && arr[i] <= pivot) i++
if(i != j){
// 交换到右分区,使得左边分区都小于或等于基数,右边分区大于或等于基数
swap(arr, i, j)
j--
}
}
// 如果两个指针相等,单独比较 arr[j] pivot
if(arr[j] > pivot) j--
// 将基数和中间树交换
swap(arr, p, j)
// 返回中间的下标
return j
}
复制代码
[31, 15, 18, 22, 33, 21, 44, 2, 9]
pivot = 31, i = 1, j = 8
15, 18, 22 < 31
(跳过)33 > 31
i = 4 j = 8
swap(4, 8)
[31, 15, 18, 22, 9, 21, 44, 2, 33]
j = 7
9, 21 < 31
(跳过)44 > 31
i = 6 j = 7
swap(6, 7)
[31, 15, 18, 22, 9, 21, 2, 44, 33]
j = 6
arr[6] = 2 < 31
swap(0, 6)
[2, 15, 18, 22, 9, 21, 31, 44, 33]
返回 j = 6
QuickSort(arr, 0, 5)
和 QuickSort(arr, 7, 8)
QuickSort(arr, 0, 5)
=> partition(arr, 0, 5)
[2, 15, 18, 22, 9, 21]
pivot = 2, i = 1, j = 5
15 > 2
swap(1, 5)
=> [2, 21, 18, 22, 9, 15]
j = 4
21 > 2
swap(1, 4)
=> [2, 9, 18, 22, 21, 15]
j = 3
9 > 2
swap(1, 3)
=> [2, 22, 18, 9, 21, 15]
j = 2
22 > 2
swap(1, 2)
=> [2, 18, 22, 9, 21, 15]
j = 1
arr[1] = 18 > 2
j--
swap(0, 0)
返回 j = 0
QuickSort(arr, 0, -1)
(跳过)和 QuickSort(arr, 1, 5)
QuickSort(arr, 1, 5)
=> partition(arr, 1, 5)
[18, 22, 9, 21, 15]
pivot = 18, i = 2, j = 5
22 > 18
swap(2, 5)
=> [18, 15, 9, 21, 22]
j = 4
15, 9 < 18
(跳过)21 > 18
此时 i = j = 4
arr[4] = 21 > 18
j--
swap(2, 3)
返回 j = 3
[9, 15, 18, 21, 22]
QuickSort(arr, 1, 2)
(跳过)和 QuickSort(arr, 4, 5)
(跳过)QuickSort(arr, 7, 8)
交换后完成排序 [2, 9, 15, 18, 21, 22, 31, 33, 44]
var partition = (arr, p, q) => {
// 取第一个数为基数
let pivot = arr[p]
// 从第二个数开始分区
let i = p + 1
// 右边界
let j = q
// 相遇时退出循环
while (i < j){
// 找到第一个大于基数的位置
while (i < j && arr[i] <= pivot) i++
// 找到第一个小于基数的位置
while (i < j && arr[j] >= pivot) j--
// 交换到右分区,使得左边分区都小于或等于基数,右边分区大于或等于基数
swap(arr, i, j)
}
// 如果两个指针相等,单独比较 arr[j] pivot
if(arr[j] > pivot) j--
// 将基数和中间树交换
swap(arr, p, j)
// 返回中间的下标
return j
}
复制代码
[22, 2, 18, 31, 33, 9, 15, 44, 21]
pivot = 22
i = 1, j = 8
2, 18 < 22
(跳过),31 > 22
i = 3
21 < 22
j = 8
swap(3, 8)
[22, 2, 18, 21, 33, 9, 15, 44, 31]
21 < 22
(跳过) 33 > 22
i = 4
31, 44 > 22
(跳过) 15 < 22
j = 6
swap(4, 6)
[22, 2, 18, 21, 15, 9, 33, 44, 31]
15, 9 < 22
跳过,i = 6
j = 6
跳出循环arr[6] = 33 > 22
j--
swap(0, 5)
[9, 2, 18, 21, 15, 22, 33, 44, 31]
返回 j = 5
QuickSort(arr, 0, 4)
和 QuickSort(arr, 6, 8)
QuickSort(arr, 0, 4)
=> partition(arr, 0, 4)
[9, 2, 18, 21, 15]
pivot = 9, i = 1, j = 4
2 < 9
(跳过) 18 > 9
i = 2
15, 21, 18 > 9
(跳过) j = 2
跳出循环arr[j] = 18 > 9
j--
swap(0, 1)
[2, 9, 18, 21, 15]
返回 j = 1
QuickSort(arr, 0, 0)
(跳过) 和 QuickSort(arr, 2, 4)
QuickSort(arr, 2, 4)
=> partition(arr, 2, 4)
[18, 21, 15]
pivot = 18, i = 3, j = 4
21 > 18
i = 3
15 < 18
j = 4
swap(3, 4)
[18, 15, 21]
j = 4
跳出循环arr[4] = 21 > 18
j--
swap(2, 3)
[15, 18, 21]
返回 j = 3
QuickSort(arr, 2, 2)
(跳过) 和 QuickSort(arr, 4, 4)
(跳过)QuickSort(arr, 6, 8)
=> partition(arr, 6, 8)
[33, 44, 31]
pivot = 33, i = 7, j = 8
44 > 33
i = 7
31 < 33
j = 8
swap(7, 8)
[33, 31, 44]
j = 8
跳出循环arr[8] > 33
j--
swap(6, 7)
[31, 33, 44]
返回 j = 7
QuickSort(arr, 6, 6)
(跳过) 和 QuickSort(arr, 8, 8)
(跳过)[2, 9, 15, 18, 21, 22, 31, 33, 44]
完成排序分析上面三个版本的实现,我们可以发现,在随机化越高的情况下,快速排序所用的轮次会越少,所以一般我们可以通过打乱数组后进行排序,效率更高
var swap = (arr, i, j) => {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
var randOne = (n, m) => n + Math.floor(Math.random() * (m - n + 1))
var shuffle = (arr) => {
let n = arr.length
for (let i = 0; i < n; i++) {
let rand = randOne(i, n - 1)
swap(arr, i, rand)
}
}
var sortArray = function(arr){
// 排序前先打乱其顺序
shuffle(arr)
return QuickSort(arr, 0, arr.length - 1)
}
复制代码
var sortArray = function(arr){
shuffle(arr)
return QuickSort(arr, 0, arr.length - 1)
}
var QuickSort = (arr, p, q) => {
if(p >= q) return arr
let m = partition(arr, p, q)
QuickSort(arr, p, m - 1)
QuickSort(arr, m + 1, q)
return arr
}
var partition = (arr, p, q) => {
let x = arr[p]
let i = p + 1
let j = q
while (i < j){
while (i < j && arr[i] <= x) i++
while (i < j && arr[j] >= x) j--
swap(arr, i, j)
}
if(arr[j] >= x) j--
swap(arr, p, j)
return j
}
var swap = (arr, i, j) => {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
var randOne = (n, m) => n + Math.floor(Math.random() * (m - n + 1))
var shuffle = (arr) => {
let n = arr.length
for (let i = 0; i < n; i++) {
let rand = randOne(i, n - 1)
swap(arr, i, rand)
}
}
复制代码
// 3路快排 [l,...lt, .. i, ... gt, r]
var QuickSort = (arr, l, r) => {
if(l >= r) return arr
let x = arr[l]
let lt = l
let gt = r + 1
let i = l + 1
while(i < gt){
if(arr[i] < x){
swap(arr, i, lt + 1)
lt++
i++
}else if(arr[i] > x){
swap(arr, i, gt - 1)
gt--
}else{
i++
}
}
swap(arr, lt, l)
QuickSort(arr, l, lt -1)
QuickSort(arr, gt, r)
return arr
}
复制代码
平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|
O(nlogn) | O(nlogn) | O(n^2) | O(n) | in-place | 不稳定 |
免费源码获取地址:http://www.crmeb.com
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。