javascript之常用排序算法
PS: 最近在做练习的时候经常用到一些排序算法，记录下来，便于以后参考一、冒泡排序
具体算法描述如下：
[*]比较相邻的元素。如果第一个比第二个大，就交换它们两个；
[*]对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
[*]针对所有的元素重复以上的步骤，除了最后一个；
[*]重复步骤1~3，直到排序完成。
[*]代码实现
function BubbleSort(arr) {
var i = arr.length;
var exchange;
while (i > 0) {
for (j = 0; j < i - 1; j++) {
if (arr > arr) {
exchange = arr;
arr = arr;
arr = exchange;
}
}
i--;
}
return arr;
}
function bubbleSort3(arr3) {
var low = 0;
var high = arr.length - 1; //设置变量的初始值
var tmp, j;
console.time('2.改进后冒泡排序耗时');
while (low < high) {
for (j = low; j < high; ++j) //正向冒泡,找到最大者
if (arr > arr) {
tmp = arr;
arr = arr;
arr = tmp;
}
--high; //修改high值, 前移一位
for (j = high; j > low; --j) //反向冒泡,找到最小者
if (arr < arr) {
tmp = arr;
arr = arr;
arr = tmp;
}
++low; //修改low值,后移一位
}
console.timeEnd('2.改进后冒泡排序耗时');
r
时间复杂度：
[*]最佳情况：T(n) = O(n)
[*]最差情况：T(n) = O(n2)
[*]平均情况：T(n) = O(n2)
二、快速排序
具体算法描述如下：
[*]从数列中挑出一个元素，称为 "基准"（pivot）；
[*]重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
[*]递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
[*]代码实现
function quickSort(arr) {
if (arr.length == 0)
return [];
var left = new Array();
var right = new Array();
var flag = arr;
for (var i = 1; i < arr.length; i++) {
if (arr < flag) {
left.push(arr);
} else {
right.push(arr);
}
}
return quicksort(left).concat(flag, quicksort(right));
}
时间复杂度：
[*]最佳情况：T(n) = O(nlogn)
[*]最差情况：T(n) = O(n2)
[*]平均情况：T(n) = O(nlogn)
三、选择排序
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
function selectionSort(array) {
var len = array.length, temp;
for (var i = 0; i < len - 1; i++) {
var min = array;
for (var j = i + 1; j < len; j++) {
if (array < min) {
temp = min;
min = array;
array = temp;
}
}
array = min;
}
return array;
}
四、sort排序的应用
实现功能：根据对象数组中的某个属性排序。
例：
var data = [
["赵", 60],
["王", 50],
];
function sortAqiData(data) {
return data.sort(function(a, b) {
return a - b;
})
}
newData = sortAqiData(data);
五、filter矢代
功能： 根据数组对象中某个属性筛选数组。
例
var data= [["赵",60]["王",50]];
//选出年龄大于等于六十的人
data = data.filter(function(item) {
return item >= 60;
});
页:
[1]