JavaScript-Data-Structures-and-Alo/sort.html at master · cqA7/JavaScript-Data-Structures-and-Alo · 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
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>sort</title>
</head>
<body>
<script>
    let arr = [6, 65, 3, 1, 98, 87, 42, 24];
    console.log(arr);

    function swap(arr, i, j) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }

    //冒泡算法排序
    /*function sortBubble(arr) {
        for(let i = 0; i<arr.length;i++){
            for(let j = 0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
    }
    sortBubble(arr);
    console.log(arr);*/

    //鸡尾酒排序(对冒泡排序的改进算法)
    /*function CocktailSort(arr) {
        let left = 0;
        let right = arr.length-1;
        while (left < right){
            for(let i = left; i < right;i++){
                if(arr[i]>arr[i+1]){
                    swap(arr,i,i+1);
                }
            }
            right--;
            for(let j = right;j>left;j--){
                if(arr[j] < arr[j-1]){
                    swap(arr,j,j-1);
                }
            }
            left++;
        }
    }
    CocktailSort(arr);
    console.log(arr);*/

    //选择排序
    /*function selectSort(arr) {
        let min;
        for(let i = 0; i < arr.length-1;i++){
            min = i;
            for(let j = i+1;j<arr.length;j++){
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            if(min !== i){
                swap(arr,i,min);
            }
        }
    }
    selectSort(arr);
    console.log(arr);*/

    //插入法排序
    /*function insertSort(arr) {
        for (let i = 1; i < arr.length; i++) {
            let get = arr[i];
            let j = i - 1;
            while (j >= 0 && arr[j] > get) {
                arr[j + 1] = arr[j];//比较之后的动作第一步一定是先移动排好序的数字，然后才是放要插入的get
                j--;
            }
            arr[j + 1] = get;//放要插入的get
        }
    }
    insertSort(arr);
    console.log(arr);*/

    //二分插入排序
    /*function InsertionSortDichotomy(arr) {
        for (let i = 1; i < arr.length; i++) {
            let get = arr[i];
            let left = 0;
            let right = i - 1;
            //二分法
            while (left <= right) {
                let mid = parseInt((left + right) / 2);
                if (arr[mid] > get) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            //console.log(left);
            //插入排序
            for (let j = i - 1; j >= left; j--) {
                arr[j + 1] = arr[j];
            }
            arr[left] = get;
        }
    }

    InsertionSortDichotomy(arr);
    console.log(arr);*/

    //希尔排序(也叫递减增量排序，是插入排序的一种更高效的改进版本)
    /*function shellSort(arr) {
        let h = 0;
        while (h <= arr.length) {
            h = h * 3 + 1;//初始化增量(这个增量其实是没有固定的一个算法的)
        }
        while (h >= 1) {
            for (let i = h; i < arr.length; i = i + h) {
                let j = i - h;
                let get = arr[i];
                //console.log(get);
                while (j >= 0 && arr[j] > get) {
                    arr[j + h] = arr[j];
                    j = j - h;
                }
                arr[j + h] = get;
            }
            h = (h - 1) / 3;
        }
    }
    shellSort(arr);
    console.log(arr);*/

    //归并排序(递归版本)
    /*function mergeSort(arr) {
        // 设置终止的条件，
        if (arr.length < 2) {
            return arr;
        }
        //设立中间值
        let middle = parseInt(arr.length / 2);
        //第1个和middle个之间为左子列
        let left = arr.slice(0, middle);
        //第middle+1到最后为右子列
        let right = arr.slice(middle);
        if (left === "undefined" && right === "undefined") {
            return false;
        }
        return merge(mergeSort(left), mergeSort(right));
    }

    function merge(left, right) {
        let result = [];
        while (left.length && right.length) {
            if (left[0] <= right[0]) {
                //把left的左子树推出一个，然后push进result数组里
                result.push(left.shift());
            } else {
                //把right的右子树推出一个，然后push进result数组里
                result.push(right.shift());
            }
        }
        //经过上面一次循环，只能左子列或右子列一个不为空，或者都为空,把剩下的元素都放入新数组的后面
        while (left.length) {
            result.push(left.shift());
        }
        while (right.length) {
            result.push(right.shift());
        }
        return result;
    }

    console.log(mergeSort(arr));*/

    //堆排序

    //快速排序
    /*let quicksort = function(arr) {
        if(arr.length <= 1) return arr;

        let pivot = Math.floor((arr.length -1)/2);
        let val = arr[pivot], less = [], more = [];

        arr.splice(pivot, 1);
        arr.forEach((e)=>{
            e < val ? less.push(e) : more.push(e);
        });

        return (quicksort(less)).concat([val],quicksort(more));
    };

    console.log(quicksort(arr));*/
</script>
</body>
</html>