-
Notifications
You must be signed in to change notification settings - Fork 0
/
algorithm.js
196 lines (170 loc) · 4.18 KB
/
algorithm.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
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
188
189
190
191
192
193
194
195
196
// 各种排序算法的实现
function ArrayList () {
var array = []
var swap = function (index1, index2) {
var aux = array[index1]
array[index1] = array[index2]
array[index2] = aux
}
// 归并排序辅助,用于合并排序
var merge = function (left, right) {
var result = [],
il = 0,
ir = 0
// 将左右两个数组元素的大小进行比较,按从小到大的顺序推入result数组
while (il < left.length && ir < right.length) {
if (left[il] < right[ir]) {
result.push(left[il++])
} else {
result.push(right[ir++])
}
}
// 上一轮比较之后其中一个数组还剩下一些元素,再将这些元素继续推入result数组
while (il < left.length) {
result.push(left[il++])
}
while (ir < right.length) {
result.push(right[ir++])
}
// 返回完成排序的数组
return result
}
// 归并排序辅助函数,用于拆分数组
var mergeSortRect = function (array) {
var length = array.length
if (length == 1) {
return array
}
var mid = Math.floor(length / 2),
left = array.slice(0, mid),
right = array.slice(mid, length)
return merge(mergeSortRect(left), mergeSortRect(right))
}
var partition = function (array, left, right) {
var pivot = array[Math.floor((right + left) / 2)],
i = left,
j = right
while (i <= j) {
while (array[i] < pivot) {
i++
}
while (array[j] > pivot) {
j--
}
if (i <= j) {
var temp = array[i]
array[i] = array[j]
array[j] = temp
i++
j--
}
}
return i
}
var quick = function (array, left, right) {
var index
if (array.length > 1) {
index = partition(array, left, right)
if (left < index - 1) {
quick(array, left, index - 1)
}
if (index < right) {
quick(array, index, right)
}
}
}
this.insert = function (item) {
array.push(item)
}
this.toString = function () {
return array.join()
}
// 自己实现的不知道什么排序,复杂度O(n^2)
this.donKnowWhatSort = function () {
var length = array.length
for (var i = 0; i < length; i++) {
for (var j = i; j < length; j++) {
if (array[i] > array[j]) {
swap(i, j)
}
}
}
}
// 改进后的冒泡排序,复杂度O(n^2)
this.bubbleSort = function () {
var length = array.length
for (var i = 0; i < length; i++) {
for (var j = 0; j < length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
swap(j, j + 1)
}
}
}
}
// 选择排序,复杂度O(n^2)
this.selectionSort = function () {
var length = array.length,
minIndex
for (var i = 0; i < length - 1; i++) {
minIndex = i
for (var j = i+1; j < length; j++) {
if (array[i] > array[j]) {
minIndex = j
}
}
if (minIndex !== i) {
swap(i, minIndex)
}
}
}
// 插入排序,复杂度O(n^2)
this.insertionSort = function () {
var length = array.length,
j, temp
for (var i = 1; i < length; i++) {
j = i
temp = array[i]
while (j > 0 && array[j - 1] > temp ) {
array[j] = array[j - 1]
j--
}
array[j] = temp
}
}
// 归并排序
this.mergeSort = function () {
array = mergeSortRect(array)
}
this.quickSort = function () {
quick(array, 0, array.length - 1)
}
this.binarySearch = function (item) {
var length = array.length
this.quickSort(array)
var low = 0,
high = array.length - 1,
middle, element
while (low <= high) {
middle = Math.floor((low + high) / 2)
element = array[middle]
if (item > element) {
low = middle + 1
} else if (item < element) {
high = middle - 1
} else {
return item
}
}
return -1
}
}
// 为数组插入元素
function createNonSortedArray (size) {
var array = new ArrayList()
for (var i = size; i > 0; i--) {
array.insert(i)
}
return array
}
/* var array = createNonSortedArray(50)
console.log(array.binarySearch(34)) */