快速排序
非常有名的排序扣墩，顧名思義，快速排序突出一個快闰挡，方法：
1.選取數(shù)組中的一個元素作為【基準點】
2.比基準點大的举娩，換到基準點右邊析校，比它小的放到左邊
3.再對基準點兩邊的部分重復1、2铜涉，直到所有元素有序為止
/**
* 快速排序（遞歸法）
* Average Time Complexity: O(nlog2n)
* Stable: false
* @param origin
* @returns {Array}
*/
function quickSortRecursive (origin) {
function swap (arr,i,j) {
let t = arr[i]
arr[i] = arr[j]
arr[j] = t
}
let arr = [...origin]
partition(arr,0,arr.length-1)
function partition ( arr, start, end) {
if (start >= end) {
return
}
let mid = arr[end];
let left = start, right = end - 1
while (left < right) {
while (arr[left] < mid && left < right)
left++
while (arr[right] >= mid && left < right)
right--
swap(arr, left, right)
}
if (arr[left] >= arr[end]){
swap(arr, left, end)
} else {
left++
}
if (left) {
partition(arr, start, left - 1)
}
partition(arr, left + 1, end)
}
return arr
}
缺點：
1.分治法需要開辟大量的空間存放分割數(shù)組智玻，遞歸法限制于函數(shù)調用棧的最大空間
2.當數(shù)組基本有序或者數(shù)組為倒序時，效率非常低
冒泡排序
這個大概是最好理解的排序方法了芙代，從左往右起比對吊奢，如果后一個元素小于前一個，則交換兩者位置纹烹，每一趟都會把最大的元素排到最后
/**
* Average Time Complexity: O(n^2)
* Stable: true
* @param origin
* @returns { Array }
*/
function bubbleSort ( origin ) {
let arr = [...origin]
for ( let i = 0, len = arr.length; i < len; i++) {
for (let j = 0; j < arr.length-i-1; j++) {
if ( arr[j] > arr[j+1] ) {
[ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ]
}
}
}
return arr
}
選擇排序
從左往右起页滚，每趟從未排序的區(qū)間選擇最大/最小值換到左邊召边，排到上一趟排好的元素后面
/**
* Average Time Complexity:
* Stable: false
* @param origin
* @returns { Array }
*/
function selectSort ( origin ) {
let arr = [...origin];
let len = arr.length;
for (let i = 0; i < len; i++ ) {
let minIndex = i;
for ( let j = i+1; j < len; j++) {
if ( arr[j] < arr[minIndex] ) {
minIndex = j;
}
}
[ arr[i], arr[minIndex] ] = [ arr[minIndex], arr[i] ]
}
return arr
}
插入排序
我們平常打撲克整牌的時候非常類似于插入排序
從左往右起，每次選取一個元素插入左邊有序區(qū)間裹驰，如果該元素比前一個大且比后一個小隧熙，則插入這兩者之間
/**
* 直接插入排序
* Stable: true
* @param origin
* @returns { Array }
*/
function insertSort ( origin ) {
let arr = [...origin]
let len = arr.length;
for ( let i = 1; i < len; i++ ) {
let temp = arr[i];
let j = i - 1;
while ( j >= 0 && arr[j] > temp ) {
arr[j+1] = arr[j];
j--;
}
if ( j !== i - 1 ) {
arr[j+1] = temp;
}
}
return arr;
}
希爾排序
分治型的插入排序
1.定義增量（以折半增量為例），首先定義數(shù)組長度一半（向下取整）為增量 gap
2.從0開始邦马，每隔一個gap取數(shù)組下標贱鼻，形成新的分數(shù)組，以一個長度10的數(shù)組為例滋将，gap=5,將數(shù)組下標(不是元素本身)為 [0,5] [1,6] [2,7] [3,8] [4,9] 的元素組成5個分數(shù)組
3.對這些分數(shù)組進行插入排序
4.開始下一趟：將增量減半（向下取整），gap = 2症昏，則分成下標[0,2,4,6,8],[1,3,5,7,9]的分數(shù)組随闽，重復3，4直到gap為1為止
5.當gap為1時肝谭，直接進行最后的插入排序
/**
* 希爾排序
* @param origin
* Stable: false
*/
function shellSort ( origin ) {
let arr = [...origin]
let len = arr.length
for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (let i = gap; i < len; i++) {
for (let j = i - gap; j >= 0 && arr[j] > arr[gap + j]; j -= gap) {
let temp = arr[j];
arr[j] = arr[gap + j];
arr[gap + j] = temp;
}
}
}
}
堆排序
利用“堆”這個數(shù)據(jù)結構掘宪，構建最大/最小堆，再從堆中取走元素的排序法
/**
* Heapsort 最大堆排序
* @param origin
* @returns { Array }
*/
function maxHeapSort ( origin ) {
let arr = [...origin]
//交換數(shù)組元素
function swap(arr, i, j) {
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
//將元素與父節(jié)點比對并交換位置攘烛，滿足最大堆性質為止
function maxHeapify(start, end) {
let dad = start;
let son = dad * 2 + 1;
if (son >= end){
return;
}
if (son + 1 < end && arr[son] < arr[son + 1]){
son++;
}
if (arr[dad] <= arr[son]) {
swap(arr, dad, son);
maxHeapify(son, end);
}
}
let len = arr.length;
for (let i = Math.floor(len / 2) - 1; i >= 0; i--)
maxHeapify(i, len);
for (let i = len - 1; i > 0; i--) {
swap(arr,0, i);
maxHeapify(0, i);
}
return arr;
}
基數(shù)排序
本例使用LSD魏滚，即從低位到高位排序
從個位開始，將數(shù)字按當前位數(shù)裝入一個{0,1,2,3,4,5,6,7,8,9}的桶中坟漱，然后按桶的下標倒出鼠次，再進行下一位數(shù)的裝桶操作
如果存在如 24 110這樣位數(shù)不一樣的數(shù)，不足的數(shù)字需要在位數(shù)前補0
/**
* Radix Sort基數(shù)排序
* 從個位開始芋齿，將數(shù)字按當前位數(shù)排入一個{0,1,2,3,4,5,6,7,8,9}的桶中腥寇；
* @param origin 原數(shù)組
* @returns { Array } 輸出新數(shù)組
*/
function radixSort ( origin ) {
let arr = [...origin]
let digit = ( Math.max(...arr) + '').length
let bucket = {};
// 初始化桶
for ( let i = 0; i < 10; i++) {
bucket[i] = []
}
// 從各位到高位排序
for ( let bit = 1; bit < 10**digit; bit*=10) {
/**
* 將元素按照位數(shù)作為下標裝入桶中
* example 456:
* 第一輪 bit = 1 -> 456個位數(shù)6，將456裝進bucket[6]
* 第二輪 bit = 10 -> 456十位數(shù)5觅捆，將456裝進bucket[5]
*/
for (let i = 0, len = arr.length; i < len; i++) {
if ( arr[i]/bit < 1 ) {
bucket[0].push(arr[i])
} else {
//獲取當前位數(shù)的數(shù)字赦役，如當前位數(shù)100，則取這個數(shù)的百位數(shù)
let bitNum = Math.floor(arr[i]%(bit*10)/bit);
bucket[bitNum].push(arr[i])
}
}
arr = []; //清空數(shù)組
//將元素從桶內倒出來
for( let i in Object.keys(bucket) ) {
while( bucket[i].length ) {
arr.push( bucket[i].shift() )
}
}
}
return arr;
}
