js版本5种排序算法

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
//百度来的随机打乱数组用的函数
function randomsort(a, b) {
    return Math.random()>.5 ? -1 : 1
    //用Math.random()函数生成0~1之间的随机数与0.5比较，返回-1或1
}

//交换num数组索引a和b的值
function ex(num,a,b){
    let x=num[a]
    num[a]=num[b]
    num[b]=x
}


//希尔排序
function shellSort(num1){
    var num=JSON.parse(JSON.stringify(num1))
    arr=[]
    var i=1
    while(i<num.length){
        arr.unshift(i)
        i=i*3+1
    }
    for(let i in arr){
        let j=arr[i]
        //console.log(j,num)
        for(let x=j;x<num.length;x++){
            var y=x
            //这里不需要写num[y]<num[y-j]，用插入排序模拟即可
            while(y<num.length&&num[y]<num[y-j]){
                ex(num,y,y-j)
                y=y-j
            }
        }
    }
    return num
}


//归并排序
function mergeBUSort(num1){
    var num=JSON.parse(JSON.stringify(num1))
    mergeBUSort_(num,0,num.length-1)
    return num
}

function mergeBUSort_(num,lo,hi){
    if(lo>=hi)return			
    //lo比hi小5到15时建议切换插入排序，这里insertSort未实现				
    //if(hi-lo>5&&hi-lo<15){insertSort(num,lo,hi);return}			
    var mid=Math.floor((hi-lo)/2)+lo
    mergeBUSort_(num,lo,mid)
    mergeBUSort_(num,mid+1,hi)
    merge_(num,lo,mid,hi)
}

function merge_(num,lo,mid,hi){
    var arr=[]
    var i=lo
    var j=mid+1
    while(i<=mid&&j<=hi){
        if(num[i]>num[j]){arr.push(num[j++])}
        else{arr.push(num[i++])}
    }
    for(let x=i;x<=mid;x++){arr.push(num[x])}
    for(let x=j;x<=hi;x++){arr.push(num[x])}
    for(let x=lo;x<=hi;x++){num[x]=arr[x-lo]}
}


//快速排序
function quickSort(num1){
    var num=JSON.parse(JSON.stringify(num1))
    //console.log('-->',num)
    quickSort_(num,0,num.length-1)
    return num
}

function quickSort_(num,lo,hi){
    //console.log(num,lo,hi)
    if(lo>=hi)return						//lo比hi小5到15时建议切换插入排序，代码同上
    let mid=partition(num,lo,hi)
    quickSort_(num,lo,mid-1)
    quickSort_(num,mid+1,hi)
}

function partition(num,lo,hi){
    var i=lo+1
    var j=hi
    let temp=num[lo]
    while(i<=j&&i<=hi&&lo<j){
        while(num[i]<=temp&&i<=hi)i++
        while(num[j]>=temp&&lo<j)j--
        if(i<j){ex(num,i++,j--)}
    }
    ex(num,lo,j)
    return j
}


//三向切分的快速排序
function quick3WaySort(num1){
    var num=JSON.parse(JSON.stringify(num1))
    //console.log(num)
    quick3WaySort_(num,0,num.length-1)
    return num
}

function quick3WaySort_(num,lo,hi){
    //console.log(num,lo,hi)
    if(lo>=hi)return
    let mid=partition3Way(num,lo,hi)
    quick3WaySort_(num,lo,mid[0]-1)
    quick3WaySort_(num,mid[1]+1,hi)
}

function partition3Way(num,lo,hi){
    var c=lo
    var i=lo+1
    var j=hi
    let temp=num[lo]
    while(i<=j&&i<=hi&&lo<j){
        if(num[i]>temp)ex(num,i,j--)
        if(num[i]<temp)ex(num,c++,i++)
        if(num[i]==temp&&i<=hi)i++
    }
    return [c,j]
}


//堆排序heapSort,使用递增的二叉堆
function up(heap,maxIndex,i){
    var j=Math.floor(i/2)
    while(heap[i]<=heap[j]&&i>1){
        ex(heap,i,j)
        i=j
        j=Math.floor(i/2)
    }
}
function down(heap,maxIndex,i){
    var j=i*2
    while (j<=maxIndex){
        if(j<maxIndex&&heap[j+1]<heap[j])j++
        if(heap[i]>=heap[j])ex(heap,i,j)
        i=j
        j=i*2
    }
}
function generateHeap(num1){
    var num=JSON.parse(JSON.stringify(num1))
    num.unshift(undefined)
    return num
}
function getSortedHeap(heap){
    let len_=heap.length
    for(let i=Math.floor(len_/2);i>0;i--){
        down(heap,len_-1,i)
    }
    return heap
}
function heapSort(heap){
    let ind=heap.length-1
    while(ind>0){
        ex(heap,1,ind)
        down(heap,ind-1,1)
        ind--
    }
    heap.splice(0,1)
    return heap.reverse()
}

//开始测试
var N=100000
var num=[]
for(let i=1;i<1+N;i++){
    num.push(i)
    num.push(i)
}
let res=JSON.stringify(num)
num.sort(randomsort)
console.log(num)
console.log('shellSort-->',JSON.stringify(shellSort(num))==res)
console.log('mergeBUSort-->',JSON.stringify(mergeBUSort(num))==res)
console.log('quickSort-->',JSON.stringify(quickSort(num))==res)
console.log('quick3WaySort-->',JSON.stringify(quick3WaySort(num))==res)
console.log('heapSort-->',JSON.stringify(heapSort(getSortedHeap(generateHeap(num))))==res)

1
2
3