詳解JavaScript如何實現(xiàn)四種常用排序
一、插入排序
插入排序有直接插入排序，折半插入排序，希爾排序，這里只實現(xiàn)常用的直接插入排序
直接插入排序
將左側(cè)序列看成一個有序序列，每次將一個數(shù)字插入該有序序列。
插入時，從有序序列最右側(cè)開始比較，若比較的數(shù)較大，后移一位。
function insertSort(array) {
//第一個默認已經(jīng)排好
for (let i = 1; i < array.length; i++) {
let target = i;
for (let j = i - 1; j >= 0; j--) {
if (array[target] < array[j]) {
[array[target], array[j]] = [array[j], array[target]]
target = j;
} else {
break;
}
}
}
return array;
}
復(fù)雜度
時間復(fù)雜度：O(n2)
空間復(fù)雜度:O(1)
穩(wěn)定性
穩(wěn)定
二、交換排序
（1）冒泡排序
循環(huán)數(shù)組，比較當(dāng)前元素和上一個元素，如果當(dāng)前元素比上一個元素小，向下冒泡。
這樣一次循環(huán)之后最前一個數(shù)就是本數(shù)組最小的數(shù)。
下一次循環(huán)繼續(xù)上面的操作，不循環(huán)已經(jīng)排序好的數(shù)。
優(yōu)化：當(dāng)一次循環(huán)沒有發(fā)生冒泡，說明已經(jīng)排序完成，停止循環(huán)。
function bubbleSort(array) {
//第一個循環(huán)是所需次數(shù)
for (let j = 0; j < array.length; j++) {
let complete = true;
for (let i = array.length-1; i>j; i--) {
// 比較相鄰數(shù)
if (array[i] < array[i -1]) {
[array[i], array[i - 1]] = [array[i - 1], array[i]];
complete = false;
}
}
// 沒有冒泡結(jié)束循環(huán)
if (complete) {
break;
}
}
return array;
}復(fù)雜度
時間復(fù)雜度：O(n2)
空間復(fù)雜度:O(1)
穩(wěn)定性
穩(wěn)定
（2）快速排序
快速排序：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)比另一部分的所有數(shù)據(jù)要小，再按這種方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，使整個數(shù)據(jù)變成有序序列。
實現(xiàn)步驟：
- 選擇一個基準(zhǔn)元素target（一般選擇第一個數(shù)）
- 將比target小的元素移動到數(shù)組左邊，比target大的元素移動到數(shù)組右邊
- 分別對target左側(cè)和右側(cè)的元素進行快速排序
從上面的步驟中我們可以看出，快速排序也利用了分治的思想（將問題分解成一些小問題遞歸求解）
下面是對序列6、1、2、7、9、3、4、5、10、8排序的過程：
//JS自帶的sort()就是快排
function quickSort(array, start, end) {
if (end - start < 1) {
return;
}
const target = array[start];
let l = start;
let r = end;
while (l < r) {
while (l < r && array[r] >= target) {
r--;
}
array[l] = array[r];
while (l < r && array[l] < target) {
l++;
}
array[r] = array[l];
}
array[l] = target;
quickSort(array, start, l - 1);
quickSort(array, l + 1, end);
return array;
}復(fù)雜度
時間復(fù)雜度：平均O(nlogn)，最壞O(n2)，實際上大多數(shù)情況下小于O(nlogn)
空間復(fù)雜度:O(logn)（遞歸調(diào)用消耗）
穩(wěn)定性
不穩(wěn)定
三、選擇排序
（1）簡單選擇排序
每次循環(huán)選取一個最小的數(shù)字放到前面的有序序列中。
function selectionSort(array) {
for (let i = 0; i < array.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
[array[minIndex], array[i]] = [array[i], array[minIndex]];
}
}
復(fù)雜度
時間復(fù)雜度：O(n2)
空間復(fù)雜度:O(1)
穩(wěn)定性
不穩(wěn)定
（2）堆排序
創(chuàng)建一個大頂堆，大頂堆的堆頂一定是最大的元素。
交換第一個元素和最后一個元素，讓剩余的元素繼續(xù)調(diào)整為大頂堆。
從后往前以此和第一個元素交換并重新構(gòu)建，排序完成。
function heapSort(array) {
creatHeap(array);
console.log(array);
// 交換第一個和最后一個元素，然后重新調(diào)整大頂堆
for (let i = array.length - 1; i > 0; i--) {
[array[i], array[0]] = [array[0], array[i]];
adjust(array, 0, i);
}
return array;
}
// 構(gòu)建大頂堆，從第一個非葉子節(jié)點開始，進行下沉操作
function creatHeap(array) {
const len = array.length;
const start = parseInt(len / 2) - 1;
for (let i = start; i >= 0; i--) {
adjust(array, i, len);
}
}
// 將第target個元素進行下沉，孩子節(jié)點有比他大的就下沉
function adjust(array, target, len) {
for (let i = 2 * target + 1; i < len; i = 2 * i + 1) {
// 找到孩子節(jié)點中最大的
if (i + 1 < len && array[i + 1] > array[i]) {
i = i + 1;
}
// 下沉
if (array[i] > array[target]) {
[array[i], array[target]] = [array[target], array[i]]
target = i;
} else {
break;
}
}
}復(fù)雜度
時間復(fù)雜度：O(nlogn)
空間復(fù)雜度:O(1)
穩(wěn)定性
不穩(wěn)定
四、歸并排序
利用歸并的思想實現(xiàn)的排序方法。
該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。（分治法將問題分成一些小的問題然后遞歸求解，而治的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。
- 將已有序的子序列合并，得到完全有序的序列
- 即先使每個子序列有序，再使子序列段間有序
- 若將兩個有序表合并成一個有序表，稱為二路歸并
分割：
- 將數(shù)組從中點進行分割，分為左、右兩個數(shù)組
- 遞歸分割左、右數(shù)組，直到數(shù)組長度小于2
歸并：
如果需要合并，那么左右兩數(shù)組已經(jīng)有序了。
創(chuàng)建一個臨時存儲數(shù)組temp，比較兩數(shù)組第一個元素，將較小的元素加入臨時數(shù)組
若左右數(shù)組有一個為空，那么此時另一個數(shù)組一定大于temp中的所有元素，直接將其所有元素加入temp
function mergeSort(array) {
if (array.length < 2) {
return array;
}
const mid = Math.floor(array.length / 2);
const front = array.slice(0, mid);
const end = array.slice(mid);
return merge(mergeSort(front), mergeSort(end));
}
function merge(front, end) {
const temp = [];
while (front.length && end.length) {
if (front[0] < end[0]) {
temp.push(front.shift());
} else {
temp.push(end.shift());
}
}
while (front.length) {
temp.push(front.shift());
}
while (end.length) {
temp.push(end.shift());
}
return temp;
}做題時，上面多了刪除過程，特別大的例子，時間也可能會超，用下面的方法
function merge(left, right){
let leftLen = left.length, rightLen = right.length;
let i = 0, j = 0;
let temp = new Array(leftLen + rightLen);
for(let cur = 0; cur < leftLen + rightLen; cur++){
// 檢查i, j有沒有超界
if(i >= leftLen) temp[cur]= right[j++];
else if(j >= rightLen) temp[cur] = left[i++];
else if(left[i] <= right[j]){
temp[cur] = left[i++];
}else{
temp[cur] = right[j++];
}
}
return temp;
}復(fù)雜度
時間復(fù)雜度：O(nlogn)
空間復(fù)雜度:O(n)
穩(wěn)定性
穩(wěn)定
到此這篇關(guān)于詳解JavaScript如何實現(xiàn)四種常用排序的文章就介紹到這了,更多相關(guān)JavaScript排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了js微信掃描二維碼登錄網(wǎng)站技術(shù)原理,具有一定的參考價值，有需要的可以了解一下。2016-12-12
這篇文章主要介紹了JavaScript 動態(tài)加載腳本和樣式的方法,需要的朋友可以參考下2015-04-04
MATLAB中fillmissing函數(shù)用法小結(jié)
這篇文章主要介紹了MATLAB中fillmissing函數(shù)用法,本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-09-09
這篇文章主要介紹了JS判斷字符串字節(jié)數(shù)并截取長度的方法,涉及JavaScript針對頁面元素與字符串的動態(tài)操作技巧,需要的朋友可以參考下2016-03-03
這篇文章主要為大家詳細介紹了微信小程序使用前置攝像頭拍照，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-10-10
本文給大家分享的javascript常用腳本有把JavaScript中的偽數(shù)組轉(zhuǎn)換為真數(shù)組、JavaScript設(shè)置主頁功能、JavaScript收藏功能、javascript檢測元素是否支持某個屬性代碼、創(chuàng)建和使用命名空間，有需要的小伙伴們快來看看吧。2015-03-03
下面小編就為大家?guī)硪黄齽t表達式,替換所有HTML標(biāo)簽的簡單實例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-11-11
這篇文章主要介紹了JS變量提升及函數(shù)提升實例解析,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-09-09
這篇文章主要介紹了如何禁止iframe里面的腳本彈出的窗口覆蓋了父窗口,經(jīng)測試，貌似只能在IE下進行需要的朋友可以參考下2014-09-09
這篇文章主要為大家詳細介紹了JavaScript代碼實現(xiàn)簡單計算器，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-12-12