在日常的開發(fā)中脚线，數(shù)據(jù)結(jié)構(gòu)中介紹的排序算法一直都是比較常用嚷狞，這里我們以js的形式再做一次總結(jié)绳姨，提高理解愈诚。
歸并排序
// 歸并排序(nlogn)
function mergeSort(arr, key){
/**
* @param {array} left 左側(cè)數(shù)組, 有序數(shù)組
* @param {array} right 右側(cè)數(shù)組, 有序數(shù)組
**/
var merge = function(left, right){
var final = [];
while(left.length && right.length){
// 左右因?yàn)槎际怯行驍?shù)組她按， 每次只比較第一位就可以了，選擇小的一位放進(jìn)新數(shù)組
final.push(left[0][key] < right[0][key] ? left.shift() : right.shift())
}
return final.concat(left.concat(right)) // 返回
}
var len = arr.length;
// 分割數(shù)組炕柔，直至數(shù)組長度為 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;
}
簡單選擇排序
// 選擇排序算法，遍歷所有數(shù)字汗唱， 將最小值和第一個(gè)沒有排序過的位置交換
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++){ // 假定第一個(gè)值為排好的
if(arr[i-1][key] > arr[i][key]){
let temp = arr[i], // 把應(yīng)往前放的值拿出來宫莱，準(zhǔn)備往前插
j;
for(j = i - 1; j >=0 && arr[j][key] > temp[key]; j--){
arr[j+1] = arr[j]; // 把前面所有小于temp的值位置往后移一位（始終會(huì)有一個(gè)空位子）
}
arr[j+1] = temp; // 把temp值放在這個(gè)空位置
}
}
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 { // 元素相同時(shí)，也插入在后面的位置
low = mid + 1;
}
}
for(var j = i - 1; j >= low; j--) {
arr[j + 1] = arr[j];
}
arr[low] = temp;
}
return arr;
}
Js內(nèi)置排序
// js 內(nèi)置的排序算法
function jsSortArray(arr, key) {
if (arr.length < 2) return arr;
arr.sort(function(a, b){
return a[key] - b[key];
})
return arr;
}
快速排序
//快速排序 取中間值哩罪，大于中間數(shù)的放在右邊授霸，小于中間數(shù)的放在左邊
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)是插入排序的一種。也稱縮小增量排序际插，是直接插入排序算法的一種更高效的改進(jìn)版本碘耳，利用了 '插排 在數(shù)組順序 接近 有序時(shí) 此 排序速度最快' 這個(gè)特性而產(chǎn)生的'
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;
};
