-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path15_排序算法.html
187 lines (173 loc) · 5.77 KB
/
15_排序算法.html
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>排序算法</title>
</head>
<body>
<script>
function ArrayList() {
this.array = []
ArrayList.prototype.insert = function (item) {
this.array.push(item)
}
ArrayList.prototype.toString = function () {
return this.array.join('-')
}
// 1.冒泡排序
// 每次比较n次 交换n次
ArrayList.prototype.bubbleSort = function () {
let length = this.array.length
while (length !== 1) { // O(n^2)
for (let i = 0; i < length - 1; i ++) {
if (this.array[i] > this.array[i+1]) {
let temp = this.array[i]
this.array[i] = this.array[i+1]
this.array[i+1] = temp
}
}
length --
}
}
// 2.选择排序
// 每次选择最小值 每次比较n次 交换1次
ArrayList.prototype.selectSort = function () {
let currentIndex = 0
let length = this.array.length
while (currentIndex !== length-1) { // 两个数 2 1 比较一次
let _index = 0 //用于记录找到更小的那个的index
let min = this.array[currentIndex] //储存最小值
for (let i = currentIndex + 1; i < length; i ++) {
if (this.array[i] < min) {
_index = i //记录index
min = this.array[i] //记录值
}
}
if (_index) { //如果存在交换情况 才执行下面
this.array[_index] = this.array[currentIndex]
this.array[currentIndex] = min
}
currentIndex ++
}
}
// 3.插入排序
ArrayList.prototype.insertSort = function () {
let length = this.array.length
for (let i = 1; i < length; i ++) {
let j = i - 1
outValue = this.array[i] // 将值取出
while (j >= 0 && outValue < this.array[j]) { //将较大的数往后移
this.array[j + 1] = this.array[j]
j --
}
this.array[j + 1] = outValue
}
}
// 4.希尔排序 效率比插入排序高
ArrayList.prototype.shellSort = function () {
let length = this.array.length
let gap = Math.floor(length / 2) // 间隔
while (gap >= 1) { // 最后一次进行 间隔为1的插入排序
//进行插入排序
for (let i = gap; i < length; i ++) {
let j = i - gap // 前一个
let outValue = this.array[i] // 取出来的值
while (outValue < this.array[j] && j >= 0) {
this.array[j + gap] = this.array[j] //把大的往后移
j -= gap
}
this.array[j + gap] = outValue
}
gap = Math.floor(gap / 2) // 希尔间隔 n/2 .....
}
}
// 5.快速排序
// utils swap(i, j)
ArrayList.prototype.swap = function (i, j) { //交换两位置
if (i === j) {
return
}
let temp = this.array[i]
this.array[i] = this.array[j]
this.array[j] = temp
}
// findMedian 寻找中位数
ArrayList.prototype.findMedian = function (left, right, center) {
if (this.array[left] > this.array[center]) {
this.swap(left, center)
}
if(this.array[center] > this.array[right]) {
this.swap(center, right)
}
if (this.array[left] > this.array[center]) {
this.swap(left, center)
}
return this.array[center]
}
// quickUtil
ArrayList.prototype.quickUtil = function (left, right) {
if (left >= right) {
return
}
let center = Math.floor((left + right) / 2)
let median = this.findMedian(left, right, center) //找到中值
console.log(median)
// 现在 center处就是中值 交换到 right的前一个
this.swap(center, right) // 如果相邻也没问题
let i = left
let j = right - 1
while (true) {
while (this.array[i] < median) {
i ++
}
while (this.array[j] > median && j > i) {
j --
}
// 两个都找到了 如果指向同一位置 则 替换
if (i === j) {
this.swap(i, right)
break
} else {
// 如果两个的指向不同
this.swap(i, j)
}
}
// 找到正确的位置 i 和 j 的指向都为 median
this.quickUtil(left, i - 1) //left
this.quickUtil(i + 1, right) //right
}
ArrayList.prototype.quickSort = function () {
let length = this.array.length
let left = 0
let right = length - 1
this.quickUtil(left, right)
}
}
let a = new ArrayList()
a.insert(2)
a.insert(1)
a.insert(3)
a.insert(5)
a.insert(7)
a.insert(10)
a.insert(13)
a.insert(81)
a.insert(533)
a.insert(133)
a.insert(0)
a.insert(8)
console.log(a.toString())
// a.bubbleSort()
// console.log('冒泡排序', a.toString())
// a.selectSort()
// console.log('选择排序', a.toString())
// a.insertSort()
// console.log('插入排序', a.toString())
// a.shellSort()
// console.log('希尔排序', a.toString())
a.quickSort()
console.log('快速排序', a.toString())
</script>
</body>
</html>