冒泡排序
思想：每次遍历，相邻两个比较大小，修改位置
复杂度：n平方
function maopao(arr) {
for (var i = 0; i < arr.length; i++) {
for (var j = 0; j < arr.length; j++) {
if (arr[i] > arr[j]) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
选择排序
思想：一次便利结束后，找到最小的，放到最前面，交换次数较冒泡排序少
排序复杂度：n平方
function xuanze(arr) {
for (var i = 0; i < arr.length; i++) {
var min = i;
for (var j = 0; j < arr.length; j++) {
if (arr[j] <arr[i]) {
min = j;
}
}
if (min != i) {
var temp = arr[i];
arr[i] = arr[min];
arr[min] = arr[i];
}
}
}
插入排序
思想：每次往最小数组里插入一个数据，并保证数组是排序的
(1) 将这个序列的第一个元素R0视为一个有序序列；
(2) 依次把 , , … , 插入到这个有序序列中；
(3) 将插入到有序序列中时，前 i-1 个数是有序的，将和 ~ 从后往前进行比较，确定要插入的位置。
function insertSort(arr) {
var len = arr.length;
var preIndex,current;
for (var i = 1; i < len; i++) {
preIndex = i -1;
current = arr[i];
while(preIndex >=0 && arr[preIndex] > current) {
arr[preIndex +1] = arr[preIndex];
preIndex --;
}
arr[preIndex +1] = current;
}
}
希尔排序
4.希尔排序，希尔排序也是一种插入排序
不同：希尔排序优先比较较远的元素，希尔排序的核心在于间隔序列的设定
对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素
分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对
各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是
有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，
当gap=1时，整个数列就是有序的。
function shellSort(arr) {
var len = arr.length;
var temp,gap =1;
while(gap < len/3){
gap = gap *3 +1;
}
for (gap; gap> 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i - gap; j >0 && arr[j] > temp; j -= gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
归并排序
作为一种典型的分而治之思想的算法应用
将一个数组排序，可以先递归的将它分成两半分别排序，然后再将结果归并起来。
缺点：需要额外的空间
从下往上的归并排序：将待排序的数列分成若干个长度为1的子数列，然后将这
些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得
到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。
这样就得到了我们想要的排序结果
function mergeSort(arr) { //采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length>0 && right.length>0) {
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;
}
快速排序（Quick Sort）
分而治之思想在排序算法。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
先是把第一个挖出来，作为基值；然后先是从右向左，对比基值，如果如果小，那么放到坑里；然后在从左往右对比基值，如果大，那么放到坑里；当换完一轮了后，把基值放到坑里；然后在根据基值，分左右两组，递归排序；
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比
另外一部分的所有数据都要小，继续对长度较短的序列进行同样的分割，最后到
达整体有序。在排序过程中，由于已经分开的两部分的元素不需要进行比较，故
减少了比较次数，降低了排序时间。
function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}
function partition(arr, left ,right) { //分区操作
var pivot = left, //设定基准值（pivot）
index = pivot + 1;
for (var i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index-1;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
堆排序（Heap Sort）
堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大
值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将
剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执
行，便能得到一个有序序列了
var len; //因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
function buildMaxHeap(arr) { //建立大顶堆
len = arr.length;
for (var i = Math.floor(len/2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) { //堆调整
var left = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for (var i = arr.length-1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}