# 冒泡排序

通过相邻元素比较和交换，使得每一趟循环都能找到未排序的子数组。

# 实现

function bubbleSort(list) {
  var n = list.length
  if(!n) return []
  
  for(var i = 0; i < n; i++) {
    for(var j = 0; j < n - i - 1; j++) {
      if(list[j] > list[j + 1]) {
        var temp = list[j + 1]
        list[j + 1] = list[j]
        list[j] = temp
      }
    }
  }
  return list
}

@前端进阶之旅: 代码已经复制到剪贴板

# 优化

# 单向冒泡

标记在一轮比较汇总中，如果没有需要交换的数据，说明数组已经是有序的，可以减少排序循环的次数。

function bubbleSort(list) {
  var n = list.length
  if(!n) return []
  
  for(var i = 0; i < n; i++) {
    let mark = true // 如果在一轮比较中没有出现需要交换的数据，说明数组已经是有序的
    for(let j = 0; j < n - i - 1; j++) {
      if(list[j] > list[j + 1]) {
        var temp = list[j + 1]
        list[j + 1] = list[j]
        list[j] = temp
        mark = false
      }
    }
    if(mark) break 
  }
  
  return list
}

@前端进阶之旅: 代码已经复制到剪贴板

# 双向冒泡

普通冒泡排序一轮只找到最大值或最小值其中之一，双向冒泡则多一轮筛选，既可以找到最大值，也可以找到最小值。

function bubbleSort(list) {
  var low = 0
  var high = list.length - 1
  while(low < high) {
    var mark = true
    // 找到最大值放在右边
    for(var i = low; i < high; i++) {
      if(list[i] > list[i + 1]) {
        var temp = list[i + 1]
        list[i + 1] = list[i]
        list[i] = temp
        mark = false
      }
    }
    high--
    // 找到最小值放在左边
    for(var j = high; j > low; j--) {
      if(list[j] < list[j - 1]) {
        var temp = list[j - 1]
        list[j - 1] = list[j]
        list[j] = temp
        mark = false
      }
    }
    low++
    if(mark) break
  }
  return list
}

@前端进阶之旅: 代码已经复制到剪贴板

# 选择排序

依次找到剩余元素的最小值或者最大值，放置末尾或者开头。

# 实现

function selectSort(list) {
  var n = list.length
  var minIndex
  
  for(var i = 0; i < n - 1; i++) {
    minIndex = i
    for(var j = i + 1; j < n; j++) {
      if(list[j] < list[minIndex]) {
        minIndex = j
      }
    }
    var temp = list[i]
		list[i] = list[minIndex]
    list[minIndex] = temp
  }
  return list
}

@前端进阶之旅: 代码已经复制到剪贴板

# 插入排序

以第一个元素为有序数组，其后的元素通过在这个已有序的数组中找到合适的元素并插入。

# 实现

function insertSort(list) {
  var n = list.length
  var preIndex
  var current
  
  for(var i = 1; i < n; i++) {
    preIndex = i - 1
    current = list[i]
    
    while(preIndex >=0 && list[preIndex] > current) {
      list[preIndex + 1] = list[preIndex]
      preIndex--
    }
    list[preIndex + 1] = current
  }
  return list
}

@前端进阶之旅: 代码已经复制到剪贴板

# 优化

# 拆半插入

function insertSort(list) {
  var low
  var high
  var j
  var temp
  for (var i = 1; i < list.length; i++) {
    if (list[i] < list[i - 1]) {
      temp = list[i]
      low = 0
      high = i - 1
      while (low <= high) {
        let mid = Math.floor((low + high) / 2)
        if (temp > list[mid]) {
          low = mid + 1
        } else {
          high = mid - 1
        }
      }
      for (j = i; j > low; --j) {
        list[j] = list[j - 1]
      }
      list[j] = temp
    }
  }
  return list
}

@前端进阶之旅: 代码已经复制到剪贴板

# 希尔排序

通过某个增量 gap，将整个序列分给若干组，从后往前进行组内成员的比较和交换，随后逐步缩小增量至 1。希尔排序类似于插入排序，只是一开始向前移动的步数从 1 变成了 gap。

