Javascript ——算法

1. 冒泡排序。

冒泡排序是排序算法中最简单的算法。从运行时间角度上看，是最差的一个。
冒泡排序规则：不断比较相邻的两个元素，如果前者比后者大，则交换他们。元素向后移动至正确顺序。
代码实现：

var bubbleSort = function(arr) {
  // 外层循环多少个元素就需要遍历多少次
  for (var i=0; i<arr.length -1;i++) {

    // 内层循环，用于当前j元素与未排列的元素j+1 n+1每一个进行比对进行交换，注意内层循环每次都在减少，因为每比对一轮定能找个最大值向后排，它已不需要再进行比较，故是arr.length-1 -i, i就是第几轮
    for (var j = 0; j < arr.length - 1 -i; j++){

      // 相邻元素比较
      if (arr[j] > arr[j+1]) {
        // 交换元素
        var temp = arr[j+1]
        arr[j+1] = arr[j]
        arr[j] = temp

        /**
         * ES6可以使用,解构赋值
         * [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
         */
      }
    }
  }
  return arr
}
var arr = [3,1,5,9,2,4,6,8,7]
console.log(bubbleSort(arr)) // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

2. 选择排序。

选择排序是找最大值或最小值选择交互的过程
本例找最小值为例。 每一轮找到最小值往前排进行元素替换（最小值与第0、1..进行替换，已排列好的元素不再进行比较，每一轮都会找到一个往前依次放置，故需要比较的元素就是第i轮与后面那些元素进行比较）

找最小值选择
function selectionSort(arr) {
  var minIndex,
      len = arr.length

  // 轮数
  for (var i = 0; i < len; i++) {
    minIndex = i
    // 因为最小的数会往前面放，因为经过全轮排序的元素已经按准确顺序排在了前面，所以内循环就是从第i + 1个元素依次开始向后比较，排好的元素不用再排,
    for (var j = i + 1; j < len; j++) {

      // 比较小于找最小值，赋值索引
      if (arr[minIndex] > arr[j]) {
        minIndex = j // 记录索引
      }
    }

    // 不是当前索引就替换元素
    if (i !== minIndex) {
      var temp = arr[i]
          arr[i] = arr[minIndex]
          arr[minIndex] = temp
    }
  }
  return arr
}
var arr = [3,1,5,9,2,4,6,8,7]
console.log(selectionSort(arr)) // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

// 找最大值，往前排列
function selectSort(arr) {
  var len = arr.length
  // 轮数
  for (var i = 0; i < len; i++) {
    maxIndex = i
    // 因为最小的数会往前面放，因为经过全轮排序的元素已经按准确顺序排在了前面，所以内循环就是从第i个元素依次开始向后比较，排好的元素不用再排,
    for (var j = i + 1; j < len; j++) {

      // 比较小于找最小值，赋值索引
      if (arr[maxIndex] < arr[j]) {
        maxIndex = j // 记录索引
      }
    }

    // 不是当前索引就替换元素
    if (i !== maxIndex) {
      var temp = arr[i]
      arr[i] = arr[maxIndex]
      arr[maxIndex] = temp
    }
  }
  return arr
}

3. 插入排序。

插入排序。从第二个元素开始，不断的跟前面排好序的元素进行比较大小交换插入，直到最后一个元素

function insertSort (arr) {
  var len = arr.length

  // 从第二项开始（索引1）跟前面比较
  for (var i = 1; i < len; i++) {

    // 不断的比较前面排好序的元素进行交换，直到最后一个元素
    for (var j = 0; j < i; j++){  // 所以内存循环是到i,也就是跟前面已排好序的那些元素进行比较
      if (arr[j] > arr[i]) {
        var temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
      }
    }
  }
  return arr
}
var arr = [3,1,5,9,2,4,6,8,7]
console.log(insertSort(arr)) // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

4. 快速排序

function quikSort(arr, left, right) {
  var index;
  if (arr.length > 1) {
    index = partition(arr, left, right)
    if (left < index - 1) {
      quikSort(arr, left, index - 1)
    }
    if (index < right) {
      quikSort(arr, index, right)
    }
  }
}

// 分治法
function partition(arr, left, right) {
  var pivot = arr[Math.floor((left + right) / 2)],
    i = left,
    j = right;

  // 左边未超过右边索引
  while(i <= j) {

    // 与中间元素比较
    while (arr[i] < pivot) {   // 找到大元素，停止循环
      i ++   // 目的是左指针索引往中间靠拢
    }
    while (arr[j] > pivot) { // 找到小元素停止循环
      j -- // 目的是右指针索引往中间靠拢
    }

    // 指针小于或相等，未过线，就交互元素； 根据小在左，大在有的原则
    if (i <= j) {
      var aux = arr[i];
      arr[i] = arr[j];
      arr[j] = aux;
      
    // 交换完后继续执行
      i++
      j--
    }
  }
  return i  // 此时的它就是中间元素，因为已对左右两边进行了正确的交换
}
quikSort(a, 0, a.length - 1)
var arr = [3,1,5,9,2,4,6,8,7]
console.log(a)