JavaScript中的排序算法代码
2024-05-06 14:25:19
供稿：网友
作为排序依据的数据项称为“排序码”，也即数据元素的关键码。为了便于查找，通常希望计算机中的数据表是按关键码有序的。如有序表的折半查找，查找效率较高。还有，二叉排序树、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函数的实现和待排序元素的有序程度。因此，快速排序是一个不稳定的排序算法。
