首页 > > 网页制作 > Javascript >

前端排序算法

2018-06-24 01:42:33来源：未知阅读 ()

一.冒泡排序

原理：简单来说就是相邻两个元素进行对比，按照你需要的排序方式（升序or降序）进行位置替换，替换时需要额外一个变量当作中间变量去暂存值。

总结步骤：

1、外循环是遍历每个元素，每次都放置好一个元素；　　　

2、内循环是比较相邻的两个元素，把大/小的元素交换到后面；

3、等到第一步中循环好了以后也就说明全部元素排序好

function Bubble(arr) {
      for (let i = 0; i < arr.length; i++) {//遍历数组每一个（回合数）
        for (let j = 0; j < arr.length - 1 - i; j++) {//真正进行比较，例：i=0时比较第一次，进入第二层循环arr[0]与arr[1]进行比较，符合交换条件即交换，不符合继续比较
          if (arr[j] < arr[j + 1]) {
            let temp = arr[j + 1]//交换变量
            arr[j + 1] = arr[j]
            arr[j] = temp
          }
        }
      }
      return arr
}

时间复杂度：http://blog.csdn.net/itachi85/article/details/54882603

　　最好的情况：数组已经排好序（不用交换元素）-----> 时间花销为：[ n(n-1) ] / 2；所以最优的情况时间复杂度为：O( n^2 )

　　最差的情况：也就是开始的时候元素是逆序的，那么每一次排序都要交换两个元素，则时间花销为：[ 3n(n-1) ] / 2；（其中比上面最优的情况所花的时间就是在于交换元素的三个步骤）；所以最差的情况下时间复杂度为：O( n^2 )；

综上：

　　最优的时间复杂度为：O( n^2 ) ；//当使用标志位方法来判断你是否排好序时，时间复杂度为O(n)

最差的时间复杂度为：O( n^2 )；

平均的时间复杂度为：O( n^2 )；

加上flag的代码如下：

function bubbleSort2(arr) {var i = arr.length-1;  //初始时,最后位置保持不变
    while ( i> 0) {
        var flag= 0; //每趟开始时,无记录交换
        for (var j= 0; j< i; j++)
            if (arr[j]> arr[j+1]) {
                flag= j; //记录交换的位置,flag之后的均已交换成功
                var tmp = arr[j];
　　　　　　　　　 arr[j]=arr[j+1];
　　　　　　　　　 arr[j+1]=tmp;
            }
        i= flag; //为下一趟排序作准备，只要扫描到flag位置即可
     }return arr;
}

二：选择排序

原理：首先从原始数组中找到最小的元素，并把该元素放在数组的最前面，然后再从剩下的元素中寻找最小的元素，放在之前最小元素的后面，直到排序完毕

function Choose(arr) {
      let maxIndex, temp;
      for (let i = 0; i < arr.length - 1; i++) {
        maxIndex = i//maxIndex始终作为最大值的位置索引，
        for (let j = i + 1; j < arr.length; j++) {//当前最大值的后一位开始比较
          if (arr[j] > arr[maxIndex]) {//当后一位大于当前maxIndex
            maxIndex = j//将最大位置的索引值变为两者中较大的
          }
        }
        temp = arr[i]//当前轮次中的i与最大值进行交换，以达成最大值在前的的目的
        arr[i] = arr[maxIndex]
        arr[maxIndex] = temp
      }
      return arr
    }

时间复杂度：

平均时间复杂度：O(n*n)

　　最好情况：O(n*n)

　　最差情况：O(n*n)

三：插入排序

原理：一组数据分成两组，分别将其称为有序组与待插入组。每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。就这样，每次插入一个元素，有序组增加，待插入组减少。直到待插入组元素个数为0。

 function InsertionSort(array) {
      var length = array.length;
      for (var i = 0; i < length - 1; i++) {//i代表已经排序好的序列最后一项下标(第一项已排好序)
        var insert = array[i + 1];//insert为待插入组的第一项
        var index = i + 1;//记录要被插入的下标
        for (var j = i; j >= 0; j--) {
          if (insert > array[j]) //要插入的项比它小/大，往后移动
            array[j + 1] = array[j];
            index = j;
          }
        }
        array[index] = insert;
      }
      return array;
    }

