也算是一时兴起，对着手机拾掇了一早上，实现了一些简单的排序算法。
冒泡排序
这个不必多说，最经典的排序算法之一，下面我也是用的最经典的解决方案，同时对算法进行了优化，减少了不必要的比较次数。
冒泡排序在嵌套循环都为数组长度的话，这个时候的循环最多次数是N的平方，但是用以下的算法，比较的次数可以减少一半。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16function bubbleSort(arr){
console.time('冒泡排序耗时')
var len = arr.length; //定义冒泡排序的数组长度
var n; //定义n用于在冒泡排序时进行位置调换
for (var i = 0; i < len-1; i++) { //外层循环，使冒泡排序循环数组长度
for (var j = 0; j < len-i-1; j++) {
if (arr[j] > arr[j+1]) {
n = arr[j];
arr[j] = arr[j+1];
arr[j+1] = n;
}
}
}
console.timeEnd('冒泡排序耗时')
}
冒泡排序的经典算法经过我自己思考优化后，其实还存在一个多次比较的问题，在网上查了些资料，大佬们给出了另一种算法，主要的优化点在于，记录上要调换的位置，然后从要调换的位置开始进行调换，调换之后，再对剩余的地方进行调换。无疑减少了在一个不需要调换的位置进行多次比较的次数。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20function betterBubbleSort(arr){
console.time('改进后冒泡排序耗时')
var i = arr.length-1; //定义i为数组的最后一位数
var n; //n作为中间值，用于进行数组调换
while(i > 0){
var pos = 0; //记录需要调换的位置
for(var j = 0; j < i; j++){ //
if (arr[j] > arr[j+1]) {
pos = j;
n = arr[j];
arr[j] = arr[j+1];
arr[j+1] = n;
}
}
i = pos;
}
console.timeEnd('改进后冒泡排序耗时')
return arr;
}
以上算法对于计算次数已经有了较多的优化了，计算次数显然已经不能再往下优化，但是还有一点就是，我们能否进行多线程的计算，从而缩短整体的计算时间呢？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
26function bestBubbleSort(arr){
console.time('改进后冒泡排序耗时')
var low = 0;
var high = arr.length -1;
var tmp,j;
while(low < high){
for(j = low; j < high; ++j){
if( arr[j] > arr[j+1]){
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
--high;
for(j = high; j > low; --j){
if( arr[j] < arr[j-1]){
tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
}
++low;
}
console.timeEnd('改进后冒泡排序耗时')
return arr;
}
选择排序的算法
选择排序是先在数组中进行查找而不调换位置，找到数组中最小数之后，将最小数放到数组的第一个位置，然后再次寻找第二个数。这样做的好处就是，相比于冒泡排序，大大减少了两个数组元素调换位置所产生的内存消耗和计算量。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22function selectionSort(arr){
var len = arr.length-1; //定义数组的长度，并赋值给len
console.time('选择排序耗时'); //设置计时开始
var minindex,temp;
for (var i = 0; i < len; i++) {
minindex = i;
//设置最小数组下标为minindex，将i赋值给minindex
for( var j = i; j < len; j++){
//设置循环，循环区间为最小值到最后一位数
if (arr[j] < arr[minindex]) {
//若某数小于第minindex个数组的值，就把它赋值给minindex
minindex = j;
}
}
//进行最小值与需要调换值的数组下标调换
temp = arr[i];
arr[i] = arr[minindex];
arr[minindex] = temp;
}
console.timeEnd('选择排序耗时');
return arr;
}
插入排序算法
插入排序即是将需要排序的数组中的元素，逐次插入，以达到排序的效果，亲测此方法比上面的两个方法所耗时间都要短。1
2
3
4
5
6
7
8
9
10
11
12
13
14function insertionSort(arr){
console.time('插入排序耗时'); //设置计时开始
for( var i = 1; i < arr.length; i++){
var key = arr[i];
var j = i - 1;
while(j >= 0 && arr[j] > key){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
console.timeEnd('插入排序耗时'); //设置计时开始
return arr;
}
排序算法耗时汇总
冒泡排序三个方法在随机生成10000个数并对其进行排序的计算中，均耗时约300ms，选择排序和插入排序则耗时较短些，选择排序耗时约200ms左右，插入排序可达到低于200ms。
JS内核的自带排序算法
不多说了，就是这个sort()方法，简直想给它跪舔！同样用10000个随机生成的0-100的数，对其进行排序，其计算时间竟然能缩短到逆天的15ms！但是并没有办法详细了解其深层次的原因，听说是因为V8引擎的优化，和基于C++的算法优化所产生的效果。