冒泡排序
通過(guò)相鄰元素的比較和交換，使得每一趟循環(huán)都能找到未有序數(shù)組的最大值或最小值。
最好：O(n)，只需要冒泡一次數(shù)組就有序了。
最壞：O(n2)
平均：O(n2)
單向冒泡
function bubbleSort(nums) {
for(let i=0, len=nums.length; i<len-1; i++) {
// 如果一輪比較中沒(méi)有需要交換的數(shù)據(jù)，則說(shuō)明數(shù)組已經(jīng)有序。主要是對(duì)[5,1,2,3,4]之類的數(shù)組進(jìn)行優(yōu)化
let mark = true;
for(let j=0; j<len-i-1; j++) {
if(nums[j] > nums[j+1]) {
[nums[j], nums[j+1]] = [nums[j+1], nums[j]];
mark = false;
}
}
if(mark) return;
}
}
雙向冒泡
普通的冒泡排序在一趟循環(huán)中只能找出一個(gè)最大值或最小值，雙向冒泡則是多一輪循環(huán)既找出最大值也找出最小值。
function bubbleSort_twoWays(nums) {
let low = 0;
let high = nums.length - 1;
while(low < high) {
let mark = true;
// 找到最大值放到右邊
for(let i=low; i<high; i++) {
if(nums[i] > nums[i+1]) {
[nums[i], nums[i+1]] = [nums[i+1], nums[i]];
mark = false;
}
}
high--;
// 找到最小值放到左邊
for(let j=high; j>low; j--) {
if(nums[j] < nums[j-1]) {
[nums[j], nums[j-1]] = [nums[j-1], nums[j]];
mark = false;
}
}
low++;
if(mark) return;
}
}
選擇排序
和冒泡排序相似，區(qū)別在于選擇排序是將每一個(gè)元素和它后面的元素進(jìn)行比較和交換。
最好：O(n2)
最壞：O(n2)
平均：O(n2)
function selectSort(nums) {
for(let i=0, len=nums.length; i<len; i++) {
for(let j=i+1; j<len; j++) {
if(nums[i] > nums[j]) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
}
}
插入排序
以第一個(gè)元素作為有序數(shù)組，其后的元素通過(guò)在這個(gè)已有序的數(shù)組中找到合適的位置并插入。
最好：O(n)，原數(shù)組已經(jīng)是升序的。
最壞：O(n2)
平均：O(n2)
function insertSort(nums) {
for(let i=1, len=nums.length; i<len; i++) {
let temp = nums[i];
let j = i;
while(j >= 0 && temp < nums[j-1]) {
nums[j] = nums[j-1];
j--;
}
nums[j] = temp;
}
}
快速排序
選擇一個(gè)元素作為基數(shù)（通常是第一個(gè)元素），把比基數(shù)小的元素放到它左邊，比基數(shù)大的元素放到它右邊（相當(dāng)于二分），再不斷遞歸基數(shù)左右兩邊的序列。
最好：O(n * logn)，所有數(shù)均勻分布在基數(shù)的兩邊，此時(shí)的遞歸就是不斷地二分左右序列。
最壞：O(n2)，所有數(shù)都分布在基數(shù)的一邊，此時(shí)劃分左右序列就相當(dāng)于是插入排序。
平均：O(n * logn)
參考學(xué)習(xí)鏈接：
算法 3：最常用的排序——快速排序
三種快速排序以及快速排序的優(yōu)化
快速排序之填坑
從右邊向中間推進(jìn)的時(shí)候，遇到小于基數(shù)的數(shù)就賦給左邊（一開(kāi)始是基數(shù)的位置），右邊保留原先的值等之后被左邊的值填上。
function quickSort(nums) {
// 遞歸排序基數(shù)左右兩邊的序列
function recursive(arr, left, right) {
if(left >= right) return;
let index = partition(arr, left, right);
recursive(arr, left, index - 1);
recursive(arr, index + 1, right);
return arr;
}
// 將小于基數(shù)的數(shù)放到基數(shù)左邊，大于基數(shù)的數(shù)放到基數(shù)右邊，并返回基數(shù)的位置
function partition(arr, left, right) {
// 取第一個(gè)數(shù)為基數(shù)
let temp = arr[left];
while(left < right) {
while(left < right && arr[right] >= temp) right--;
arr[left] = arr[right];
while(left < right && arr[left] < temp) left++;
arr[right] = arr[left];
}
// 修改基數(shù)的位置
arr[left] = temp;
return left;
}
recursive(nums, 0, nums.length-1);
}
快速排序之交換
從左右兩邊向中間推進(jìn)的時(shí)候，遇到不符合的數(shù)就兩邊交換值。
function quickSort1(nums) {
function recursive(arr, left, right) {
if(left >= right) return;
let index = partition(arr, left, right);
recursive(arr, left, index - 1);
recursive(arr, index + 1, right);
return arr;
}
function partition(arr, left, right) {
let temp = arr[left];
let p = left + 1;
let q = right;
while(p <= q) {
while(p <= q && arr[p] < temp) p++;
while(p <= q && arr[q] > temp) q--;
if(p <= q) {
[arr[p], arr[q]] = [arr[q], arr[p]];
// 交換值后兩邊各向中間推進(jìn)一位
p++;
q--;
}
}
// 修改基數(shù)的位置
[arr[left], arr[q]] = [arr[q], arr[left]];
return q;
}
recursive(nums, 0, nums.length-1);
}
歸并排序
遞歸將數(shù)組分為兩個(gè)序列，有序合并這兩個(gè)序列。
最好：O(n * logn)
最壞：O(n * logn)
平均：O(n * logn)
參考學(xué)習(xí)鏈接：
圖解排序算法(四)之歸并排序
function mergeSort(nums) {
// 有序合并兩個(gè)數(shù)組
function merge(l1, r1, l2, r2) {
let arr = [];
let index = 0;
let i = l1, j = l2;
while(i <= r1 && j <= r2) {
arr[index++] = nums[i] < nums[j] ? nums[i++] : nums[j++];
}
while(i <= r1) arr[index++] = nums[i++];
while(j <= r2) arr[index++] = nums[j++];
// 將有序合并后的數(shù)組修改回原數(shù)組
for(let t=0; t<index; t++) {
nums[l1 + t] = arr[t];
}
}
// 遞歸將數(shù)組分為兩個(gè)序列
function recursive(left, right) {
if(left >= right) return;
// 比起(left+right)/2，更推薦下面這種寫(xiě)法，可以避免數(shù)溢出
let mid = parseInt((right - left) / 2) + left;
recursive(left, mid);
recursive(mid+1, right);
merge(left, mid, mid+1, right);
return nums;
}
recursive(0, nums.length-1);
}
桶排序
取 n 個(gè)桶，根據(jù)數(shù)組的最大值和最小值確認(rèn)每個(gè)桶存放的數(shù)的區(qū)間，將數(shù)組元素插入到相應(yīng)的桶里，最后再合并各個(gè)桶。
最好：O(n)，每個(gè)數(shù)都在分布在一個(gè)桶里，這樣就不用將數(shù)插入排序到桶里了(類似于計(jì)數(shù)排序以空間換時(shí)間)。
最壞：O(n2)，所有的數(shù)都分布在一個(gè)桶里。
平均：O(n + k)，k表示桶的個(gè)數(shù)。
參考學(xué)習(xí)鏈接：
拜托，面試別再問(wèn)我桶排序了?。?！
function bucketSort(nums) {
// 桶的個(gè)數(shù)，只要是正數(shù)即可
let num = 5;
let max = Math.max(...nums);
let min = Math.min(...nums);
// 計(jì)算每個(gè)桶存放的數(shù)值范圍，至少為1，
let range = Math.ceil((max - min) / num) || 1;
// 創(chuàng)建二維數(shù)組，第一維表示第幾個(gè)桶，第二維表示該桶里存放的數(shù)
let arr = Array.from(Array(num)).map(() => Array().fill(0));
nums.forEach(val => {
// 計(jì)算元素應(yīng)該分布在哪個(gè)桶
let index = parseInt((val - min) / range);
// 防止index越界，例如當(dāng)[5,1,1,2,0,0]時(shí)index會(huì)出現(xiàn)5
index = index >= num ? num - 1 : index;
let temp = arr[index];
// 插入排序，將元素有序插入到桶中
let j = temp.length - 1;
while(j >= 0 && val < temp[j]) {
temp[j+1] = temp[j];
j--;
}
temp[j+1] = val;
})
// 修改回原數(shù)組
let res = [].concat.apply([], arr);
nums.forEach((val, i) => {
nums[i] = res[i];
})
}
基數(shù)排序
使用十個(gè)桶 0-9，把每個(gè)數(shù)從低位到高位根據(jù)位數(shù)放到相應(yīng)的桶里，以此循環(huán)最大值的位數(shù)次。但只能排列正整數(shù)，因?yàn)橛龅截?fù)號(hào)和小數(shù)點(diǎn)無(wú)法進(jìn)行比較。
最好：O(n * k)，k表示最大值的位數(shù)。
最壞：O(n * k)
平均：O(n * k)
參考學(xué)習(xí)鏈接：
算法總結(jié)系列之五: 基數(shù)排序(Radix Sort)
function radixSort(nums) {
// 計(jì)算位數(shù)
function getDigits(n) {
let sum = 0;
while(n) {
sum++;
n = parseInt(n / 10);
}
return sum;
}
// 第一維表示位數(shù)即0-9，第二維表示里面存放的值
let arr = Array.from(Array(10)).map(() => Array());
let max = Math.max(...nums);
let maxDigits = getDigits(max);
for(let i=0, len=nums.length; i<len; i++) {
// 用0把每一個(gè)數(shù)都填充成相同的位數(shù)
nums[i] = (nums[i] + '').padStart(maxDigits, 0);
// 先根據(jù)個(gè)位數(shù)把每一個(gè)數(shù)放到相應(yīng)的桶里
let temp = nums[i][nums[i].length-1];
arr[temp].push(nums[i]);
}
// 循環(huán)判斷每個(gè)位數(shù)
for(let i=maxDigits-2; i>=0; i--) {
// 循環(huán)每一個(gè)桶
for(let j=0; j<=9; j++) {
let temp = arr[j]
let len = temp.length;
// 根據(jù)當(dāng)前的位數(shù)i把桶里的數(shù)放到相應(yīng)的桶里
while(len--) {
let str = temp[0];
temp.shift();
arr[str[i]].push(str);
}
}
}
// 修改回原數(shù)組
let res = [].concat.apply([], arr);
nums.forEach((val, index) => {
nums[index] = +res[index];
})
}
計(jì)數(shù)排序
以數(shù)組元素值為鍵，出現(xiàn)次數(shù)為值存進(jìn)一個(gè)臨時(shí)數(shù)組，最后再遍歷這個(gè)臨時(shí)數(shù)組還原回原數(shù)組。因?yàn)?JavaScript 的數(shù)組下標(biāo)是以字符串形式存儲(chǔ)的，所以計(jì)數(shù)排序可以用來(lái)排列負(fù)數(shù)，但不可以排列小數(shù)。
最好：O(n + k)，k是最大值和最小值的差。
最壞：O(n + k)
平均：O(n + k)
function countingSort(nums) {
let arr = [];
let max = Math.max(...nums);
let min = Math.min(...nums);
// 裝桶
for(let i=0, len=nums.length; i<len; i++) {
let temp = nums[i];
arr[temp] = arr[temp] + 1 || 1;
}
let index = 0;
// 還原原數(shù)組
for(let i=min; i<=max; i++) {
while(arr[i] > 0) {
nums[index++] = i;
arr[i]--;
}
}
}
計(jì)數(shù)排序優(yōu)化
把每一個(gè)數(shù)組元素都加上 min 的相反數(shù)，來(lái)避免特殊情況下的空間浪費(fèi)，通過(guò)這種優(yōu)化可以把所開(kāi)的空間大小從 max+1 降低為 max-min+1，max 和 min 分別為數(shù)組中的最大值和最小值。
比如數(shù)組 [103, 102, 101, 100]，普通的計(jì)數(shù)排序需要開(kāi)一個(gè)長(zhǎng)度為 104 的數(shù)組，而且前面 100 個(gè)值都是 undefined，使用該優(yōu)化方法后可以只開(kāi)一個(gè)長(zhǎng)度為 4 的數(shù)組。
function countingSort(nums) {
let arr = [];
let max = Math.max(...nums);
let min = Math.min(...nums);
// 加上最小值的相反數(shù)來(lái)縮小數(shù)組范圍
let add = -min;
for(let i=0, len=nums.length; i<len; i++) {
let temp = nums[i];
temp += add;
arr[temp] = arr[temp] + 1 || 1;
}
let index = 0;
for(let i=min; i<=max; i++) {
let temp = arr[i+add];
while(temp > 0) {
nums[index++] = i;
temp--;
}
}
}
堆排序
根據(jù)數(shù)組建立一個(gè)堆（類似完全二叉樹(shù)），每個(gè)結(jié)點(diǎn)的值都大于左右結(jié)點(diǎn)（最大堆，通常用于升序），或小于左右結(jié)點(diǎn)（最小堆，通常用于降序）。對(duì)于升序排序，先構(gòu)建最大堆后，交換堆頂元素（表示最大值）和堆底元素，每一次交換都能得到未有序序列的最大值。重新調(diào)整最大堆，再交換堆頂元素和堆底元素，重復(fù) n-1 次后就能得到一個(gè)升序的數(shù)組。
最好：O(n * logn)，logn是調(diào)整最大堆所花的時(shí)間。
最壞：O(n * logn)
平均：O(n * logn)
參考學(xué)習(xí)鏈接：
常見(jiàn)排序算法 - 堆排序 (Heap Sort)
圖解排序算法(三)之堆排序
function heapSort(nums) {
// 調(diào)整最大堆，使index的值大于左右節(jié)點(diǎn)
function adjustHeap(nums, index, size) {
// 交換后可能會(huì)破壞堆結(jié)構(gòu)，需要循環(huán)使得每一個(gè)父節(jié)點(diǎn)都大于左右結(jié)點(diǎn)
while(true) {
let max = index;
let left = index * 2 + 1; // 左節(jié)點(diǎn)
let right = index * 2 + 2; // 右節(jié)點(diǎn)
if(left < size && nums[max] < nums[left]) max = left;
if(right < size && nums[max] < nums[right]) max = right;
// 如果左右結(jié)點(diǎn)大于當(dāng)前的結(jié)點(diǎn)則交換，并再循環(huán)一遍判斷交換后的左右結(jié)點(diǎn)位置是否破壞了堆結(jié)構(gòu)（比左右結(jié)點(diǎn)小了）
if(index !== max) {
[nums[index], nums[max]] = [nums[max], nums[index]];
index = max;
}
else {
break;
}
}
}
// 建立最大堆
function buildHeap(nums) {
// 注意這里的頭節(jié)點(diǎn)是從0開(kāi)始的，所以最后一個(gè)非葉子結(jié)點(diǎn)是 parseInt(nums.length/2)-1
let start = parseInt(nums.length / 2) - 1;
let size = nums.length;
// 從最后一個(gè)非葉子結(jié)點(diǎn)開(kāi)始調(diào)整，直至堆頂。
for(let i=start; i>=0; i--) {
adjustHeap(nums, i, size);
}
}
buildHeap(nums);
// 循環(huán)n-1次，每次循環(huán)后交換堆頂元素和堆底元素并重新調(diào)整堆結(jié)構(gòu)
for(let i=nums.length-1; i>0; i--) {
[nums[i], nums[0]] = [nums[0], nums[i]];
adjustHeap(nums, 0, i);
}
}
希爾排序
通過(guò)某個(gè)增量 gap，將整個(gè)序列分給若干組，從后往前進(jìn)行組內(nèi)成員的比較和交換，隨后逐步縮小增量至 1。希爾排序類似于插入排序，只是一開(kāi)始向前移動(dòng)的步數(shù)從 1 變成了 gap。
最好：O(n * logn)，步長(zhǎng)不斷二分。
最壞：O(n * logn)
平均：O(n * logn)
參考學(xué)習(xí)鏈接：
圖解排序算法(二)之希爾排序
function shellSort(nums) {
let len = nums.length;
// 初始步數(shù)
let gap = parseInt(len / 2);
// 逐漸縮小步數(shù)
while(gap) {
// 從第gap個(gè)元素開(kāi)始遍歷
for(let i=gap; i<len; i++) {
// 逐步其和前面其他的組成員進(jìn)行比較和交換
for(let j=i-gap; j>=0; j-=gap) {
if(nums[j] > nums[j+gap]) {
[nums[j], nums[j+gap]] = [nums[j+gap], nums[j]];
}
else {
break;
}
}
}
gap = parseInt(gap / 2);
}
}
作者：前端一菜鳥(niǎo)
鏈接：http://www.itdecent.cn/p/a1f251c6709b
來(lái)源：簡(jiǎn)書(shū)
簡(jiǎn)書(shū)著作權(quán)歸作者所有，任何形式的轉(zhuǎn)載都請(qǐng)聯(lián)系作者獲得授權(quán)并注明出處。
