-
Notifications
You must be signed in to change notification settings - Fork 0
/
912. Sort an Array.js
92 lines (74 loc) · 1.62 KB
/
912. Sort an Array.js
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
return quickSort(nums)
}
function quickSort(arr = []) {
if (arr.length <= 1) return arr
const pivot = arr.splice(Math.floor(arr.length / 2), 1)
const leftArr = []
const rightArr = []
arr.forEach((item) => {
if (item < pivot) {
leftArr.push(item)
} else {
rightArr.push(item)
}
})
return [...quickSort(leftArr), pivot, ...quickSort(rightArr)]
}
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
quickSort(nums, 0, nums.length - 1)
return nums
}
function quickSort(nums, l, r) {
partition(nums, l, r)
insertSort(nums, l, r)
}
function partition(nums, l, r) {
while (r - l > 16) {
let x = l,
y = r,
base = getMid(nums[l], nums[r], nums[Math.floor((l + r) / 2)])
do {
while (x < y && nums[x] < base) x++
while (x < y && nums[y] > base) y--
if (x < y) {
;[nums[x], nums[y]] = [nums[y], nums[x]]
x++
y--
}
} while (x < y)
partition(nums, x + 1, r)
r = x
}
}
function insertSort(nums, l, r) {
let ind = l
for (let i = l; i <= r; i++) {
if (nums[ind] > nums[i]) ind = i
}
while (ind > l) {
;[nums[ind - 1], nums[ind]] = [nums[ind], nums[ind - 1]]
ind--
}
for (let i = l + 2; i <= r; i++) {
let j = i
while (nums[j] < nums[j - 1]) {
;[nums[j], nums[j - 1]] = [nums[j - 1], nums[j]]
j--
}
}
}
function getMid(a, b, c) {
if (a > b) return getMid(b, a, c)
if (a > c) return getMid(c, b, a)
if (b > c) return getMid(a, c, b)
return b
}