function shellSort(list) {
  var n = list.length
  var gap = parseInt(n / 2) // 初始化步数
  while(gap) { // 逐步缩小步数
    for(var i = gap; i < n; i++) {
      // 逐步和前面其他成员比较交换
      for(var j = i - gap; j >=0; j -= gap) {
        if(list[j] > list[j + gap]) {
          var temp = list[j + gap]
          list[j + gap] = list[j]
          list[j] = temp
        } else {
          break
        }
      }
    }
    gap = parseInt(gap / 2)
  }
}

@前端进阶之旅: 代码已经复制到剪贴板

# 归并排序

递归将数组分成两个序列，有序合并这两个序列。作为一种典型的分治法思想算法应用，归并排序的实现有两种方法：

自上而下的递归

自下而上的迭代

function mergeSort(list) {
  var n = list.length
  if(n < 2) return list
  
  var mid = Math.floor(n / 2)
  var left = list.slice(0, mid)
  var right = list.slice(mid)
  
  return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
  var result = []
  while(left.length && right.length) {
    if(left[0] <= right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }
  while(left.length) {
    result.push(left.shift())
  }
  while(right.length) {
    result.push(right.shift())
  }
  return result
}

@前端进阶之旅: 代码已经复制到剪贴板

# 快速排序

选择一个元素作为基数，把比基数小的元素放在它左边，比它大的放在右边（相当于二分），再不断递归基数左右的序列。快速排序是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上递归分治法。快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，它是处理大数据最快的排序算法之一。

# 实现一

function quickSort(arr) {
  if (arr.length<=1){
    return arr;
  }
  var baseIndex = Math.floor(arr.length/2);//向下取整，选取基准点
  var base = arr.splice(baseIndex,1)[0];//取出基准点的值，
  // splice 通过删除或替换现有元素或者原地添加新的元素来修改数组,并以数组形式返回被修改的内容。此方法会改变原数组。
  // slice方法返回一个新的数组对象,不会更改原数组
  //这里不能直接base=arr[baseIndex],因为base代表的每次都删除的那个数
  var left=[];
  var right=[];
  for (var i = 0; i<arr.length; i++){
    // 这里的length是变化的，因为splice会改变原数组。
    if (arr[i] < base){
      left.push(arr[i]);//比基准点小的放在左边数组，
    }
  }else{
    right.push(arr[i]);//比基准点大的放在右边数组，
  }
  return quickSort(left).concat([base],quickSort(right));
}

@前端进阶之旅: 代码已经复制到剪贴板

# 实现二

function quickSort(list, left = 0, right = list.length - 1) {
  var n = list.length
	if(left < right) {
    var index = left - 1
    for(var i = left; i <= right; i++) {
      if(list[i] <= list[right]) {
        index++
        var temp = list[index]
        list[index] = list[i]
        list[i] = temp
      }
    }
    quickSort(list, left, index - 1)
    quickSort(list, index + 1, right)
  }
  
  return list
}

@前端进阶之旅: 代码已经复制到剪贴板

# 堆排序

说到堆排序，首先需要了解一种数据结构–堆。堆是一种完全二叉树，这种结构通常可以用数组表示。在实际应用中，堆又可以分为最小堆和最大堆，两者区别如下：

-max-heap property：对于所有除了根节点的节点i，A[Parent(i)] >= A[i]

-min-heap property：对于除了根节点的节点i，A[Parent(i)] <= A[i]

堆排序可以说是一种利用堆的概念来排序的选择排序，分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排序；

小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排序。

# 实现

# 计数排序

以数组元素值为键，出现次数为值存进一个临时数组，最后再遍历这个临时数组还原回原数组。因为 JS 的数组下标是以字符串形式存储的，所以计数排序可以用来排列负数，但是不可以排列小数。

# 冒泡排序

# 实现

# 优化

# 单向冒泡

# 双向冒泡

# 选择排序

# 实现

# 插入排序

# 实现

# 优化

# 拆半插入

# 希尔排序

# 归并排序

# 快速排序

# 实现一

# 实现二

# 堆排序

# 实现

# 计数排序

# 实现

# 桶排序

# 基数排序

前端高频面试题-精选篇-排序算法模块

前端高频面试题-精选篇-排序算法模块