js-sort/test.html at master · caoweiju/js-sort · GitHub

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
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>排序测试</title>
    <style>
        html,body{
            padding: 0;
            margin: 0;
            height: 100%;
            width: 100%;
            font-size: 16px;
            color: #212121;
        }
        .test{
            height: 100%;
            width: 100%;
            display: flex;
            flex-direction: column;
            justify-content: center;
            align-items: center;
            background-color: #eee;
        }
    </style>
</head>
<body>
    <div class="test">
        chrome is the best test tools;
    </div>
    <script>
        let sortArray = [];
        // 生成若干个随机整数
        function mathRandom(num=10000) {
            let arrRes = [];
            for(let i=0; i<num; i++) {
                arrRes.push(parseInt(Math.random()*100000));
            }
            return arrRes;
        }

        sortArray = mathRandom(10000);
        console.log(`待排序数组结果：`, sortArray);

        const testSortTimeAnRes = function(sortFunc, sortFuncName, needSortArray) {
            let startTime = new Date().getTime();

            let res = sortFunc(needSortArray);

            let endTime = new Date().getTime();
            console.log(`${sortFuncName}耗时：`, endTime-startTime, "ms");
            console.log(`${sortFuncName}结果：`, res);
        }
        /**
         * 冒泡排序方法 先把大的数据冒泡上去[升序]
         * @param {*} needSortArray 是一个待排序的init 数组【未校验】
         */
        function Bubble_Sort(needSortArray=[]) {
            const isArray = Object.prototype.toString.call(needSortArray) === '[object Array]',
                isIntArray = needSortArray.every( item => typeof item === 'number');
            if(!isArray || !isIntArray) { // 校验整数数组
                return needSortArray;
            }
            const arrayLen = needSortArray.length;
            let okFlag = false;
            for(let i=0; i<arrayLen-1 && !okFlag; i++) {
                okFlag = true; // 假设已经OK
                for(let j=0; j<arrayLen-i-1; j++) {
                    let beforeNum = needSortArray[j],
                        afterNum = needSortArray[j+1];
                    if(beforeNum > afterNum) {
                        needSortArray[j] = afterNum;
                        needSortArray[j+1] = beforeNum;
                        okFlag = false; // 如果有变化说明排序还没完成
                    }
                }
            }
            return needSortArray;
        }
        testSortTimeAnRes(Bubble_Sort, '冒泡排序', [...sortArray]);

        /**
         * 选择排序
         * @param {*} needSortArray 待排序整形数组
         */
        function Select_Sort(needSortArray=[]) {
            const isArray = Object.prototype.toString.call(needSortArray) === '[object Array]',
                isIntArray = needSortArray.every( item => typeof item === 'number');
            if(!isArray || !isIntArray) { // 校验整数数组
                return needSortArray;
            }
            let minIndex = 0,
                arrayLen = needSortArray.length;
            for(let i=0; i<arrayLen-1; i++) {
                minIndex = i;
                for(let n=i+1; n<arrayLen; n++) {
                    needSortArray[minIndex] > needSortArray[n] && (minIndex=n);
                }
                if(i !== minIndex) {
                    let temp = needSortArray[i];
                    needSortArray[i] = needSortArray[minIndex];
                    needSortArray[minIndex] = temp;
                }
            }
            return needSortArray;
        }
        testSortTimeAnRes(Select_Sort, '选择排序', [...sortArray]);

        /**
         * 插入排序
         * @param {*} needSortArray 待排序数组
         */
        function Insertion_Sort(needSortArray=[]) {
            const isArray = Object.prototype.toString.call(needSortArray) === '[object Array]',
                isIntArray = needSortArray.every( item => typeof item === 'number');
            if(!isArray || !isIntArray) { // 校验整数数组
                return needSortArray;
            }
            let minIndex = 0,
                arrayLen = needSortArray.length;
            for(let i=1; i<arrayLen; i++) {
                let currInsertNum = needSortArray.splice(i, 1)[0];
                for(let j=i-1; j>=0; j--) {
                    if(currInsertNum > needSortArray[j]) {
                        needSortArray.splice(j+1, 0, currInsertNum);
                        break;
                    } else if(j===0) {
                        needSortArray.unshift(currInsertNum);
                    }
                }
            }
            return needSortArray;
        }
        testSortTimeAnRes(Insertion_Sort, '插入排序', [...sortArray]);

        /**
         * 希尔排序
         * @param {*} needSortArray
         */
         function Shell_Sort(needSortArray=[]){
            const isArray = Object.prototype.toString.call(needSortArray) === '[object Array]',
                isIntArray = needSortArray.every( item => typeof item === 'number');
            if(!isArray || !isIntArray) { // 校验整数数组
                return needSortArray;
            }
            let shell_gap_step = 2,
                arrayLen = needSortArray.length,
                initGap = Math.floor(arrayLen / shell_gap_step);
            //增量gap，并逐步缩小增量
            // debugger;
            for(let gap=initGap;gap>0;gap=Math.floor(gap/ shell_gap_step)){
                //从第gap个元素，逐个对其所在组进行直接插入排序操作
                for(let i=gap;i<arrayLen;i++){
                    let j = i;
                    while(j-gap>=0 && needSortArray[j]<needSortArray[j-gap]){
                        //插入排序采用交换法
                        let temp = needSortArray[j];
                        needSortArray[j] = needSortArray[j-gap];
                        needSortArray[j-gap] = temp;
                        j-=gap;
                    }
                }
            }
            return needSortArray;
        }
        testSortTimeAnRes(Shell_Sort, '希尔排序', [...sortArray]);

        /**
         * 单路快速排序
         */
        function Quick_Sort_Single(needSortArray=[], left, right) {
            const isArray = Object.prototype.toString.call(needSortArray) === '[object Array]',
                isIntArray = needSortArray.every( item => typeof item === 'number');
            if(!isArray || !isIntArray) { // 校验整数数组
                return needSortArray;
            }

            let arrayLen = needSortArray.length,
                partitionIndex;
            typeof left === 'number' || (left = 0);
            typeof right === 'number' || (right = arrayLen - 1);

            if (left < right) {
                let pivot = left,                      // 设定基准值（pivot）
                    index = pivot + 1,
                    temp;
                for (var i = index; i <= right; i++) {
                    if (needSortArray[i] < needSortArray[pivot]) {
                        temp = needSortArray[index];
                        needSortArray[index] = needSortArray[i];
                        needSortArray[i] = temp;
                        index++;
                    }
                }
                partitionIndex = index-1;
                temp = needSortArray[partitionIndex];
                needSortArray[partitionIndex] = needSortArray[pivot];
                needSortArray[pivot] = temp;
                Quick_Sort_Single(needSortArray, left, partitionIndex-1);
                Quick_Sort_Single(needSortArray, partitionIndex+1, right);
            }
            return needSortArray;
        }
        testSortTimeAnRes(Quick_Sort_Single, '单路快速排序', [...sortArray]);

        /**
         * 快速排序[双路]
         * @param {*} needSortArray 待排序数组
         */
         function Quick_Sort_Double(needSortArray=[], left, right) {
            const isArray = Object.prototype.toString.call(needSortArray) === '[object Array]',
                isIntArray = needSortArray.every( item => typeof item === 'number');
            if(!isArray || !isIntArray) { // 校验整数数组
                return needSortArray;
            }

            let arrayLen = needSortArray.length,
                partitionIndex;
            typeof left === 'number' || (left = 0);
            typeof right === 'number' || (right = arrayLen - 1);

            if (left < right ) {
                let pivot = left,          // 设定基准值（pivot）为左侧第一个
                    currPivotValue= needSortArray[pivot],
                    leftPoint = left, // 左路探针
                    rightPoint = right, // 右路探针 左侧第一个是基准，先移动右路探针
                    // rightPointFirstCount = 0, // 右侧探针第一次扫描
                    // rightPointHasEverFindValue = false,
                    temp;
                while(leftPoint < rightPoint) {
                    // 右侧探针移动 找到小于基准值位置为止
                    while(currPivotValue <= needSortArray[rightPoint] && leftPoint < rightPoint) {
                        rightPoint--;
                    }
                    // 检测右侧探针是否第一趟直接和左侧探针汇合都没有找到合适的元素
                    // rightPointFirstCount++;
                    // rightPointFirstCount === 1 && (leftPoint < rightPoint) && (rightPointHasEverFindValue=true);
                    // 左侧探针移动 找到大于基准值位置为止
                    while(currPivotValue >= needSortArray[leftPoint] && leftPoint < rightPoint) {
                        leftPoint++;
                    }
                    // 交换左右指针的值 【如果左右探针汇合了 其实可以不交换】
                    temp = needSortArray[leftPoint];
                    needSortArray[leftPoint] = needSortArray[rightPoint];
                    needSortArray[rightPoint] = temp;
                }
                // [交换值的时候都要考虑需不需要交换，如果是右侧探针第一趟直接和左侧探针汇合都没有找到合适的元素就不能更换]
                // 如果是右侧探针第一趟直接和左侧探针汇合都没有找到合适的元素就不能更换则不换位置  否则基准和左侧指针交换值
                // 如果还没有进行比较，生成探针的时候左右探针就已经重合了需要手动对比基准值和左探针值
                // if(rightPointHasEverFindValue || needSortArray[leftPoint] < currPivotValue) {
                //     needSortArray[pivot] = needSortArray[leftPoint];
                //     needSortArray[leftPoint] = currPivotValue;
                // } else {
                //     leftPoint = left; // 如果没有交换 说明当前基准已经是正确的基准 把做指针指向基准
                // }
                needSortArray[pivot] = needSortArray[leftPoint];
                needSortArray[leftPoint] = currPivotValue;
                Quick_Sort_Double(needSortArray, left, leftPoint-1);
                Quick_Sort_Double(needSortArray, leftPoint+1, right);
            }
            return needSortArray;
        }
        testSortTimeAnRes(Quick_Sort_Double, '双路快速排序', [...sortArray]);

        /**
         * 归并排序
         * @param {*} needSortArray 待排序数组
         */
        function Merge_Sort(needSortArray=[]) {
            const isArray = Object.prototype.toString.call(needSortArray) === '[object Array]',
                isIntArray = needSortArray.every( item => typeof item === 'number');
            if(!isArray || !isIntArray) { // 校验整数数组
                return needSortArray;
            }

            const merge = (left, right) => {
                let result = [];

                while (left.length>0 && right.length>0) {
                    if (left[0] <= right[0]) {
                        result.push(left.shift());
                    } else {
                        result.push(right.shift());
                    }
                }
                // 把多余的直接追加
                result.push(...left);
                result.push(...right);

                return result;
            }

            let len = needSortArray.length;
            if (len < 2) {
                return needSortArray;
            }
            let middle = Math.floor(len / 2),
                left = needSortArray.slice(0, middle),
                right = needSortArray.slice(middle);
            return merge(Merge_Sort(left), Merge_Sort(right));
            // return needSortArray;
        }
        testSortTimeAnRes(Merge_Sort, '归并排序', [...sortArray]);
    </script>
</body>
</html>