前端算法篇

[liuyidi]

基础排序

冒泡排序

概念：越小的元素会经由交换慢慢“浮”到数列的顶端

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成

方案

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

var sort = (arr) => {
  var middle;
  for (var i = 0; i < arr.length - 1; i++) {
     for (var j = 0; j < arr.length - 1 - i; j++) {
         if (arr[j] > arr[j+1]) {
            middle = arr[j+1];  // 此处也可以使用ES6的解构赋值处理 [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
            arr[j+1] = arr[j];
            arr[j] = middle;
         }
     }
  } 	
  return arr
}

时间复杂度 O(n^2)

选择排序

var sort = (arr) => {
    var min;
    for (var i = 0; i < arr.length -1; i++) {
       min = i
       for (var j = i + 1; j < arr.length - 1; j++) {
           if (arr[min] > arr[j]) {
               min = j
           }
       }
       if (min != i) {
       	  var temp = arr[min]
          arr[min] = arr[i] 
          arr[i] = temp
       }
    }
    return arr
}

时间复杂度 O(n^2)

插入排序

快速排序

资料

• https://visualgo.net/zh