前端排序算法

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

新老客户大回馈,云服务器低至5折

一.冒泡排序

原理:简单来说就是相邻两个元素进行对比,按照你需要的排序方式(升序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));
    }

时间复杂度:

  最佳情况:T(n) = O(nlogn)

  最差情况:T(n) = O(n2)

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

排序算法所有时间复杂度及空间复杂度,稳定性等:

 

掘金的这个文章写的很详细:https://juejin.im/post/57dcd394a22b9d00610c5ec8

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Web前端可以转行做游戏吗?

下一篇:Json与字符串互相转换