作为排序依据的数据项称为“排序码”，也即数据元素的关键码。为了便于查找，通常希望计算机中的数据表是按关键码有序的。如有序表的折半查找，查找效率较高。还有，二叉排序树、B-树和B+树的构造过程就是一个排序过程。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可能不唯一，这是因为具有相同关键码的数据元素，这些元素在排序结果中，它们之间的的位置关系与排序前不能保持。
若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。
排序分为两类：内排序和外排序。
内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。
外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。
现在贴3种排序算法的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);
}
快速排序的主要思想就是分治法，将被排序的序列分割为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来代替。首先初始化一个大数组count，长度为MAX。在将被排序集合里面的值放入到对应的位置上去，比如有一个元素值为24，那么count的第24位被标记为1，同时result数组长度+1。再计算出count数组中标志为1的元素位置在整个count数组中标志为1的排位。此时count数组中，第n个元素的值，就应当是排序后它的位置，而n这是这个排序后这个位置对应的值。所以，最后再一一的将count数组里面的键值倒过来映射入结果数组中即可。
桶排序巧妙的利用了这样一种思想，如果一个元素它在一个集合中是第n大的，那么它应该排第n位，而无需关心它前一位或者后一位是比它大还是比它小（无需比较）。很显然的是，在实际情况中，被排序集合的元素的值的范围很可能远远大于这个集合的元素数量，因此，也需要分配相应的一个巨大空间的数组才行。因此，桶排序的常见场景是在外排序上面。
有兴趣的同学，可以测试下3种排序在不同数量级下的耗时。
您可能感兴趣的文章: