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 = [
    ["赵", 60],
    ["王", 50],
  ];
function sortAqiData(data) {
        return data.sort(function(a, b) {
            return a[1] - b[1];
        })
    }
newData = sortAqiData(data);

五、filter矢代

功能：根据数组对象中某个属性筛选数组。

例

  var data= [["赵",60]["王",50]];   
 
//选出年龄大于等于六十的人   
data = data.filter(function(item) {
            return item[1] >= 60;
      });

清风徐来，水波不兴