快速排序
非常有名的排序，顾名思义，快速排序突出一个快，方法：
1.选取数组中的一个元素作为【基准点】
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.分治法需要开辟大量的空间存放分割数组，递归法限制于函数调用栈的最大空间
2.当数组基本有序或者数组为倒序时，效率非常低
冒泡排序
这个大概是最好理解的排序方法了，从左往右起比对，如果后一个元素小于前一个，则交换两者位置，每一趟都会把最大的元素排到最后
/**
* 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
}
选择排序
从左往右起，每趟从未排序的区间选择最大/最小值换到左边，排到上一趟排好的元素后面
/**
* 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
}
插入排序
我们平常打扑克整牌的时候非常类似于插入排序
从左往右起，每次选取一个元素插入左边有序区间，如果该元素比前一个大且比后一个小，则插入这两者之间
/**
* 直接插入排序
* 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.定义增量（以折半增量为例），首先定义数组长度一半（向下取整）为增量 gap
2.从0开始，每隔一个gap取数组下标，形成新的分数组，以一个长度10的数组为例，gap=5,将数组下标(不是元素本身)为 [0,5] [1,6] [2,7] [3,8] [4,9] 的元素组成5个分数组
3.对这些分数组进行插入排序
4.开始下一趟：将增量减半（向下取整），gap = 2，则分成下标[0,2,4,6,8],[1,3,5,7,9]的分数组，重复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;
}
}
}
}
堆排序
利用“堆”这个数据结构，构建最大/最小堆，再从堆中取走元素的排序法
/**
* Heapsort 最大堆排序
* @param origin
* @returns { Array }
*/
function maxHeapSort ( origin ) {
let arr = [...origin]
//交换数组元素
function swap(arr, i, j) {
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
//将元素与父节点比对并交换位置，满足最大堆性质为止
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;
}
基数排序
本例使用LSD，即从低位到高位排序
从个位开始，将数字按当前位数装入一个{0,1,2,3,4,5,6,7,8,9}的桶中，然后按桶的下标倒出，再进行下一位数的装桶操作
如果存在如 24 110这样位数不一样的数，不足的数字需要在位数前补0
/**
* Radix Sort基数排序
* 从个位开始，将数字按当前位数排入一个{0,1,2,3,4,5,6,7,8,9}的桶中；
* @param origin 原数组
* @returns { Array } 输出新数组
*/
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) {
/**
* 将元素按照位数作为下标装入桶中
* example 456:
* 第一轮 bit = 1 -> 456个位数6，将456装进bucket[6]
* 第二轮 bit = 10 -> 456十位数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 {
//获取当前位数的数字，如当前位数100，则取这个数的百位数
let bitNum = Math.floor(arr[i]%(bit*10)/bit);
bucket[bitNum].push(arr[i])
}
}
arr = []; //清空数组
//将元素从桶内倒出来
for( let i in Object.keys(bucket) ) {
while( bucket[i].length ) {
arr.push( bucket[i].shift() )
}
}
}
return arr;
}
