選擇排序
遞歸寫法
思路：每次找到最小的數(shù)放在前面佛点，然后后面的數(shù)做一樣的事情
let min = (numbers) => {
if (numbers.length > 2) {
return min([numbers[0], min(numbers.slice(1))]);
} else {
return Math.min.apply(null, numbers);
}
}; //求數(shù)組最小值
let minIndex = (numbers) => numbers.indexOf(min(numbers)); //拿到最小值的下標(biāo)
let sort = (numbers) => {
if (numbers.length > 2) {
let index = minIndex(numbers); //最小值下標(biāo)
let min = numbers[index]; //找到最小值
numbers.splice(index, 1); //把當(dāng)前最小值從數(shù)組沖剔除
return [min].concat(sort(numbers)); //遞歸：繼續(xù)排序剩余數(shù)組
} else {
return numbers[0] < numbers[1] ? numbers : numbers.reverse();
}
};
循環(huán)寫法
思路大致相同：先把最小值放在前面醇滥，后面執(zhí)行i++
let minIndex = (numbers) => {
let index = 0;
for (let i = 1; i < numbers.length; i++) {
if (numbers[i] < numbers[index]) {
index = i; //遍歷過程中每遇到一個比當(dāng)前數(shù)小的數(shù)就認(rèn)為是最小值，直到遍歷結(jié)束
}
}
return index;
};
let swap = (array, i, j) => {
let temp = array[i]; //把i放入容器temp
array[i] = array[j]; //j給i
array[j] = temp; //容器中的內(nèi)容i給j超营，實現(xiàn)交換
};
let sort = (numbers) => {
for (let i = 0; i < numbers.length - 1; i++) {
let index = minIndex(numbers.slice(i)) + i;
if (index != i) {
swap(numbers, index, i);
}
}
return numbers;
};
快速排序
思路：以某個數(shù)為基準(zhǔn)鸳玩，比它小的數(shù)放前面，比它大的數(shù)放后面演闭，對每個數(shù)都做這樣的操作實現(xiàn)排序
//快速排序 遞歸思路
let quickSort = (arr) => {
if (arr.length <= 1) {
return arr;
}
let pivotIndex = Math.floor(arr.length / 2); //設(shè)定基準(zhǔn)數(shù)的下標(biāo)
let pivot = arr.splice(pivotIndex, 1)[0]; //拿出基準(zhǔn)數(shù)不跟，因為會返回一個數(shù)組所以要標(biāo)注第零項
let left = []; //比標(biāo)準(zhǔn)數(shù)字小的數(shù)組
let right = []; //比標(biāo)準(zhǔn)數(shù)大的數(shù)組
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)); //實現(xiàn)排序
};
歸并算法
思路：不找基準(zhǔn)數(shù)，左邊一半排好序米碰，右邊一半排好序躬拢，最后左右兩邊進(jìn)行歸并。
let mergeSort = (arr) => {
if (arr.length === 1) {
return arr;
}
let left = arr.slice(0, Math.floor(arr.length / 2)); //左邊數(shù)組截取為0到數(shù)組的2分之1
let right = arr.slice(Math.floor(arr.length / 2)); //右邊數(shù)組截取為從2分之1開始
return merge(mergeSort(left), mergeSort(right)); //對左右兩部分繼續(xù)進(jìn)行mergeSort的操作后進(jìn)行歸并
};
let merge = (a, b) => {
if (a.length === 0) return b;
if (b.length === 0) return a; //特殊情況a或者b為空數(shù)組則直接返回另一半
return a[0] > b[0]
? [b[0]].concat(merge(a, b.slice(1)))
: [a[0]].concat(merge(a.slice(1), b)); //實現(xiàn)歸并排序
};
計數(shù)排序
思路：用一個哈希表做記錄见间，發(fā)現(xiàn)數(shù)字N就記N：1聊闯，如果再次發(fā)現(xiàn)N就加一
最后把哈希表的key都打出來
let countingSort = (arr) => {
let hashTable = {};
let result = [];
let max = 0;
for (let i = 0; i < arr.length; i++) {
//遍歷數(shù)組
if (!(arr[i] in hashTable)) {
hashTable[arr[i]] = 1; //把數(shù)組內(nèi)容寫進(jìn)來
} else {
hashTable[arr[i]] += 1;
}
if (arr[i] > max) {
max = arr[i]; //max會成為數(shù)組內(nèi)最大的
}
}
for (let n = 0; n <= max; n++) {
//遍歷哈希表
if (n in hashTable) {
for (let i = 0; i < hashTable[n]; i++) {
//再次遍歷,拿到哈希的value，實現(xiàn)多次輸出
result.push(n);
}
}
}
return result;
};
以上四種算法的時間復(fù)雜度
選擇排序 O(n^2)
快速排序 O(n log2 n)
歸并排序 O(n log2 n)
計數(shù)排序 O(n + max)
還有四種排序算法是：
冒泡排序
插入排序
希爾排序
基數(shù)排序
