1、冒泡排序： 时间复杂度：O(n^2)，空间复杂度O(1)
function bubleSort(nums) {
let len = nums.length;
for(let i = 0; i < len; i++) {
for(j = 0; j < len-i-1; j++) {
if(nums[j] > nums[j+1]) {
let temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
return nums;
}
bubleSort([3, 44, 5, 47, 12,38, 15, 27, 26]);
2、选择排序： 时间复杂度：O(n^2)，空间复杂度O(1)
function selectSort(nums) {
let len = nums.length;
for(let i = 0; i< len; i++) {
minIdx = i;
for(let j = i+1; j < len; j++) {
if(nums[j] < nums[minIdx]) {
minIdx = j;
}
}
let temp = nums[i];
nums[i] = nums[minIdx];
nums[minIdx] = temp;
}
return nums;
}
3、插入排序，时间复杂度O(n^2)， 空间复杂度O(1)
function insertSort(nums) {
if(nums.length < 1) return;
for(let i = 1; i< nums.length; i++) {
if(nums[i] < nums[i-1]) {
let j = i-1;
let copy = nums[i];
// nums[i] = nums[i-1];
while(copy < nums[j]) {
nums[j+1] = nums[j];
j--;
}
nums[j+1] = copy;
}
}
return nums;
}
4、快速排序，时间复杂度：O (nlogn), 空间复杂度 O(log2n)
function quickSort(nums) {
const sort = (arr, left = 0, right = arr.length - 1) => {
if(left >= right) return; //说明整理完成
let i = left;
let j = right;
const baseVal = arr[j]; // 取最后一位为基准值
// 把所有比基准值小的数放在左边，大的数放在右边
while(i < j) {
while(i < j && arr[i] <= baseVal) { // 从前往后，找到比基准值大的数放右边
i++;
}
arr[j] = arr[i]; // 将较大的值放右边，如果没找到，则自己赋值给自己（i=j)
while(j > i && arr[j] >= baseVal) { // 从后往前，找到比基准值小的数放左边
j--;
}
arr[i] = arr[j]; // 将较小值放左边，如果没找到，则自己赋值给自己（i=j)
}
arr[i] = baseVal; // 此时i = j;
console.log(arr, '一轮循环后');
sort(arr, left, i-1);
sort(arr, i, right);
}
const newArr = nums.concat(); // 为了保证这个函数是纯函数拷贝一次数组
sort(newArr);
return newArr;
}
5、归并排序 时间复杂度：O (nlogn), 空间复杂度O(n)
// 递归调用
let count = 0; // 逆序对数量
function mergeSort(nums) {
if(nums.length === 1) return nums;
var mid = Math.floor(nums.length / 2),
left = nums.slice(0, mid),
right = nums.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var result = [];
while(left.length > 0 && right.length > 0) {
if(left[0] < right[0]) {
result.push(left.shift()); // 截取数组第一个
}else {
result.push(right.shift());
count += left.length; // 计算逆序对
}
}
return result.concat(left).concat(right); // concat-left和right的原因是，截取完后，左右两个数组总有一个还剩下
}
6、希尔排序 时间复杂度：O (nlogn), 空间复杂度O(1)
插入排序的优化版本，即缩小增量排序
function shellSort(array) {
let number = Math.floor(array.length / 2);
while(number >= 1) {
for(let i = number; i < array.length; i++) {
let temp = array[i];
let j = i - number;
while(j >= 0 && array[j] > temp) {
array[j + number] = array[j];
j -= number;
}
array[j + number] = temp;
}
number = Math.floor(number / 2);
}
return array;
}
7、计数数组 时间复杂度：O(n+m), 空间复杂度O(n+m)
局限性：
1、差值过大不适用（会造成空间浪费）
2、非整数不适用，如小数，无法创建统计数组
function countSort(array) {
if(array.legth < 2) return array;
let max = array[0],
min = array[0];
// 得到最大最小值
for(let i = 1; i < array.length; i++) {
if(array[i] > max) {
max = array[i];
}
if(array[i] < min) {
min = array[i];
}
}
let dis = max - min + 1; // 得到差值
let countArr = new Array(dis).fill(0);
// 统计原数组对应个数
for(let i = 0; i < array.length; i++) {
countArr[array[i] - min]++;
}
// 统计数组变形，后面元素等于前面元素之和
for(let i = 1; i < countArr.length; i++) {
countArr[i] += countArr[i-1];
}
// 倒序遍历原始数组，从统计数组找到正确数组，输出到结果数组
//倒序是因为统计的时候正序遍历原始数组， 统计数组中的序号值，应该对应的是原始数组中元素最后一次出现的位置。(类似栈的后进先出？)
let sortArr = new Array(array.length);
for(let i = array.length - 1; i >= 0; i--) {
let idx = array[i] - min; // 统计数组的下标（为啥不直接作为结果数组的下标是因为相同元素排序问题没办法确定先后）
let sortIdx = countArr[idx] - 1;
sortArr[sortIdx] = array[i];
//统计数组个数-1
countArr[idx]--;
}
return sortArr;
}
8、桶排序, 时间复杂度：O(n), 空间复杂度O(m)
计数排序是桶排序的一种特例的感觉
function bucketSort(array, bucketCount) {
if(array.length < 2) return array;
bucketCount = bucketCount || Math.floor(array.length / 4); // 桶数量
let max = array[0],
min = array[0];
for(let i = 1; i < array.length; i++) {
if(array[i] > max) {
max = array[i];
}
if(array[i] < min) {
min = array[i];
}
}
let bucketArr = new Array(bucketCount);
let diff = (max - min + 1) / bucketCount; // 桶之间的差值
// 将数据装入各个桶
for(let i = 0; i < array.length; i++) {
let idx = Math.floor((array[i] - min) / diff);
if(bucketArr[idx]) { // 桶非空
let buc_len = bucketArr[idx].length - 1;
while(buc_len >=0 && bucketArr[idx][buc_len] > array[i]) { // 插入排序
bucketArr[idx][buc_len + 1] = bucketArr[idx][buc_len];
buc_len--;
}
bucketArr[idx][buc_len + 1] = array[i];
} else {
bucketArr[idx] = [];
bucketArr[idx].push(array[i]);
}
}
let sortArr = [], n=0;
while(n < bucketCount) {
if(bucketArr[n]) { // 合并非空桶
sortArr = [...sortArr, ...bucketArr[n]]
}
n++;
}
return sortArr;
}
9、基数排序, 时间复杂度：O(k*N), 空间复杂度O(k + N)
function radixSort(arr) {
if(arr.length < 2) return arr;
let maxNum = Math.max(...arr); // 求最大值
let maxBit = maxNum.toString().length; // 最大值位数
let time = 1; //从末位开始
let bucketArr = new Array(10); // 0-9个桶
while( time <= maxBit ) {
// 置空桶
for(let i = 0; i < bucketArr.length; i++) {
bucketArr[i] = null;
}
// 按位数放入桶中
for(let i = 0; i < arr.length; i++) {
let idx = Math.floor(arr[i] / Math.pow(10, time - 1) % 10); // 桶序号
if(bucketArr[idx]) { // 桶非空
bucketArr[idx].push(arr[i]);
}else {
bucketArr[idx] = [arr[i]];
}
}
// 把桶内数据倒出
let newArrIdx = 0;
for(let i = 0; i < bucketArr.length; i++) {
if(bucketArr[i]) {
let j = 0;
while(j < bucketArr[i].length) {
arr[newArrIdx++] = bucketArr[i][j];
j++;
}
}
}
time++;
}
return arr;
}
基数排序：根据键值的每位数字来分配桶(0-9个桶)
桶排序： 每个桶存储一定范围的数值
计数排序： 每个桶只存储单一键值