[TOC]

# 排序算法

# 1. 冒泡排序

算法描述：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。

function sort(arr) {
  var ar = []; var tmp;
  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp;
      }
    }
  }
  console.log(arr)
}
sort([3, 9, 2])

# 2. 快读排序

快速排序，又称划分交换排序。以分治法为策略实现的快速排序算法。

数组中指定一个元素作为标尺，比它大的放到该元素后面，比它小的放到该元素前面，然后在新的两边中重复上面的步骤。

快速排序分三步：

1. 选基准：在数据结构中选择一个元素作为基准(pivot)
2. 划分区：参照基准元素值的大小，划分无序区，所有小于基准元素的数据放入一个区间，所有大于基准元素的数据放入另一区间，分区操作结束后，基准元素所处的位置就是最终排序后它应该所处的位置
3. 递归：对初次划分出来的两个无序区间，递归调用第 1步和第 2步的算法，直到所有无序区间都只剩下一个元素为止。

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    // 找基准点
    var pivot = arr.splice(0, 1)[0];
    var left = [];
    var right = [];
		// 划分区域，小的在左边，大的在右边
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
  	// 递归调用，并拼接结果
    return quickSort(left).concat([pivot], quickSort(right));
}
var arr = [10, 2, 9, 20, 4, 1, 7, 15];
console.log(quickSort(arr));

66道前端算法面试题附思路分析助你查漏补缺

十大经典排序算法：

https://www.cnblogs.com/onepixel/articles/7674659.html

https://www.cnblogs.com/beli/p/6297741.html

https://www.cnblogs.com/liyongshuai/p/7197962.html