常见的排序算法（冒泡，选择，快排，插入，希尔）
分类和性能
1、稳定排序和非稳定排序
简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。
比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。
2、内排序和外排序
在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；
在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。
3、算法的时间复杂度和空间复杂度
所谓算法的时间复杂度，是指执行算法所需要的计算工作量。
一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。
1.冒泡排序
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换
最差时间复杂度为O(n^2),平均时间复杂度为O(n^2)。稳定性：稳定。辅助空间O(1)。
function sort(element) {
for (var i = 0; i < element.length; i++) {
for (var j = i + 1; j < element.length; j++) {
if (element[i] > element[j]) {
var tmp = element[i];
element[i] = element[j];
element[j] = tmp;
}
}
}
return element;
}2.选择排序
在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
最差、最优、平均时间复杂度都为O(n^2)。辅助空间为O(1)。稳定性：不稳定。
function selectSort(arr) {
var minIndex, tmp;
for (var i = 0; i < arr.length; i++) {
minIndex = i;
for (var j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
return arr;
}三.快速排序
快速排序的思想：
在数组中找到一个基准数（mid）
分区，将数组中比基准数大的放到它的右边，比基准数小的放到它的左边
继续对左右区间重复第二步，直到各个区间只有一个数，这时候，数组也就有序了。
最差时间复杂度：每次选取的基准元素都为最大（或最小元素）导致每次只划分了一个分区，需要进行n-1次划分才能结束递归，故复杂度为O(n^2)；最优时间复杂度：每次选取的基准元素都是中位数，于是每次都划分出两个分区，需要进行logn次递归，故时间复杂度为O(nlogn)；平均时间复杂度：O(nlogn)。稳定性：不稳定的。辅助空间：O(nlogn)。
function quickSort(arr) {
if (arr.length < 2) { return arr }
var left = [], right = [], mid = arr.splice(Math.floor(arr.length / 2), 1);
for (var i = 0; i < arr.length; i++) {
if (arr[i] < mid) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat(mid, quickSort(right));
}四.插入排序
（1） 从第一个元素开始，该元素可以认为已经被排序
（2） 取出下一个元素，在已经排序的元素序列中从后向前扫描
（3） 如果该元素（已排序）大于新元素，将该元素移到下一位置
（4） 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
（5）将新元素插入到下一位置中
（6） 重复步骤2
最坏时间复杂度为数组为逆序时，为O(n^2)。最优时间复杂度为数组正序时，为O(n)。平均时间复杂度为O(n^2)。辅助空间O(1)。稳定性：稳定。
function insertSort(arr) {
var tmp;
var len = arr.length;
for (var i = 1; i < len; i++) {
tmp = arr[i];
var j = i - 1;
while (j >= 0 && arr[j] > tmp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = tmp;
}
return arr;
}五.希尔排序
希尔排序本质上是一种插入排序，但是对数列进行了等间隔分组处理，在每一组中做插入排序，这一优化使得原本 O(n^2) 的时间复杂度一下降为 O(nlogn)。
希尔排序是按一定的间隔对数列进行分组，然后在每一个分组中做插入排序；随后逐次缩小间隔，在每一个分组中做插入排序...直到间隔等于1，做一次插入排序后结束。
那么问题来了，间隔应该取多大，怎么缩小？通常我们去取初始间隔为数列长度的一半：gap = length/2，以 gap = gap/2 的方式缩小，下面详细图解整个过程。
原始数组数组如下：
首先取间隔为 gap = length/2 = 4，将数组分为如下的4组，对每一组实施插入排序：
第一次排序，每一组较小的元素都移到了相对靠前的位置（这个状态可以叫 n-sorted，即以n为gap分组有序），可以想象相对有序的数组可能更有利于后面的排序。接着继续分组，gap = gap/2 = 2，对每一组实施插入排序：
继续对数组分组，gap = gap/2 = 1，即所有元素组成一组，做插入排序完成算法：
function shellSort(arr) {
var tmp;
for (var gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (var i = gap; i < arr.length; i++) {
var j = i;
tmp = arr[j];
while (gap >= 0 && tmp < arr[j - gap]) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = tmp;
}
}
return arr;
}总结：