选择排序
基本思想
将待排序数组中最小的那个数放置于序列首位，之后将数组中的剩余元素中最小的取出放置于序列末尾，之后进行递归操作，直至待排序数组中没有元素。
算法实现
let selectsort = arr => {
if (arr.length <= 0) {return [];}
let min = Math.min.apply(null, arr);
let minindex = arr.indexOf(min);
arr.splice(minindex, 1);
return [min].concat(arr.length > 1 ? selectsort(arr):arr);
}
快速排序
基本思想
将原数组分为左和右两部分，进行一次排序确保其中一部分(左或右)中的所有数比另一部分中的都要小。之后继续对左右两部分进行递归，直到分片数组长度为1时退出递归，继续分组排序，直到所有递归完成时排序完成。
算法实现
let quicksort = (numbers, head, tail) => {
if (head >= tail || numbers === null || numbers ===undefined || numbers.length <= 1) {
return;
}
let i = head;
let j = tail;
let pivot = numbers[Math.floor((head + tail) / 2)];
while (i <= j) {
while (numbers[i] < pivot) {
++i;
}
while (numbers[j] > pivot) {
--j;
}
if (i < j) {
let swap = numbers[i];
numbers[i] = numbers[j];
numbers[j] = swap;
++i;
--j;
} else if (i == j) {
++i;
}
}
quicksort(numbers, head, j);
quicksort(numbers, i, tail);
return numbers;
}
阮一峰版本
可以通过新增空数组的方式，避免交换顺序。
let quickSort = arr => {
if (arr.length <= 1) { return arr; }
let pivotIndex = Math.floor(arr.length / 2);
let pivot = arr.splice(pivotIndex, 1)[0];
let left = [];
let right = [];
for (let 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) )
}
归并排序
基本思想
先将数组分解成大小为1的各个部分(不停地二等分直至大小为1)，然后从左至右依次进行排序将集合归并（从前至后依次比较要待归并的两个集合的首元素，将小的元素放入新队列并在待归并的集合中移除该元素）。
算法实现
let mergesort = arr => {
let n = arr.length;
if (n <= 1) { return arr }
let left = arr.slice(0, Math.floor(n / 2));
let right = arr.slice(Math.floor(n / 2));
return merge(mergesort(left), mergesort(right));
}
let merge = (a, b) => {
if (a.length <= 0) { return b; }
if (b.length <= 0) { return a; }
return a[0] > b [0] ? [b[0]].concat(merge(a,b.slice(1))) : [a[0]].concat(merge(b,a.slice(1)))
}
计数排序
基本原理
常用于一定范围内的数，用一个哈希表记录数组中元素的个数，记录完成后按从小到大的顺序遍历哈希表(需要最小值和最大值，可取0 至 max)，输出排序后的数组。
算法实现
let countsort = arr => {
let hashTable = {}, max = 0, result = []
for (let i = 0; i < arr.length; i++) {
arr[i] in hashTable ? hashTable[arr[i]] += 1 : hashTable[arr[i]] = 1;
if (arr[i] > max) { max = arr[i] }
}
//遍历hashTable，最小值为0，最大值为max
for (let i = 0; i <= max; i++) {
if (i in hashTable) {
while (hashTable[i]--> 0) {
result.push(i);
}
}
}
return result;
}
冒泡排序
基本思想
重复的遍历数组，比较连续的两个元素，如果顺序错误就交换，直到最后一次遍历中没有任何连续的两个元素需要交换，排序完成。
算法实现
暴力写法
let bubblesort = arr => {
let continuing = true;
while (continuing) {
continuing = false;
let swap;
for (let j = 0; j < arr.length-1; j++) {
if (arr[j] > arr[j + 1]) {
swap = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = swap;
continuing = true;
}
}
}
return arr;
}
优化写法
由于每次内层循环结束后，最大的数一定会被交换到最右边，所以第n-i次冒泡可以只执行i次运算（从右往左的n-i个元素必为从大到小，因此不参与冒泡）
let bubblesort = arr => {
for (let i = 0; i < arr.length-1;i++){
let swap;
for (let j = 0; j < arr.length-1-i; j++) {
if (arr[j] > arr[j + 1]) {
swap = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = swap;
}
}
}
return arr;
}
插入排序
基本思想
从数组第二个元素开始将当前元素与左侧的元素进行比较，并将当前元素插入合适的位置(对于左侧元素，从右至左依次冒泡)，直到插入原数组最后一个元素后排序完成。
算法实现
let inssort = arr => {
let n = arr.length - 1;
let swap;
for (let i = 1; i < n; i++) {
for (let j = i; j >= 0; j--){
if (arr[j] < arr[j-1]) {
swap = arr[j];
arr[j] = arr[j-1];
arr[j-1] = swap;
}
}
}
return arr;
}
希尔排序
基本思想
希尔排序通过将比较的全部元素按相同间隔(即gap:数组长度不断除以2(向下取整))分为几个区域，对于每个区域采用插入排序，每个区域排序完成后减少区域的个数(缩小区域的间隔直到为1)，由此来提升插入排序的性能。(例如，数组[1,2,3,4,5] 初始间隔为5/2 向下取整=2，第一次数组分为[1,3,5]和[2,4] 下一次的间隔为2/2 =1，数组分为[1,2,3,4,5])。
算法实现
let shellsort = arr => {
for (let gap = Math.floor(arr.length / 2); gap >= 1; gap = Math.floor(gap / 2)) {
for (let i = gap; i < arr.length; i++) {
let swap = arr[i];
let j;
for (j = i - gap; j >= 0 && arr[j] > swap; j -= gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = swap;
}
}
return arr;
}
基数排序
基本思想
将整数按位数切割成不同的数字(从个位至最大位数)，然后按每个位数分别比较。
- 例如数组[1,7,3,25,33]，先新建余数为0-9的10个数组buckets[0-9]，来存放对位数取余数为0-9的数；以及一个空数组来存放排序后的元素，将原数组全部放入buckets数组后，按余数从小到大依次放入新增的空数组(存放排序后的元素)。
- 第一次结果为个位数小的排在前面，变成[1,3,33,25,7]
- 第二次结果为十位数小的在前面,变成[1,3,7,25,33],因为最大位数为2，此时排序完成。
算法实现
let radixsort = arr => {
const max = Math.max.apply(null, arr);
let digit = `${max}`.length;
let buckets = [];
let start = 1;
while (digit > 0) {
start *= 10;
for (let i = 0; i < arr.length; i++) {
const index = arr[i] % start;
!buckets[index] && (buckets[index] = []);
buckets[index].push(arr[i]);
}
arr = [];
for (let i = 0; i < buckets.length; i++) {
buckets[i] && (arr = arr.concat(buckets[i]));
}
buckets = [];
digit--;
}
return arr;
}
