插入排序二分插入排序希尔排序冒泡排序快速排序选择排序
1、插入排序
最普通的排序算法， 从数组下标1开始每增1项排序一次，越往后遍历次数越多
//插入排序
function sort(arr){
var copyArr = [...arr] // 复制一个复本出来
for(let i=1;i<copyArr.length;i++){
var prev = i - 1,temp = copyArr[i];
while(prev>=0 && temp<copyArr[prev]){
// 后 > 前，互换位置
[copyArr[prev+1],copyArr[prev] ] = [copyArr[prev],copyArr[prev+1]];
prev-- ;
}
}
return copyArr;
}
var list = [100,-5,10,0,0,-3,22,405,1,-3,96]
console.log(sort(list));
2、二分插入排序
插入排序的一种优化实现， 通过二分法减少遍历时间。
先在有序区通过二分查找的方法找到移动元素的起始位置， 然后通过这个起始位置将后面所有的元素后移
function
sort(arr
){
var result
= [...arr
],temp
,low
,high
,mid
;
for(let i
=1;i
<result
.length
;i
++){
temp
= result
[i
];
low
= 0;
high
= i
- 1;
while(low
<=high
){
mid
= Math
.ceil((low
+high
)/2)
if(result
[mid
]>temp
) high
= mid
- 1;
else low
= mid
+ 1;
}
for(let j
= i
- 1; j
>= high
+1; j
--){
result
[j
+1] = result
[j
];
}
result
[high
+1] = temp
;
}
return result
;
}
3、希尔排序
算法描述
先将整个待排序记录序列分割成若干个子序列，在序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。
编码
// 希尔排序：先将整个待排序记录序列分割成若干个子序列
// 在序列内分别进行直接插入排序，待整个序列基本有序时，
// 再对全体记录进行一次直接插入排序
function shellSort(arr){
var len = arr.length,
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++){ // 4--7
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;
}
var test = [1,10,-3,100,5,67,34];
var sortTest = shellSort(test);
console.log(sortTest);
4、冒泡排序（每次遍历相邻互换）
算法描述
(1)比较相邻的元素。如果第一个比第二个大，就交换它们两个； (2)第一层for循环的第一次遍历完，数组最后的元素应该会是最大的数；， 第一层for循环的第二次遍历完，数组倒数第二的元素应该会是第二大的数； … (3)直到第一层for循环彻底完成，则数组就将会是从小到大排列；
编码
function sort(arr){
for (var i = 1; i <arr.length; i++) { //
for (var j = 0; j <arr.length-i; j++) { // 注意这里在，最后i项已经是最大的，不需要再遍历
if(arr[j]>arr[j+1]){ //需要交换位置
// var temp=arr[j];
// arr[j]=arr[j+1];
// arr[j+1]=temp;
[arr[j+1], arr[j]] = [arr[j], arr[j+1]]
}
};
};
return arr.toString();
}
console.log(sort([23,45,18,37,92,13,24]));
5、快速排序(分区比较，直到每个区就一个)
算法描述
（1）先从数列中取出一个数作为“基准” （2）分区过程：将比这个“基准”大的数全放到“基准”的右边，小于或等于“基准”的数全放到“基准”的左边。 （3）再对左右区间重复第二步，直到各区间只有一个数。
编码
function quickSort(arr) {
if(arr.length<= 1) return arr;
var pivotIndex = Math.floor(arr.length / 2); //基准位置（理论上可任意选取）
var pivot = arr.splice(pivotIndex, 1)[0]; //基准数
var left = [];
var right = [];
for(var i = 0; i < arr.length; i++) {
if(arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right)); //链接左数组、基准数构成的数组、右数组
};
var test = [1,10,-3,100,5,67,34];
var sortTest = quickSort(test);
console.log(sortTest);
6、选择排序 (每次遍历选最值)
算法描述
（1）遍历未排序的区域，将最小值的下标暂定为当前遍历的下标i; （2）拿当前元素之后的元素与当前遍历的元素比较，若比其小，则修改最小下标。最终确定最小值所在的下标。 （3) 如果当前遍历的元素的下标与最小值的下标不一致，则互换位置 （4）重复第二步、第三步，直到所有元素均排序完毕。
编码
function selectSort(arr) {
const len = arr.length
for (let i = 0; i < len - 1; i++) { // 遍历未排序的区域
// 将最小值的下标暂定为i
let minIndex = i
// 依次与它右侧元素比较
for (let j = i+1; j < len; j++) {
if (arr[minIndex] > arr[j]) {
// 找到一个更小的值, 更新一下最小值的下标
minIndex = j
}
}
// 一旦minIndex有变化(发现最小值的下标不是i)
if (minIndex!==i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}
}
return arr
}
var test = [1,10,-3,100,5,67,34];
var sortTest = selectSort(test);
console.log(sortTest);
参考链接 快速排序：https://segmentfault.com/a/1190000009426421 选择排序：https://segmentfault.com/a/1190000009366805 希尔排序：https://segmentfault.com/a/1190000009461832 常见排序：https://www.cnblogs.com/wteam-xq/p/4752610.html
