-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathjs_sort_arithemtic.html
More file actions
463 lines (414 loc) · 16.3 KB
/
Copy pathjs_sort_arithemtic.html
File metadata and controls
463 lines (414 loc) · 16.3 KB
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
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>JS十大排序算法</title>
</head>
<body>
<script>
//冒泡排序（bubble sort）
// var a = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
// bubbleSort(a);
// console.log(a);
// function bubbleSort(array) {
// for (let i = 0; i < array.length; i++) {
// for (let j = 0; j < array.length - 1 - i; j++) {
// if (array[j] > array[j + 1]) {
// let temp = array[j];
// array[j] = array[j + 1];
// array[j + 1] = temp;
// }
// }
// }
// }
//选择排序
// var a = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
// console.log(slectionSort(a));
// function slectionSort(array) {
// var minIndex, temp;
// for (let i = 0; i < array.length - 1; i++) {
// minIndex = i;
// for (let j = i + 1; j < array.length; j++) {
// if (array[j] < array[minIndex]) {
// minIndex = j;
// }
// }
// temp = array[i];
// array[i] = array[minIndex];
// array[minIndex] = temp;
// }
// return array;
// }
//插入排序
// var a = [9, 8, 11, 6, 11, 12, 3, 2, 1, 0];
// console.log(InsertSort(a))
// function InsertSort(array) {
// var preIndex, current;
// for (let i = 1; i < array.length; i++) {
// preIndex = i - 1;
// current = array[i];
// //将current的值与前面有序数组比较，然后插入
// while (preIndex >= 0 && current < array[preIndex]) {
// array[preIndex + 1] = array[preIndex];
// preIndex--;
// }
// array[preIndex + 1] = current;
// }
// return array;
// }
//折半插入排序
// console.log(InsertSort2(a));
// function InsertSort2(array) {
// var j, middle, low, heigh;
// var temp;
// for (let i = 1; i < array.length; i++) {
// temp = array[i]; //待插入数
// low = 0;
// heigh = i - 1;
// //折半查找应该插入的位置
// while (low <= heigh) {
// middle = Math.floor((low + heigh) / 2);
// if (temp >= array[middle]) {
// low = middle + 1;
// } else {
// heigh = middle - 1;
// }
// }
// //确定位置后将数插入
// //为temp腾出位置
// for (j = i - 1; j > heigh; j--) {
// array[j + 1] = array[j];
// }
// array[j + 1] = temp;
// }
// return array;
// }
// var a = [9, 8, 11, 6, 11, 12, 3, 2, 1, 0];
// console.log(shellSort(a));
// function shellSort(arr) {
// var len = arr.length,
// temp,
// gap = 1;
// while (gap < len / 3) { //动态定义间隔序列
// gap = gap * 3 + 1;
// }
// for (gap; gap > 0; gap = Math.floor(gap / 3)) {
// for (var i = gap; i < len; i++) {
// temp = arr[i];
// for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
// arr[j + gap] = arr[j];
// }
// arr[j + gap] = temp;
// }
// }
// return arr;
// }
// 希尔排序
// var a = [9, 8, 11, 6, 11, 12, 3, 2, 1, 0];
// shellSort(a);
// console.log(a);
// function shellSort(array) {
// var gap = 1;
// var temp;
// // 确定步长
// while (gap < array.length / 3) {
// gap = 3 * gap + 1;
// }
// for (gap; gap >= 1; gap = Math.floor((gap / 3))) {
// for (let i = gap; i < array.length; i++) {
// temp = array[i];
// for (var j = i - gap; j >= 0 && temp < array[j]; j -= gap) {
// array[j + gap] = array[j];
// }
// array[j + gap] = temp;
// }
// }
// }
// 归并排序
// var a = [9, 8, 11, 6, 11, 12, 3, 2, 1, 0];
// console.log(mergeSort(a));
// function mergeSort(array) { //自上而下递归
// if (array.length < 2) {
// return array;
// }
// var middle = Math.floor(array.length / 2);
// var left = array.slice(0, middle);
// var right = array.slice(middle);
// return merge(mergeSort(left), mergeSort(right));
// }
// // 排序部分
// function merge(left, right) {
// var result = [];
// while (left.length && right.length) {
// if (left[0] <= right[0]) {
// result.push(left.shift());
// } else {
// result.push(right.shift());
// }
// }
// while (left.length) {
// result.push(left.shift());
// }
// while (right.length) {
// result.push(right.shift());
// }
// return result;
// }
//归并排序——迭代
// var a = [9, 8, 11, 6, 11, 12, 101, 2, 1, 0];
// console.log(mergeSort(a));
// function mergeSort(array) {
// var i, next, left_min, left_max, right_min, right_max;
// var temp = new Array(array.length);
// //i：步长。逐级上升，第一次比较2个，第二次比较4个，第三次比较8个。。。
// for (i = 1; i < array.length; i *= 2) {
// //每次都从0开始，数组的头元素开始
// for (left_min = 0; left_min < array.length - i; left_min = right_max) {
// right_min = left_max = left_min + i;
// right_max = right_min + i;
// //right_max最大到n，防止越界
// if (right_max > array.length) {
// right_max = array.length;
// }
// //next是用来标志temp数组下标的，由于每次数据都有返回到K，
// //故每次开始得重新置零
// next = 0;
// //如果左边的数据还没达到分割线且右边的数组没到达分割线，开始循环
// while (left_min < left_max && right_min < right_max) {
// if (array[left_min] < array[right_min]) {
// temp[next++] = array[left_min++];
// } else {
// temp[next++] = array[right_min++];
// }
// }
// //如果左侧有剩余，将剩余的拼到右侧
// while (left_min < left_max) {
// array[--right_min] = array[--left_max];
// }
// while (next > 0) {
// array[--right_min] = temp[--next];
// }
// }
// }
// return array;
// }
//快速排序
//找中轴
//从右往左，右边赋值到左边；
//从左往右，左边赋值到右边；
//找中轴过程中，保证对于两个指针left和right，在它们相遇时，left左边的都比基准值小，right右边的都比基准值大
// var arr = [6, 5, 8, 7, 4, 3];
// quickSort(arr, 0, arr.length - 1);
// console.log(arr);
// function quickSort(arr, left, right) {
// if (left < right) {
// var index = getIndex(arr, left, right);
// quickSort(arr, left, index - 1);
// quickSort(arr, index + 1, right);
// }
// }
// function getIndex(arr, left, right) {
// var pivot = arr[left];
// while (left < right) {
// while (arr[right] >= pivot && left < right) {
// right--;
// }
// arr[left] = arr[right];
// while (arr[left] <= pivot && left < right) {
// left++;
// }
// arr[right] = arr[left];
// }
// arr[left] = pivot;
// return left;
// }
// //堆排序
// //数值交换
// function swap(arr, i, j) {
// let temp = arr[i];
// arr[i] = arr[j];
// arr[j] = temp;
// }
// //heapify操作
// function heapifty(arr, n, i) {
// var c1 = 2 * i + 1,
// c2 = 2 * i + 2,
// max = i;
// if (c1 < n && arr[max] < arr[c1]) {
// max = c1;
// }
// if (c2 < n && arr[max] < arr[c2]) {
// max = c2;
// }
// if (max != i) {
// swap(arr, max, i);
// heapifty(arr, n, max);//调整经改动的那个节点
// }
// }
// //建立大顶堆
// function build_heap(arr, n) {
// for (let i = Math.floor((n - 2) / 2); i >= 0; i--) {
// heapifty(arr, n, i);
// }
// }
// //排序
// function heapSort(arr) {
// build_heap(arr, arr.length);//构建堆
// var length = arr.length;
// for (let i = length - 1; i > 0; i--) {
// swap(arr, i, 0); //将堆首与堆尾互换，让最大的值到堆尾部；
// length--; // 将堆尾切掉
// heapifty(arr, length, 0); //再对堆进行heapify操作，让剩余最大值上浮到0号节点
// }
// }
// var arr = [6, 5, 8, 7, 4, 3, 9, 9, 4];
// heapSort(arr);
// console.log(arr);
// var arr = [6, 5, 8, 7, 4, 3, 9, 9, 4, 1, 1, 1, 1, 2];
// countingSort(arr, 9);
// console.log(arr);
//计数排序
// function countingSort(arr, maxValue) {
// var bucket = new Array(maxValue + 1),
// sortedIndex = 0;
// for (let i = 0; i < arr.length; i++) {
// if (!bucket[arr[i]]) { //如果bucket[arr[i]为非大于等于0的数字，就将它初始化为0
// bucket[arr[i]] = 0;
// }
// bucket[arr[i]]++;
// }
// //将排序后的数返还到原数组
// for (let j = 0; j < maxValue + 1; j++) {
// while (bucket[j]-- > 0) {
// arr[sortedIndex++] = j;
// }
// }
// }
// var arr = [6, 5, 8, 7, 4, 3, 9, 9, 4, 1, 1, 1, 1, 2];
// var arr = [1.1, 1.3, 8.6, 5.6];
// console.log(BucketSort(arr));
// quickSort(arr, 0, arr.length - 1);
// console.log(arr);
// 桶排序
// console.log(Math.ceil(0));
// function BucketSort(arr, gap) {
// if (arr.length === 0 || arr.length < 2) {
// return arr;
// }
// var minValue = arr[0],
// maxValue = arr[0],
// result = new Array();
// //找出arr的最大最小值
// for (let i = 0; i < arr.length; i++) {
// minValue = minValue < arr[i] ? minValue : arr[i];
// maxValue = maxValue > arr[i] ? maxValue : arr[i];
// }
// //初始化捅
// //同数量
// var DEFAULT_BUCKET_GAP = 5;
// gap = gap || DEFAULT_BUCKET_GAP;
// //计算桶的个数
// var bucketNum = Math.ceil((maxValue - minValue) / gap);
// var buckets = new Array(bucketNum);
// for (let i = 0; i < bucketNum; i++) {
// buckets[i] = [];
// }
// //利用映射函数将数据分配到各个桶中
// for (let i = 0; i < arr.length; i++) {
// var index;
// for (let j = 0; j < bucketNum; j++) {
// if (minValue <= arr[i] && arr[i] < minValue + gap * (j + 1)) {
// index = j;
// }
// }
// buckets[index].push(arr[i]);
// }
// //去除空桶
// buckets = buckets.filter(function(item) {
// return item.length;
// });
// //在每个桶中进行排序
// for (let i = 0; i < buckets.length; i++) {
// //对每个桶中数据进行排序，在将排好序的桶进行拼接
// // quickSort(buckets[i], 0, buckets[i].length - 1);
// InsertSort2(buckets[i]);
// result = result.concat(buckets[i]);
// }
// return result;
// }
//针对数字
//LSD
// var arr = [423, 115, 2225, 31, 15555];
// console.log(radixSort(arr));
// function radixSort(arr) {
// //求出最大数的位数
// var max = arr[0],
// dev = 1;
// for (let i = 1; i < arr.length; i++) {
// max = max > arr[i] ? max : arr[i];
// }
// var radix = max.toString().length;
// //针对每一位由低到高进行计数排序，共进行radix轮
// for (let i = 1; i <= radix; i++) {
// //结果暂存数组
// var temp = new Array();
// var count = new Array(10); //10个桶
// for (let j = 0; j < count.length; j++) {
// count[j] = [];
// }
// //把数组中的数放到桶中
// for (let k = 0; k < arr.length; k++) {
// let pos = parseInt(arr[k] / dev) % 10;
// count[pos].push(arr[k]);
// }
// dev *= 10;
// //将计数排序结果拼回
// for (let l = 0; l < 10; l++) {
// temp = temp.concat(count[l]);
// }
// arr = temp;
// }
// return arr;
// }
// var arr = ["banana", "apple", "orange", "ape", "he", "a"];
// console.log(radixSort_String(arr));
// function radixSort_String(arr) {
// if (arr.length < 2) {
// return arr;
// }
// var radix = arr[0].length;
// for (let i = 1; i < arr.length; i++) {
// radix = radix > arr[i].length ? radix : arr[i].length;
// }
// for (let j = 1; j <= radix; j++) {
// var s = "a";
// var temp = [];
// var count = new Array(26);
// for (let i = 0; i < count.length; i++) {
// count[i] = [];
// }
// //取出每个字符的第j位
// for (let k = 0; k < arr.length; k++) {
// if (arr[k].charAt(radix - j) == "") {
// count[0].push(arr[k]);
// } else {
// var pos = arr[k].charCodeAt(radix - j) - s.charCodeAt(0);
// count[pos].push(arr[k]);
// }
// }
// //将结果拼回
// for (let m = 0; m < 26; m++) {
// temp = temp.concat(count[m]);
// }
// arr = temp;
// }
// return arr;
// }
// }
// var s = "zZ"
// console.log(s.charCodeAt("0"), s.charCodeAt("1"));
// console.log(s.localeCompare("A"));
</script>
</body>
</html>