算法学习

排序

算法学习 📒 repo

快速排序

http://www.conardli.top/docs/algorithm/%E6%8E%92%E5%BA%8F/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F.html#%E6%80%9D%E6%83%B3

这个方法比较简单也很好理解

方法一

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
let list = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];
// 自定义个数
let ageLists = []
for(let i = 0; i <=100; i++) {
let id = Math.floor(Math.random() * 100 + 1)
ageLists.push({
id: id,
age: Math.floor(Math.random() * 40 + 1),
name: `学号${i}`,
type: 'student'
})
}

console.log(ageLists)

// 排数组
function quickSort(array) {
if (array.length <= 1) {
return array
}

let target = array[0]
let left = []
let right = []

for (let i = 1; i < array.length; i++) {
if (array[i] < target) {
left.push(array[i])
} else {
right.push(array[i])
}
}

return quickSort(left).concat([target], quickSort(right))
}

console.log(quickSort(list))

// 排对象
function quickSortObj(array, key) {
if (array.length <= 1) {
return array
}

let target = array[0]
let left = []
let right = []

for (let i = 1; i < array.length; i++) {
if (array[i][key] < target[key]) {
left.push(array[i])
} else {
right.push(array[i])
}
}

return quickSortObj(left, key).concat([target], quickSortObj(right, key))
}

console.time('quickSortObj')
console.log(quickSortObj(ageLists, 'id'))
console.timeEnd('quickSortObj')

方法二

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
// 排序数组
function quickSort(array, start, end) {
if (end - start < 1) return

let target = array[start]
let l = start
let r = end

while (l < r) {
while (l < r && array[r] >= target) {
r--
}
array[l] = array[r]
while (l < r && array[l] < target) {
l++
}
array[r] = array[l]
}

array[l] = target

quickSort22(array, start, l - 1)
quickSort22(array, l + 1, end)
return array
}

console.time('quickSort')
console.log(quickSort(list, 0, list.length - 1))
console.timeEnd('quickSort')

// 拍对象
function quickSort2Obj(array, start, end, key) {
if (end - start < 1) return

let target = array[start]
let l = start
let r = end

while(l < r) {
while(l < r && array[r][key] >= target[key]) {
r--
}
array[l] = array[r]

while(l < r && array[l][key] < target[key]) [
l++
]
array[r] = array[l]
}

array[l] = target

quickSort2Obj(array, start, l - 1, key)
quickSort2Obj(array, l + 1, end, key)

return array
}

console.time('quickSort2Obj')
console.log(quickSort2Obj(ageLists, 0, ageLists.length - 1, 'id'))
console.timeEnd('quickSort2Obj')

这个对比方法一难点, 一下不容易理解

经过测试 少量的数据 方法二有时候比方法一要慢(10 - 100), 但是数据足够大的时候 方法二比方法一就要快很多(10000左右)

归并排序

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
let list = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];

function mergeSort(array) {
if (array.length < 2) {
return array
}

let mid = Math.floor(array.length / 2)
let front = array.slice(0, mid)
let end = array.slice(mid)

return merge(mergeSort(front), mergeSort(end))
}

function merge(front, end) {
let temp = []

while (front.length && end.length) {
if (front[0] < end[0] ){
temp.push(front.shift())
} else {
temp.push(end.shift())
}
}

while(front.length) {
temp.push(front.shift())
}
while(end.length) {
temp.push(end.shift())
}
return temp
}

console.time()
console.log(mergeSort(list))
console.timeEnd()

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let list = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];

function selectionSort(array) {
for (let i = 0; i < array.length - 1; i++) {
let minIndex = i
for (let j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j
}
}
[array[minIndex], array[i]] = [array[i], array[minIndex]]
}
return array
}

console.time()
console.log(selectionSort(list))
console.timeEnd()

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
let list = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];


function insertSort(array) {
for (let i = 1; i < array.length; i++) {
let target = i
for (let j = i - 1; j >= 0; j--) {
if (array[target] < array[j]) {
[array[target], array[j]] = [array[j], array[target]]
target = j
} else {
break
}
}
}
return array
}


console.time()
console.log(insertSort(list))
console.timeEnd()

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
let list = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];

function bubbleSort(array) {
for (let i = 0; i < array.length; i++) {
let complate = true
for (let j = 0; j < array.length - 1 - i; j++) {
console.log(1, array.length - 1 - i)
if (array[j] > array[j + 1]) {
[array[j], array[j + 1]] = [array[j + 1], array[j]]
complate = false
}
}
if (complate) {
break
}
}
return array
}

console.time()
console.log(bubbleSort(list))
console.timeEnd()

堆排序

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
let list = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];

function heapSort(array) {
createHeap(array)
console.log('array', array)
// 交换第一个和最后一个元素,然后重新调整大顶堆
for (let i = array.length - 1; i > 0; i--) {
[array[i], array[0]] = [array[0], array[i]]
adJust(array, 0, i)
}
return array
}

// 构建大顶堆,从第一个非叶子节点开始,进行下沉操作
function createHeap(array) {
const len = array.length
const start = parseInt(len / 2) - 1
for (let i = start; i >= 0; i--) {
adJust(array, i, len)
}
}
// 将第target个元素进行下沉,孩子节点有比他大的就下沉
function adJust(array, target, len) {
for (let i = 2 * target + 1; i < len; i= 2 * i + 1) {
// 找到孩子节点中最大的
if (i + 1 < len && array[i + 1] > array[i]) {
i = i + 1
}
// 下沉
if (array[i] > array[target]) {
[array[i] ,array[target]] = [array[target], array[i]]
target = i
} else {
break
}
}
}

console.time()
console.log(heapSort(list))
console.timeEnd()
打赏测试