时间复杂度：

平均时间复杂度：O(n*n)

　　最好情况：O(n)

　　最差情况：O(n*n)

四：希尔排序（属于插入排序的一种）

原理：利用步长来进行两两元素比较，然后缩减步长在进行排序。

　　复制了一个详细的说明：希尔排序的实质是分组插入排序，该方法又称缩小增量排序。该方法的基本思想是：先将整个待排元素序列分割为若干个子序列（由相隔某个‘增量’的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，带这个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况）效率是很高的，因此希尔排序在时间效率上有较大的提高。
希尔排序算法实现。

与插入排序的不同之处：它会优先比较距离较远的元素

function shellSort(arr) {
      let temp,
        gap = 1;
      while (gap < arr.length / 3) {
        gap = gap * 3 + 1//动态定义间隔序列
      }
      for (gap; gap > 0; gap = Math.floor(gap / 3)) {//控制步长（间隔）并不断缩小
        for (var i = gap; i < arr.length; i++) {//按照增量个数对序列进行排序
          temp = arr[i]
          for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {//例：j=0  arr[1]>arr[5]
            arr[j + gap] = arr[j]
          }
          arr[j + gap] = temp
        }
      }
      return arr
    }

时间复杂度：

　　最佳情况： O(nlog2 n)

　　最坏情况： O(nlog2 n)

　　平均情况： O(nlog n)

五：归并排序

原理：采用分治法，先划分，再合并

　步骤：

　1.先将C划分为两个数组A和B（即把数组C从中间分开）
　　2.再分别对数组A、B重复步骤1的操作，逐步划分，直到不能再划分为止(每个子数组只剩下一个元素)，这样，划分的过程就结束了。
　　如： [12 20 30 21 15 33 26 19 40 25]
　　划分为: [12 20 30 21 15] [33 26 19 40 25]
[12 20] [30 21 15] [33 26] [19 40 25]
[12] [20] [30] [21 15] [33] [26] [19] [40 25]
[12] [20] [30] [21] [15] [33] [26] [19] [40] [25]
　　3.然后从下层往上层不断合并数组，每一层合并相邻的两个子数组，合并的过程是每次从待合并的两个子数组中选取一个最小的元素，然后把这个元素放到合并后的数组中，不断重复直到把两个子数组的元素都放到合并后的数组为止。

　　4.依次类推，直到合并到最上层结束，这时数据的排序已经完成了。

 function mergeSort(arr) {
      if (arr.length < 2) {
        return arr;
      }
      //将数组分为左右两个子序列
      let middle = Math.floor(arr.length / 2)
      let left = arr.slice(0, middle)
      let right = arr.slice(middle)
      return merge(mergeSort(left), mergeSort(right))//对两个子序列重复划分为两个进行排序，直到不能划分
    }
    function merge(left, right) {
      let result = []
      while (left.length > 0 && right.length > 0) {
        if (left[0] < right[0]) {//两两比较，较小的放入结果数组
          result.push(left.shift())//shift()方法删除数组第一个元素，并返回被删除的元素
        } else {
          result.push(right.shift())
        }
      }
      /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */  
        return result.concat(left).concat(right);  
    }

时间复杂度：

　　最佳情况：T(n) = O(n)

　　最差情况：T(n) = O(nlogn)

　　平均情况：T(n) = O(nlogn)

六：快速排序

原理：选择一个基准，将比基准小的放左边，比基准小的放在右边（基准处在中间位置）

    function quickSort2(arr) {
      //如果数组<=1,则直接返回
      if (arr.length <= 1) { return arr; }
      var pivotIndex = Math.floor(arr.length / 2);
      //找基准，并把基准从原数组删除
      var pivot = arr.splice(pivotIndex, 1) [0];
      //定义左右数组
      var left = [];
      var right = [];

      //比基准小的放在left，比基准大的放在right
      for (var i = 0; i < arr.length; i++) {
        if (arr[i] <= pivot) {
          left.push(arr[i]);
        }
        else {
          right.push(arr[i]);
        }
      }
      //递归
      return quickSort2(left).concat([pivot], quickSort2(right));
    }