零、写在最前
排序的方法有很多种，这篇文章只是记录我熟悉的算法；
我发现了一个关于排序算法很有趣的网站，把相关的算法演示做成了动画，有兴趣的同学可以看看！
附上SortAnimate网站链接：http://jun-lu.github.io/SortAnimate/index.html
一、冒泡排序
这是一种最基础的排序算法，也就是入门级别的算法！
原理：两两检测，比较两者之间的大小关系，大的往后丢！
function bubbleSort(arr){
for(var i=0;i<arr.length;i++){
for(var j=0;i<arr.length-i-1;i++){
if(arr[j]>arr[j+1]){
var temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
return arr;
}
二、快速排序
常用、排序速度快，但有点浪费内存空间！
原理：以中间基准点为中心进行比较，小的放左，大的放右，需要另外的2个数组存放；
function quickSort(arr){
if (arr.length <= 1) { return arr; }
var index=Math.floor(arr.length/2);
var center=arr.splice(index,1)[0];
var left=[],right=[];
for(var i=0;i<arr.length;i++){
arr[i]<center ? left.push(arr[i]) : right.push(arr[i]);
}
return quickSort(left).concat([center],quickSort(right));
}
三、插入排序
原理：逐个检测，最大的往最后丢，每次减少检测次数！
function insertSort(arr){
var arrLen=arr.length;
for(var i=0;i<arrLen;i++){
var index=0;
for(var j=1;j<arrLen-i;j++){
if(arr[j]>arr[index]) index=j;
}
var temp=arr[arrLen-i-1];
arr[arrLen-i-1]=arr[index];
arr[index]=temp;
}
return arr;
}
四、归并排序 （2019/03/14补充）
算法原理简单说就是拆分与合并的过程；
拆分：反复一拆为二，直到独立为一个为止 （中间有个递归的过程，数据量大会遭遇溢出）
合并：向上回溯，做到有序排列
代码如下：
(function () {
//例子：
let arr = [2,5,4,6,9,111,0,8,1];
function mergeFn(left, right) {
//合并
let tem = [];
while (left.length > 0 && right.length > 0) {
if (left[0] < right[0]) {
tem.push(left.shift());
} else {
tem.push(right.shift());
}
}
return tem.concat(left, right); //返回最终的数组结果
}
function slitFn(data) {
//拆分
let dataLen = data.length;
if (dataLen === 1) {
return data;
}
let midNum = Math.floor(dataLen / 2); //获取中间下标
let leftData = data.slice(0, midNum);
let rightData = data.slice(midNum);
return mergeFn(slitFn(leftData), slitFn(rightData));
}
console.log(slitFn(arr));
})()
PS：具体分析或者是数据溢出处理可以参考 韩子迟的博客
五、选择排序 （2019/5/13补充）
选择排序是一种简单直观的排序算法；
原理： 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置 ； 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾； 以此类推，直到所有元素均排序完毕。
function selectionSort (arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len-1; i++) {
minIndex = i;
for (var j = i+1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
temp = arr[minIndex]
arr[minIndex] = arr[i]
arr[i] = temp
}
return arr
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
selectionSort(arr)
六、结尾
排序算法还有 选择排序、希尔排序、二分排序等等.......
选择算法还需要考虑时间复杂度、稳定性、数据重复量多少；
我以后再学习，再来补充这篇文章！
-------------------- End ---------------------