在日常的开发中，数据结构中介绍的排序算法一直都是比较常用，这里我们以js的形式再做一次总结，提高理解。
归并排序
// 归并排序(nlogn)
function mergeSort(arr, key){
/**
* @param {array} left 左侧数组, 有序数组
* @param {array} right 右侧数组, 有序数组
**/
var merge = function(left, right){
var final = [];
while(left.length && right.length){
// 左右因为都是有序数组， 每次只比较第一位就可以了，选择小的一位放进新数组
final.push(left[0][key] < right[0][key] ? left.shift() : right.shift())
}
return final.concat(left.concat(right)) // 返回
}
var len = arr.length;
// 分割数组，直至数组长度为 1，则不再分割
if (len < 2) return arr;
var mid = len / 2;
return merge(mergeSort(arr.slice(0, parseInt(mid))), mergeSort(arr.slice(parseInt(mid))));
}
冒泡排序
// 冒泡排序
function bSort(arr){
for(var i = 0; i < arr.length - 1; i++){
var flag = false;
for(var j = arr.length; j > i; j--){
if(arr[i] > arr[j]){
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
flag = true;
}
}
if(flag === false){
return arr;
}
}
return arr;
}
简单选择排序
// 选择排序算法，遍历所有数字， 将最小值和第一个没有排序过的位置交换
function sortArray(arr, key) {
if (arr.length < 2) return arr;
for (var i = 0; i < arr.length - 1; i++){
for (var j = i + 1; j < arr.length; j++){
let temp;
if(arr[i][key] > arr[j][key]){
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
插入排序
// 插入排序(nlogn)
function insertSortArray(arr,key) {
if(arr.length < 2 ) return arr;
for(var i = 1; i < arr.length; i++){ // 假定第一个值为排好的
if(arr[i-1][key] > arr[i][key]){
let temp = arr[i], // 把应往前放的值拿出来，准备往前插
j;
for(j = i - 1; j >=0 && arr[j][key] > temp[key]; j--){
arr[j+1] = arr[j]; // 把前面所有小于temp的值位置往后移一位（始终会有一个空位子）
}
arr[j+1] = temp; // 把temp值放在这个空位置
}
}
return arr;
}
// 二分插入排序
function insertSort2(arr){
if(arr.length && arr.length < 2) return arr;
for(var i = 0; i < arr.length; i++){
var temp = arr[i];
var low = 0, high = i - 1;
var mid = -1;
while (low <= high) {
mid = Math.floor((high + low) / 2);
if (arr[mid] > temp) {
high = mid - 1;
} else { // 元素相同时，也插入在后面的位置
low = mid + 1;
}
}
for(var j = i - 1; j >= low; j--) {
arr[j + 1] = arr[j];
}
arr[low] = temp;
}
return arr;
}
Js内置排序
// js 内置的排序算法
function jsSortArray(arr, key) {
if (arr.length < 2) return arr;
arr.sort(function(a, b){
return a[key] - b[key];
})
return arr;
}
快速排序
//快速排序 取中间值，大于中间数的放在右边，小于中间数的放在左边
function quickSort(arr){
if(arr.length < 2) return arr;
var left =[] , right = [];
var mid = arr.splice(Math.floor(arr.length / 2), 1)[0];
for(var i =0; i < arr.length; i++){
arr[i] > mid ? right.push(arr[i]) : left.push(arr[i]);
}
return quickSort(left).concat(mid, quickSort(right))
}
function quickSort(array , start = 0, end = array.length -1) {
if (array.length < 2) return arr;
var partition = function(array, from, to) {
var position = from - 1;
var base = array[to];
for (var i = from; i < to; i++) {
if (array[i] <= base) {
position++;
var temp = array[position];
array[position] = array[i];
array[i] = temp;
}
}
var temp = array[position + 1];
array[position + 1] = array[to];
array[to] = temp;
return position + 1;
}
if (start < end) {
var position = partition(array, start, end);
quickSort(array, start, position - 1);
quickSort(array, position + 1, end);
}
}
希尔排序
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本，利用了 '插排 在数组顺序 接近 有序时 此 排序速度最快' 这个特性而产生的'
function shell_sort(arr) {
var len =arr.length;
gap = Math.floor(len/2);
while(gap!==0){
for(var i = gap; i < len; i++){
let temp = arr[i];
let j;
for(j = i -gap; j>=0 && temp < arr[j]; j = j -gap){
arr[i] = arr[j]
}
arr[j+gap] = temp
}
gap=Math.floor(gap/2);
}
return arr;
};
