JavaScript排序算法详解：冒泡、快速与桶排序实现

排序基础概念与分类

作为排序依据的数据项被称为“排序码”，即数据元素的关键码。为了便于后续查找，通常要求计算机中的数据表按关键码有序排列。例如，有序表的折半查找具有较高的效率。此外，二叉排序树、B-树和B+树的构建过程本质上也是一种排序过程。若关键码为主关键码，则任意待排序序列经排序后结果唯一；若为次关键码，排序结果可能不唯一，因为具有相同关键码的数据元素在排序结果中的相对位置可能与排序前不一致。

若对任意数据元素序列使用某排序方法按关键码排序，且相同关键码元素间的相对位置在排序前后保持一致，则称该排序方法是稳定的；反之，若不能保持这种一致性，则称为不稳定的。

排序过程主要分为两类：内排序和外排序。

内排序是指在排序过程中，待排序列完全存放在内存中进行的排序操作，适用于元素序列规模不太大的场景。

外排序是指排序过程中需要访问外部存储器。当元素序列足够大，无法完全放入内存时，必须使用外排序方法。

JavaScript排序算法实现

接下来展示三种排序算法的JavaScript具体实现。

首先是基础且直观的冒泡排序，其原理简单易懂，直接提供代码实现。

 
/** @name 冒泡排序
* @lastmodify 2010/07/13
* @desc 比较排序
复杂度为O(n*n)
*/ 
function BubbleSort(list){
var len = list.length;
var cl,temp;
while(len--){
cl = list.length;
while(cl--){
if(list[cl]>list[len] && cl < len){
temp = list[len];
list[len] = list[cl];
list[cl] = temp;
} 
} 
} 
return list;
} 

冒泡排序代码

接下来是最常见的快速排序，这也是面试中高频考察的内容。

 
/** @name 快速排序
* @lastmodify 2010/07/14
* @desc 比较排序
最差运行时间O(n*n);
最好运行时间O(nlogn)
*/ 
function QuickSort(list){
var i = 0;
var j = list.length;
var len = j;
var left;
var right;
var k = findK(i , j);
if(k != 0){
var leftArr = [];
var rightArr = [];
var midArr = [list[k]];
while(len--) {
if(len != k){
if(list[len] > list[k]){
rightArr.push(list[len]);
} 
else{
leftArr.push(list[len]);
} 
} 
} 
left = QuickSort(leftArr);
right = QuickSort(rightArr);
list = left.concat(midArr).concat(right);
} 
return list;
} 
function findK(i,j){
//默认找它的中间位置
return Math.floor((i + j) / 2);
} 

快速排序原理与代码

快速排序的核心思想是分治法，通过将待排序序列分割为两部分来降低排序复杂度。递归的运用是快速排序的精髓。在上述示例中，首先通过findK函数确定“参照元素”，其他元素依次与该元素比较，大于它的放入一个集合，小于它的放入另一个集合，然后分别对这两个集合进行排序。快速排序的效率主要取决于findK函数的实现方式以及待排序元素的初始有序程度。因此，快速排序属于不稳定的排序算法。

桶排序机制与代码

尽管快速排序基于比较，所有基于比较的排序算法在平均情况下，其排序时间随集合元素数量增加而增加。相比之下，非比较排序算法试图克服这一限制，使排序时间复杂度趋于与元素数量无关的稳定值。其中具有代表性的是桶排序，下面展示其JavaScript实现。

 
/** @name 桶排序
* @author lebron
* @lastmodify 2010/07/15
* @desc 非比较排序
*/ 
function BucketSort(list) {
var len = list.length;
var range = findMax(list);
var result = [],
count = [];
var i,j;
for (i = 0; i < range; i++) {
count.push(0);
} 
for ( j = 0; j < len; j++) {
count[list[j]]++;
result.push(0);
} 
for (i = 1; i < range; i++) {
count[i] = count[i-1] + count[i];
} 
for (j = len - 1; j >= 0; j--) {
result[count[list[j]]] = list[j];
count[list[j]]--;
} 
return result;
} 
function findMax(list) {
return MAX;
} 

从桶排序的实现可以看出，代码中使用了findMax函数来确定大数组的范围，此处直接用常量MAX代替。首先初始化长度为MAX的大数组count。将待排序集合中的值放入对应位置，例如元素值为24，则count的第24位标记为1，同时result数组长度加1。接着计算count数组中标志为1的元素在整个数组中的排位。此时count数组中第n个元素的值即为排序后该元素的位置，而n是该位置对应的值。最后，将count数组中的键值倒映射入结果数组即可。

桶排序巧妙利用了一种思想：如果一个元素在集合中是第n大的，它应排在第n位，无需关心其前后元素的大小关系（即无需比较）。然而，实际场景中待排序集合的值范围可能远大于元素数量，因此需要分配巨大的空间数组。正因如此，桶排序的常见应用场景是外排序。

有兴趣的同学可以测试这三种排序算法在不同数据量级下的耗时表现。