▓▓▓▓▓▓ 大致介绍
由于最近要考试复习，所以学习js的时间少了 -_-||，考试完还会继续的努力学习，这次用原生的JavaScript实现以前学习的常用的排序算法，有冒泡排序、快速排序、直接插入排序、希尔排序、直接选择排序
▓▓▓▓▓▓ 交换排序
交换排序是一类在排序过程中借助于交换操作来完成排序的方法，基本思想是两两比较排序记录的关键字，如果发现两个关键字逆序，则将两个记录位置互换，重复此过程，直到该排序列中所有关键字都有序为止，接下来介绍交换排序中常见的冒泡排序和快速排序
▓▓▓▓▓▓ 冒泡排序
冒泡排序的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名
冒泡排序算法的运作如下：（从后往前）
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序的时间复杂度是 O(n^2)
代码：
// 冒泡排序
function bubbleSort(arr){ for(var i=0;i<arr.length;i++){
for(var j=0;j<arr.length-i-1;j++){
if(arr[j] > arr[j+1]){
var arrMax = arr[j+1];
arr[j+1] = arr[j];
arr[j] = arrMax;
}
}
} return arr;
}
▓▓▓▓▓▓ 快速排序
// 快速排序
function quickSort(arr){
// 结束递归条件
if(arr.length <= 1){
return arr;
} var left = [];
var right = [];
var key = arr[0]; // 分组
for(var i=1;i<arr.length;i++){
if(arr[i] < key){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
} // 递归分组
return quickSort(left).concat(key,quickSort(right));
}
▓▓▓▓▓▓ 插入排序
插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排序的序列中的适当位置，直到全部记录插入完成为止，接下来介绍两种常用的插入排序方法：直接插入排序和希尔排序
▓▓▓▓▓▓ 直接插入排序
// 直接插入排序
function insertSort(arr){
// 默认第一个元素是有序的
for(var i=1;i<arr.length;i++){ if(arr[i] < arr[i-1]){
var guard = arr[i];
var j = i - 1;
// 将有序数组扩大一位
arr[i] = arr[j]; //遍历有序组，找到自己的位置
while(j >= 0 && guard < arr[j]){
arr[j+1] = arr[j];
j--;
} // 插入检查的元素
arr[j+1] = guard;
}
}
return arr;
}
▓▓▓▓▓▓ 希尔排序
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出 而得名。
// 希尔排序
function shellSort(arr){
var len = arr.length;
var stepLen = 1;
// 确定首次遍历的步长
while(stepLen < len/3){
stepLen = 3*stepLen + 1;
}
// 开始遍历
while(stepLen >= 1){
for(var i=stepLen;i<len;i++){
for(var j=i;j>=stepLen && arr[j] < arr[j-stepLen];j-=stepLen){
swap(arr,j,j-stepLen);
}
}
stepLen = (stepLen - 1)/3;
} return arr;
} function swap(arr,i,j){
var temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
▓▓▓▓▓▓ 选择排序
选择排序的基本思想是：每一趟排序在n-i+1个带排序记录中选出关键字最小的记录，作为有序序列的第i个记录，直到全部记录排序完毕。常用的排序方法有直接选择排序和堆排序(由于js不能很好的体现堆排序的特点就不写了)
▓▓▓▓▓▓ 直接选择排序
基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，....，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列
直接选择排序的时间复杂度：O(n^2)
代码：
// 直接选择排序
function straightSelectSort(arr){
// 默认第一个元素是最小的
var min;
var k;
var lArr = [];
for(var i=0;i<arr.length-1;i++){
min = arr[i];
k = i;
for(var j=i+1;j<arr.length;j++){
if(arr[j] < min){
min = arr[j];
k = j;
}
}
if(k != i){
arr[k] = arr[i];
arr[i] = min;
}
}
return arr;
}