# 前言
很多同学在前端面试中，手写代码已经是家常便饭。要求写一些常见的排序算法也是常常遇到，接下来将把几种常见的算法用 JavaScript 的方法实现。
# 快速排序
分治法的思想，寻找中间点，并对其左右的序列递归进行排序，直到左右都排序完成。
function quickSort(arr){
if(arr.length == 0) return arr;
let pirotIndex = Math.floor(arr.length/2),
pirot = arr.splice(pirotIndex, 1)[0],
left= [], right = [];
for(let i = 0; i < arr.length; i++){
arr[i] > pirot ? right.push(arr[i]) : left.push(arr[i]);
}
return quickSort(left).concat(pirot, quickSort(right))
}
# 插入排序
将数组分为 无序区 和 有序区 两个区，然后不断 将无序区 的第一个元素按大小顺序插入到 有序区 中去，最终将所有 无序区 元素都移动到 有序区完 成排序
function insertionSort(arr) {
var preIndex, current;
for (let i = 1; i < arr.length; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
# 冒泡排序
比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
function bubbleSort(arr){
if(arr.length==0) return arr
for(let i = 0; i < arr.length; i++){
for(let j = 0; j < arr.length-1; j++){
if(arr[j] > arr[j+1]){
[arr[j], arr[j+1]] = [arr[j+1], arr[j]] //ES6解构
}
}
}
return arr
}
# 选择排序
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
function selectionSort(arr) {
if (arr.length == 0) return arr
let minIndex;
for (let i = 0; i < arr.length; i++) {
minIndex = i;
for (let j = i; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}
return arr
}
# 归并排序
把数组分半，不断递归排序，最后进行已排序的数字进行合并。
function mergeSort(arr) {
if (arr.length < 2) return arr
let middle = Math.floor(arr.length / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
let 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
}
