js排序的时间复杂度_JS中的算法与数据结构——排序
（Sort）
排序算法(Sort)
引⾔
我们平时对计算机中存储的数据执⾏的两种最常见的操作就是排序和查，对于计算机的排序和查的研究，⾃计算机诞⽣以来就没有停⽌过。如今⼜是⼤数据，云计算的时代，对数据的排序和查的速度、效率要求更⾼，因此要对排序和查的算法进⾏专门的数据结构设计，(例如我们上⼀篇聊到的⼆叉查树就是其中⼀种)，以便让我们对数据的操作更加简洁⾼效。
这⼀篇我们将会介绍⼀些数据排序的基本算法和⾼级算法并利⽤JavaScript来逐⼀实现，让⼤伙对计算机中常见的排序算法的思想和实现有基本的了解，起到⼀个抛砖引⽟的作⽤。
关于排序算法的说明
在介绍各个算法之前，我们有必要了解⼀下评估算法优劣的⼀些术语：
稳定：如果a原本在b前⾯，当a=b时，排序之后a仍然在b的前⾯
不稳定：如果a原本在b的前⾯，当a=b时，排序之后a可能会出现在b的后⾯
内排序：所有排序操作都在内存中完成
外排序：由于数据太⼤，因此把数据放在磁盘中，⽽排序通过磁盘和内存的数据传输才能进⾏
时间复杂度：⼀个算法执⾏所耗费的时间
空间复杂度：运⾏完⼀个程序所需内存的⼤⼩
有想要了解更多，关于时间空间复杂度的，我推荐⼀篇⽂章，请戳这⾥这⾥
基本排序算法
基本排序算法的核⼼思想就是对⼀组数据按照⼀定的顺序重新排序，其中重排时⼀般都会⽤到⼀组嵌套的 for 循环，外循环会遍历数组的每⼀项元素，内循环则⽤于进⾏元素直接的⽐较。
1.冒泡排序(BubbleSort)
冒泡排序是⽐较经典的算法之⼀，也是排序最慢的算法之⼀，因为它的实现是⾮常的容易的。
冒泡排序的算法思想如下(升序排序)：
⽐较相邻的元素。如果第⼀个⽐第⼆个⼤，就交换它们两个；
对每⼀对相邻元素作同样的⼯作，从开始第⼀对到结尾的最后⼀对，这样最终最⼤数被交换到最后的位置
除了最后⼀个元素以外，针对所有的元素重复以上的步骤
重复步骤1~3，直到排序完成
下⾯我借⽤⽹上⼀张动图，来展⽰冒泡排序的过程：
冒泡排序
具体的JS实现如下：
//冒泡排序
function bubbleSort ( data ) {
var temp = 0;
for ( var i = data.length ; i > 0 ; i -- ){
for( var j = 0 ; j < i - 1 ; j++){
if( data[j] > data[j + 1] ){
temp = data[j];
data[j] = data [j+1];
data[j+1] = temp;
}
}
}
return data;
}
我们先设定⼀组数据，后⾯我们将都⽤这组数据来测试 :
var dataStore = [ 72 , 1 , 68 , 95 , 75 , 54 , 58 , 10 , 35 , 6 , 28 , 45 , 69 , 13 , 88 , 99 , 24 , 28 , 30 , 31 , 78 , 2 , 77 , 82 , 72 ];
console.log( '原始数据:' + dataStore );
console.log( '冒泡排序:' + bubbleSort( dataStore) );
// 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 冒泡排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99
2.选择排序(SelctionSort)
选择排序是⼀种⽐较简单直观的排序算法。它的算法思想是，从数组的开头开始遍历，将第⼀个元素和其他元素分别进⾏⽐较，记录最⼩的元素，等循环结束之后，将最⼩的元素放到数组的第⼀个位置上，然后从数组的第⼆个位置开始继续执⾏上述步骤。当进⾏到数组倒数第⼆个位置的时候，所有的数据就完成了排序。
选择排序同样会⽤到嵌套循环，外循环从数组第⼀个位置移到倒数第⼆个位置；内循环从第⼆个位置移动到数组最后⼀个位置，查⽐当前外循环所指向的元素还要⼩的元素，每次内循环结束后，都会将最⼩的值放到合适的位置上。
同样，我借⽤⽹上⼀张动图，来展⽰选择排序的过程 ：
选择排序
了解了算法思想，具体实现应该也不成问题：
//选择排序
function selectionSort( data ) {
for( var i = 0; i< data.length ; i++){
var min = data[i];
var temp;
var index = i;
for( var j = i + 1; j< data.length; j++){
if( data[j] < min ){
index = j;
}
}
temp = data[i];
data[i] = min;
data[index]= temp;
}
return data;
}
它的测试结果如下：
console.log( '原始数据:' + dataStore );
console.log( '选择排序:' + selectionSort( dataStore) );
// 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 选择排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99
3.插⼊排序(insertionSort)
插⼊排序有点类似⼈类按字母顺序对数据进⾏排序，就如同你打扑克牌⼀样，将摸来的扑克按⼤⼩放到合适的位置⼀样。它的原理就是通过嵌套循环，外循环将数组元素挨个移动，⽽内循环则对外循环中选中的元素及它后⾯的元素进⾏⽐较；如果外循环中选中的元素⽐内循环中选中的元素⼩，那么数组元素会向右移动，为内循环中的这个元素腾出位置。
实现步骤如下：
从第⼀个元素开始，该元素默认已经被排序
取出下⼀个元素，在已经排序的元素序列中从后向前扫描
如果该元素(已排序)⼤于新元素，将该元素移到下⼀位置
重复步骤3，直到到已排序的元素⼩于或者等于新元素的位置
将新元素插⼊到该位置
重复步骤2~5，直到排序完成
它的实现效果图如下：
插⼊排序
具体实现代码如下：
//插⼊排序
function insertionSort( data ) {
var len = data.length;
for (var i = 1; i < len; i++) {
var key = data[i];
js合并两个数组
while ( j >= 0 && data[j] > key) {
data[j + 1] = data[j];
j--;
}
data[j + 1] = key;
}
return data;
}
排序结果如下：
console.log( '原始数据:' + dataStore );
console.log( '插⼊排序:' + insertionSort( dataStore) );
/
/ 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 插⼊排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99
我们已经学习了三种基本的排序算法，其中冒泡排序是最慢的，插⼊排序是最快的，我们可以在运⾏的过程中通过
console.time('sortName') 和 console.timeEnd('sortName') 两个输出来看他们的效率如何，我这⾥给出⼀组值作为参考，实际中需要⼤量的数据测试和反复实验，进⾏数理统计后才能被视为有效的统计；
排序时间⽐较
⾼级排序算法
4.希尔排序(Shell Sort)
我们⾸先要学习的就是希尔排序，⼜称缩⼩增量排序，这个算法是在插⼊排序的基础上做了很⼤的改善，与插⼊排序不同的是，它⾸先会⽐较位置较远的元素，⽽⾮相邻的元素。这种⽅案可以使离正确位置很远的元素能够快速回到合适的位置，当算法进⾏遍历时，所有元素的间距会不断的减⼩，直到数据的末尾，此时⽐较的就是相邻元素了。
该⽅法的基本思想是：先将整个待排元素序列分割成若⼲个⼦序列(由相隔某个“增量”的元素组成的)分别进⾏直接插⼊排序，然后依次缩减增量再进⾏排序，待整个序列中的元素基本有序(增量⾜够⼩)时，再对全体元素进⾏⼀次直接插⼊排序。因为直接插⼊排序在元素基本有序的情况下(接近最好情况)，效率是很⾼的，因此希尔排序在时间效率上有较⼤提⾼。
好吧，我还是⽤个案例来解释，这样会更清晰，我们以下⾯⼀组数据为例：
数据集
第⼀次 gap(增量) = 10 / 2 = 5 , 会按照下⾯进⾏分组得到五组数据(49，13)、(38，27)、(65，49)、(97，55)、(26，4)，这样进⾏组内排序之后(13，49)、(27，38)、(49，65)、(55，97)、(4，26)
第⼀次分组
此时，数据会排成如下结构
第⼀次排序
第⼆次 gap = 5 / 2 = 2 , 此时可以得到两个分组，如下
第⼆次分组
再通过组内排序之后，可以得到
第⼆次排序
第三次 gap = 2 / 2 = 1 ， 即不⽤分组，进⾏排序后
第三次排序
第四次 gap = 1 / 2 = 0 ，即可得到排序完成的数组
排序完成
现在，可能对希尔排序有了⼀定得了解了，⽤JS实现如下：
//希尔排序
function shallSort(array) {
var increment = array.length;
var i
var temp; //暂存
do {
//设置增量
increment = Math.floor(increment / 3) + 1;
for (i = increment ; i < array.length; i++) {
if ( array[i] < array[i - increment]) {
temp = array[i];
for (var j = i - increment; j >= 0 && temp < array[j]; j -= increment) {
array[j + increment] = array[j];
}
array[j + increment] = temp;
}
}
}
while (increment > 1)
return array;
}
效果如下：
console.log( '原始数据:' + dataStore );
console.log( '希尔排序:' + shallSort( dataStore) );
// 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72 // 希尔排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。