文章序
排序算法作為算法的入門抱究，也是在日常開發(fā)中十分常用的铝条，故在此整理出十大排序算法，方便自己和需要的朋友查閱
先定義交換函數(shù)
//不使用額外空間交換算法,不能自己跟自己換
function swap(array, i, j) {
if (i === j) {
return array;
}
let arr = array;
arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
return arr;
}
//使用額外空間交換算法,可以自己跟自己換
function swap(array, i, j) {
let arr = array;
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
1冒泡排序
原理：數(shù)組長度為 n杉辙，遍歷 n - 1 趟模捂，每趟從第 1 個(gè)元素向后兩兩比較，如果左邊的元素大于右邊的元素則將兩個(gè)元素?fù)?jù)交換蜘矢，直到左邊的元素為第 n - 1 個(gè)元素狂男，交換完畢后，此時(shí)數(shù)組最右端的元素即為該數(shù)組中最大的元素品腹。接著對該數(shù)組剩下的 n-1 個(gè)元素繼續(xù)冒泡排序岖食，直到整個(gè)數(shù)組有序排列
特性：時(shí)間復(fù)雜度：O(n^2)，空間復(fù)雜度：O(1) 舞吭，穩(wěn)定排序 泡垃，原地排序
方法：兩層循環(huán)嵌套，外層共遍歷 n - 1 趟羡鸥，內(nèi)層遍歷從第 1 個(gè)元素到 n - 1 - i 個(gè)元素兔毙，進(jìn)行兩兩比較交換
function bubbleSort(arr) {
let res = arr;
let n = arr.length;
for(let i = 0; i < n - 1; i++) {
for(let j = 0; j < n - 1 - i; j++) {
if(res[j] > res[j + 1]) {
res = swap(res, j, j + 1);
}
}
}
return res;
}
2選擇排序
原理：遍歷 n - 1 趟，每趟遍歷找到剩余最小的元素放在前面兄春，依次類推，直到數(shù)組有序排列
特性：時(shí)間復(fù)雜度：O(n^2) 锡溯，空間復(fù)雜度：O(1) 赶舆，非穩(wěn)定排序，原地排序
方法：兩層循環(huán)嵌套祭饭，外層共遍歷 n - 1 趟芜茵，內(nèi)層遍歷從第 i 個(gè)元素開始，找到最小的元素和第 i 個(gè)元素交換
function selectionSort(arr) {
let res = arr;
let n = arr.length;
let minIndex = 0;
for(let i = 0; i < n - 1; i++) {
minIndex = i;
for(let j = i + 1; j < n; j++) {
if(res[j] < res[minIndex]) {
minIndex = j;
}
}
if(minIndex !== i) {
res = swap(res, i, minIndex);
}
}
return res;
}
3插入排序
原理：從第 1 個(gè)元素開始倡蝙，將后面的元素與該元素比較九串，大則放在右邊，小則放在左邊寺鸥，此時(shí)該兩元素構(gòu)成數(shù)組有序猪钮，剩余元素構(gòu)成的數(shù)組無序，依次將剩余的元素向前面已有序數(shù)組中插入胆建，直到整個(gè)數(shù)組有序
特性：時(shí)間復(fù)雜度：O(n^2)烤低，空間復(fù)雜度：O(1) ，穩(wěn)定排序 笆载，原地排序
方法：兩層循環(huán)嵌套扑馁，外層共遍歷 n - 1 趟代表插入 n - 1 個(gè)元素涯呻，內(nèi)層遍歷前面已有序數(shù)組直到找到合適的插入的元素的位置
function insertSort(arr) {
let res = arr;
let n = arr.length;
for (let i = 1; i < n; i++) {
for (let j = i - 1; j >= 0; j--) {
if (res[j] < res[j + 1]) {
break;
}
swap(res, j, j + 1);
}
}
return res;
}
4希爾排序
原理：定義增量(gap) h，將待排數(shù)組分割成為 h 個(gè)子數(shù)組分別進(jìn)行插入排序腻要，操作之后減小 h 的值复罐，再次分別進(jìn)行插入排序，直到 h = 1雄家，則再進(jìn)行最后一次插入排序效诅，完成后整個(gè)數(shù)組排序完成
特性：時(shí)間復(fù)雜度：O(nlogn) ，空間復(fù)雜度：O(1) 咳短，非穩(wěn)定排序填帽，原地排序
方法：三層遍歷，最外層每次減少增量h的值咙好，內(nèi)兩層做插入排序篡腌，注意間隔不再是 1 而是增量 h
function shellSort(arr) {
let res = arr;
let n = arr.length;
let h = parseInt(n / 2);
while (h >= 1) {
//進(jìn)行插入排序
let i = 0;
let temp = 0;
while(temp < h) {
for (let j = i - h; j >= 0; j = j - h) {
if (res[j] < res[j + h]) {
break;
}
swap(res, j, j + h);
}
i = i + h;
if(i >= n) {
temp++;
i = temp;
}
}
h = parseInt(h / 2);
}
return res;
}
5快速排序
原理：選擇一個(gè)元素，將比他大的都放到右側(cè)勾效，比它小的都放在左側(cè)嘹悼，此時(shí)數(shù)組分成兩個(gè)數(shù)組，再次對兩個(gè)數(shù)組進(jìn)行快排层宫，這樣遞歸下去直到整個(gè)數(shù)組有序
特性：時(shí)間復(fù)雜度：O(nlogn)杨伙，空間復(fù)雜度：O(nlogn) ，非穩(wěn)定排序萌腿，原地排序
方法：設(shè)指針 cur 指向第 1 個(gè)元素開始限匣，指針 i 從 cur 指向元素向右走，指針 j 從最后一個(gè)元素向前走毁菱，j 先走米死，當(dāng) j 找到比 cur 小的元素停止，當(dāng) i 找到比 cur 大的元素停止贮庞，交換 i j指向的元素峦筒，直到i j相遇，交換此時(shí)cur 和 i 指向元素的位置窗慎，對此時(shí)指針左右兩側(cè)數(shù)組遞歸進(jìn)行快排
function quickSort(arr) {
let n = arr.length;
handleSort(arr, 0, n - 1);
return arr;
}
const handleSort = (arr, start, end) => {
if (start >= end) {
return;
}
let cur = start,
i = start + 1,
j = end;
let mid = start;
while (true) {
while (j >= start && j > i) {
if (arr[j] < arr[cur]) {
break;
}
j--;
}
while (i <= end && i < j) {
if (arr[i] > arr[cur]) {
break;
}
i++;
}
if (i === j) {
if (arr[i] < arr[cur]) {
swap(arr, cur, i);
mid = i;
}
break;
}
swap(arr, i, j);
}
handleSort(arr, start, mid - 1);
handleSort(arr, mid + 1, end);
};
6歸并排序
原理：將數(shù)組除2拆分物喷，直到拆分到僅有一個(gè)元素的數(shù)組，此時(shí)該數(shù)組有序遮斥，將該數(shù)組與上一次拆分的另一個(gè)數(shù)組合并峦失，此時(shí)本次拆分的數(shù)組有序，繼續(xù)向上和上一次拆分的另一個(gè)數(shù)組合并伏伐，直到整個(gè)數(shù)組合并完畢宠进，整個(gè)數(shù)組有序
特性：時(shí)間復(fù)雜度：O(nlogn)，空間復(fù)雜度：O(n)藐翎，穩(wěn)定排序材蹬，非原地排序
方法：遞歸操作实幕，先定義拆分函數(shù)mergeSort，再定義合并函數(shù)merge堤器，拆分函數(shù)負(fù)責(zé)將入?yún)?shù)組除2拆分昆庇，并對拆分過的數(shù)組繼續(xù)調(diào)用拆分函數(shù)，當(dāng)兩次拆分函數(shù)都調(diào)用完畢返回結(jié)果則調(diào)用合并函數(shù)
function mergeSort(arr) {
let n = arr.length;
if (n < 2) {
return arr;
}
let mid = parseInt(n / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid, n);
let sortedLeft = mergeSort(left);
let sortedRight = mergeSort(right);
return merge(sortedLeft, sortedRight);
}
const merge = (left, right) => {
let res = [];
while (left.length > 0 && right.length > 0) {
if (left[0] < right[0]) {
res.push(left.shift());
} else {
res.push(right.shift());
}
}
if (left.length > 0) {
res = res.concat(left);
}
if (right.length > 0) {
res = res.concat(right);
}
return res;
};
7堆排序
原理：大頂堆為二叉樹數(shù)結(jié)構(gòu)闸溃，任意節(jié)點(diǎn)的值均大于左右子節(jié)點(diǎn)整吆，數(shù)組可以構(gòu)建一顆二叉樹結(jié)構(gòu)，將此數(shù)組調(diào)整為二叉樹符合大頂堆的順序辉川，再依次交換第 0 個(gè)元素和第 n 個(gè)元素表蝙，并重新調(diào)整堆使之符合大頂堆定義，n依次遞減直到n = 1乓旗，此時(shí)排序完成
特性：時(shí)間復(fù)雜度：O(nlogn)府蛇，空間復(fù)雜度：O(1)，非穩(wěn)定排序屿愚，原地排序
方法：parseInt(n / 2)該元素為最后一個(gè)非葉子節(jié)點(diǎn)的數(shù)據(jù)汇跨，從這里開始遍歷，構(gòu)建大頂堆妆距。大頂堆構(gòu)建完成后將第 0 個(gè)元素和最后一個(gè)元素交換穷遂，此時(shí)剩下的堆不符合大頂堆定義，調(diào)整堆使符合大頂堆定義娱据，再次交換第 0 個(gè)元素和此時(shí)最后一個(gè)元素蚪黑，循環(huán) n - 1 次結(jié)束獲得有序數(shù)組
function heapSort(arr) {
let n = arr.length;
//從最后一個(gè)非葉子節(jié)點(diǎn)開始遍歷，構(gòu)建大頂堆
for (let i = parseInt(n / 2); i >= 0; i--) {
heapify(arr, i, n);
}
//大頂堆構(gòu)建完畢中剩，開始從最后一個(gè)元素開始交換
for (let j = arr.length - 1; j > 0; j--) {
n--;
swap(arr, 0, j);
heapify(arr, 0, n);
}
return arr;
}
function heapify(arr, i, n) {
//調(diào)整堆
let leftChild = 2 * i + 1;
let rightChild = 2 * i + 2;
let largest = i;
if (leftChild < n && arr[leftChild] > arr[largest]) {
largest = leftChild;
}
if (rightChild < n && arr[rightChild] > arr[largest]) {
largest = rightChild;
}
if (largest !== i) {
swap(arr, i, largest);
heapify(arr, largest, n);
}
}
8計(jì)數(shù)排序
原理：開辟新的數(shù)組 newArray祠锣，長度為 k，將待排數(shù)組內(nèi)的元素值作為 newArray 的下標(biāo)咽安，將數(shù)組 newArray 從頭遍歷依次輸出賦值給原數(shù)組即完成排序
特性：時(shí)間復(fù)雜度：O(n + m)，空間復(fù)雜度：O(n + m)蓬推，穩(wěn)定排序妆棒，非原地排序
方法：
function countingSort(arr) {
let newArray = [];
let k = 0;
for (let i = 0; i < arr.length; i++) {
newArray[arr[i]] = arr[i];
}
for (let j = 0; j < newArray.length; j++) {
if (newArray[j]) {
arr[k] = newArray[j];
k++;
}
}
return arr;
}
9桶排序
原理：創(chuàng)建多個(gè)桶空間用來存放一定范圍內(nèi)的數(shù)據(jù)，每個(gè)桶內(nèi)再排序沸伏，將數(shù)據(jù)按順序從非空桶中取出糕珊，排序完成
特性：時(shí)間復(fù)雜度：O(n + m)，空間復(fù)雜度：O(n + m)毅糟，穩(wěn)定排序红选，非原地排序
方法：創(chuàng)建一個(gè)數(shù)組，該數(shù)組內(nèi)元素為數(shù)組表示不同的桶
function bucketSort(arr) {
let n = arr.length;
let max = arr[0];
let min = arr[0];
//找到最大最小值
arr.forEach(item => {
if (max < item) {
max = item;
} else if (min > item) {
min = item;
}
});
//設(shè)數(shù)組長度為桶長度姆另，獲取桶數(shù)量
let bucketCount = parseInt((max - min) / n);
let bucketList = new Array(bucketCount + 1);
for (let i = 0; i < bucketList.length; i++) {
bucketList[i] = [];
}
//將每一個(gè)數(shù)據(jù)放入到合適的桶
for (let j = 0; j < n; j++) {
let index = parseInt((arr[j] - min) / n);
bucketList[index].push(arr[j]);
}
//對每一個(gè)桶進(jìn)行排序喇肋，這里選擇計(jì)數(shù)排序
bucketList.forEach(bucket => {
countingSort(bucket);
});
for (let k = 0; k < bucketList.length; k++) {
if (k === 0) {
arr = [];
}
arr = arr.concat(bucketList[k]);
}
return arr;
}
10基數(shù)排序
原理：將數(shù)組按照從低位到高位的順序排序坟乾，當(dāng)每一趟都排序完成之后整個(gè)數(shù)組有序
特性：時(shí)間復(fù)雜度：O(nm)，空間復(fù)雜度：O(n + m)蝶防，穩(wěn)定排序甚侣，非原地排序
方法：先找到最大的數(shù)并獲取其位數(shù) n，然后從個(gè)位開始向上遍歷间学，共 n 次殷费，每次遍歷獲取該數(shù)當(dāng)前位的數(shù)并和桶里的數(shù)的當(dāng)前位的數(shù)比較，沒有當(dāng)前位則補(bǔ) 0
function radixSort(arr) {
let max = arr[0];
//找到最大的數(shù)并獲取其位數(shù)
arr.forEach(number => {
if (number > max) {
max = number;
}
});
const n = max.toString().length;
// let divide = Math.pow(10, n);
let divide = 1;
for (let i = 0; i < n; i++) {
let bucket = new Array(arr.length);
for (let j = 0; j < arr.length; j++) {
let tempNum = parseInt(arr[j] / divide);
while (tempNum >= 10) {
tempNum %= 10;
}
for (let k = 0; k < bucket.length; k++) {
if (bucket[k]) {
let tempBucketNum = parseInt(bucket[k] / divide);
while (tempBucketNum >= 10) {
tempBucketNum %= 10;
}
if (tempNum < tempBucketNum) {
bucket.splice(k, 0, arr[j]);
bucket.pop();
break;
}
} else {
bucket[k] = arr[j];
break;
}
}
}
divide *= 10;
arr = bucket;
}
return arr;
}
