首页 > 代码库 > javascript之常用排序算法
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[j] > arr[j + 1]) { exchange = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = 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[j] > arr[j + 1]) {
tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
--high; //修改high值, 前移一位
for (j = high; j > low; --j) //反向冒泡,找到最小者
if (arr[j] < arr[j - 1]) {
tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = 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[0]; for (var i = 1; i < arr.length; i++) { if (arr[i] < flag) { left.push(arr[i]); } else { right.push(arr[i]); } } 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[i];
for (var j = i + 1; j < len; j++) {
if (array[j] < min) {
temp = min;
min = array[j];
array[j] = temp;
}
}
array[i] = min;
}
return array;
}
四、sort排序的应用
实现功能：根据对象数组中的某个属性排序。
例：
var data = http://www.mamicode.com/["赵", 60],
["王", 50],
];
function sortAqiData(data) {
return data.sort(function(a, b) {
return a[1] - b[1];
})
}
newData = http://www.mamicode.com/sortAqiData(data);>
五、filter矢代
功能： 根据数组对象中某个属性筛选数组。
例
var data= http://www.mamicode.com/[["赵",60]["王",50]];
//选出年龄大于等于六十的人
data = http://www.mamicode.com/data.filter(function(item) {>
javascript之常用排序算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。