JS排序算法全解析：冒泡、选择、插入、希尔、归并、快速排序实现

本文通过具体实例，深入讲解JavaScript中常见的排序（Sort）算法，供读者参考学习。

排序算法（Sort）

引言

在计算机存储数据的日常操作中，排序与查找是最基础且频繁的应用。自计算机诞生以来，针对这两项操作的研究从未停歇。在大数据与云计算盛行的今天，对数据排序和查找的速度及效率提出了更高要求。因此，设计专门的数据结构（如前文提到的二叉查找树）以优化数据操作，使其更加简洁高效，显得尤为重要。

本文将介绍多种数据排序的基本算法与高级算法，并使用JavaScript逐一实现。旨在帮助读者对计算机中常见排序算法的核心思想及具体实现建立基本认知，起到抛砖引玉的作用。

关于排序算法的说明

在深入介绍各个具体算法之前，有必要先了解评估算法优劣的一些关键术语：

稳定性：若两个元素a和b相等（a=b），且排序前a位于b之前，排序后a仍保持在b之前，则该算法是稳定的；反之，若排序后a可能出现在b之后，则为不稳定算法。

内排序：所有排序过程均在内存中完成。外排序：由于数据量过大，数据存储在磁盘中，排序过程需通过磁盘与内存之间的数据传输来完成。

时间复杂度：算法执行所耗费的时间。空间复杂度：运行程序所需的内存大小。

若希望深入了解时间复杂度与空间复杂度，推荐阅读相关文章：请戳这里

基本排序算法

基本排序算法的核心在于按照特定顺序重新排列一组数据。在重排过程中，通常会使用嵌套的for循环：外循环遍历数组中的每个元素，内循环则负责元素之间的比较。

1.冒泡排序（BubbleSort）

冒泡排序是经典且实现最简单的算法之一，但同时也是效率较低的排序算法。

冒泡排序的算法思想（以升序为例）如下：

比较相邻的两个元素，若第一个比第二个大，则交换它们的位置；
对每一对相邻元素重复上述操作，从第一对直到最后一对，这样最大的数会被交换到数组末尾；
除了最后一个元素外，对所有剩余元素重复上述步骤；
重复步骤1至3，直至整个排序过程完成。

以下借用一张网络动图来直观展示冒泡排序的执行过程：

排序算法（Sort）冒泡排序

具体的JavaScript实现代码如下：


//冒泡排序
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）

选择排序是一种简单直观的排序算法。其核心思想是从数组开头开始遍历，将第一个元素与其他元素逐一比较，记录最小值。循环结束后，将最小值放置到数组的第一个位置，随后从第二个位置开始重复上述步骤。当处理到数组倒数第二个位置时，所有数据即完成排序。

选择排序同样依赖嵌套循环：外循环从数组第一个位置移动至倒数第二个位置；内循环从第二个位置移动至数组最后一个位置，查找比外循环当前指向元素更小的值。每次内循环结束后，最小值会被放置在合适的位置。

以下借用一张网络动图来直观展示选择排序的执行过程：

排序算法（Sort）选择排序

理解算法思想后，具体实现便水到渠成：


//选择排序
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 ){
    min = data[j];
    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，直至排序完成。

其实现效果图如下：

排序算法（Sort）插入排序

具体实现代码如下：


//插入排序

function insertionSort( data ) {
 var len = data.length;
 for (var i = 1; i < len; i++) {
  var key = data[i];
  var j = i - 1;
  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') 两个输出来观察它们的效率差异。此处提供一组参考数值，实际应用中需进行大量数据测试与反复实验，经数理统计后方能视为有效统计结果；

排序算法（Sort）排序时间比较

高级排序算法

4.希尔排序（Shell Sort）

首先介绍的是希尔排序，又称缩小增量排序。该算法在插入排序的基础上进行了重大改进，与插入排序不同，它首先比较距离较远的元素，而非相邻元素。这种策略能使远离正确位置的元素快速回到合适位置。随着算法遍历进行，元素间的间距不断缩小，直至最后比较相邻元素。

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成）分别进行直接插入排序，然后依次缩减增量再进行排序。当整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。由于直接插入排序在元素基本有序的情况下（接近最好情况）效率极高，因此希尔排序在时间效率上有显著提升。

为更清晰地解释，以下通过一个案例进行说明，我们使用如下数据集为例：

排序算法（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）

排序算法（Sort）第一次分组

此时，数据会排成如下结构

排序算法（Sort）第一次排序

第二次 gap = 5 / 2 = 2，此时可以得到两个分组，如下

排序算法（Sort）第二次分组

再通过组内排序之后，可以得到

排序算法（Sort）第二次排序

第三次 gap = 2 / 2 = 1，即不用分组，进行排序后

排序算法（Sort）第三次排序

第四次 gap = 1 / 2 = 0，即可得到排序完成的数组

排序算法（Sort）排序完成

现在，可能对希尔排序有了一定了解，使用JavaScript实现如下：


//希尔排序

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

5.归并排序（Merge Sort）

将两个有序数列合并成一个有序数列，我们称之为“归并”。归并排序的思想是将一系列排序好的子序列合并成一个大的完整有序序列。

具体实现步骤如下：

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

以下通过一张动图来说明归并排序的过程：

排序算法（Sort）归并排序

具体的JavaScript代码实现如下：


//归并排序

function mergeSort ( array ) {
 var len = array.length;
 if( len < 2 ){
  return array;
 }
 var middle = Math.floor(len / 2),
  left = array.slice(0, middle),
  right = array.slice(middle);
 return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
 var result = [];
 while (left.length && right.length) {
  if (left[0] <= right[0]) {
   result.push(left.shift());
  } else {
   result.push(right.shift());
  }
 }
 while (left.length)
  result.push(left.shift());
 while (right.length)
  result.push(right.shift());
 return result;
}

测试结果如下：


console.log( '原始数据:' + dataStore );
console.log( '希尔排序:' + mergeSort( 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

6.快速排序（Quicksort）

快速排序是处理大数据最快的排序算法之一，它采用分而治之的策略，通过递归方式将数据依次分解为包含较小元素和较大元素的不同子序列，并不断重复此步骤，直到所有序列全部有序，最后将这些子序列依次拼接起来，即可得到排序好的数据。

该算法首先需从数列中选出一个元素作为基数（pivot）。接着所有数据都将围绕这个基数进行，将小于该基数的元素放在它的左边，大于或等于它的数全部放在它的右边，对左右两个小数列重复上述步骤，直至各区间只有1个数。

整个排序过程如下：

排序算法（Sort）快速排序

具体实现如下：


//快速排序

function quickSort( arr ){
 if ( arr.length == 0) {
  return [];
 }
 var left = [];
 var right = [];
 var pivot = arr[0];
 for (var i = 1; i < arr.length; i++) {
  if (arr[i] < pivot) {
   left.push( arr[i] );
  } else {
   right.push( arr[i] );
  }
 }
 return quickSort( left ).concat( pivot, quickSort( right ));
}

测试结果如下：


console.log( '原始数据:' + dataStore );
console.log( '快速排序:' + quickSort( 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

至此，我们已基本介绍了常见排序算法的思想及具体实现（基数排序在之前的文章已介绍过）。排序算法博大精深，我们不仅要学习理论，也要不断去实践，大家加油！

感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun测试上述代码运行效果。

PS：这里再为大家推荐一款关于排序的演示工具供大家参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具： http://tools.jb51.net/aideddesign/paixu_ys

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

JavaScript常见排序算法详解：从基础到高级实现

排序算法（Sort）

引言

关于排序算法的说明

基本排序算法

高级排序算法

实用工具推荐