作為一個有追求的前端,忙裡偷閑(閑得發慌)地複習了一下基礎的排序算法,以此文留念.
本篇主要記錄O(n²)複雜度的基礎算法O(nlogn)的算法将在下次有空(閑得發慌)時更新
在記錄時發現Es6文法中的解構指派與傳統的中間變量交換相比效率低下,經過幾次測試發現其耗時大約為交換中間變量的兩倍
1.冒泡排序
衆所周知排序最基礎的算法,也就是大名鼎鼎的冒泡了,為了友善日後回顧還是簡單提一下冒泡的原理:
其核心思想在于不停地比較相鄰元素的大小關系,如果前面的比後面的大則兩個元素互換位置(此處以順序為例);每當一次大的循環後總能将目前剩餘數中最大的數交換到數組的末尾,類似于一個泡泡從底部浮出水面,故得名冒泡算法.下方代碼為未使用任何優化的原始冒泡算法.
其時間複雜度為O(n²) 不需要額外空間;
1 //冒泡排序
2 function BubbleSort(arr) {//arr即需要排序的數組;本文後續中的arr均為此意
3 console.time('timer');//用于統計代碼執行時間
4 for (let i = 0; i < arr.length; i++) {
5 for (let j = 0; j < arr.length; j++) {
6 if (arr[j] > arr[j + 1])
7 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];//交換元素(解構指派ES6)
8 }
9 }
10 console.timeEnd('timer');
11 } 以一萬個數構成的倒序(從大到小)數組變為順序的時間如下圖(與個人電腦及其它因素有關請勿較真)用解構指派交換:
後續算法的時間均以同一數組測試
2.雞尾酒排序
這種排序算法乃是對冒泡算法的一種小優化,其與冒泡的差別在于,在一趟排序中可以将一個最大的移到後端,同時将一個最小的移到前端,進而對冒泡算法進行優化
核心代碼如下:
//雞尾酒排序
function CocktailSort(arr) {
console.time('timer');
let [start, end] = [0, arr.length];
while (start < end) {
//此循環與正常冒泡一緻
for (let i = start; i < end; i++) {
if (arr[i] > arr[i + 1])
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
}
end--;//由于數組最後一位已經是最大的是以沒有必要再讓其參與後續的排序
for (let i = end - 1; i >= start; i--) {
if (arr[i] < arr[i - 1])
[arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
}
start++;
}
console.timeEnd('timer');
} 耗費時間如下
由于其本質與冒泡算法類似,雖然好上些許,但其本質仍為O(n²)的時間複雜度故時間并未得到太大的縮減(由于解構指派的原因優化後的算法還不如不優化,是真的騷)
3.選擇排序
選擇排序也是大家所熟知的一種基礎算法,其核心在于每一次選出最小(或最大)的一個數放到已經有序的數列後,經過如此重複操作後獲得有序的數列
代碼如下:
//選擇排序
function SelecttionSort(arr) {
console.time('timer');
for (let i = 0; i < arr.length; i++) {
let min = i;//min表示目前最小值的下标
for (let j = i + 1; j < arr.length; j++) {
min = arr[j] < arr[min] ? j : min; //如果目前下标的值比arr[min]的值要小則以目前值替換
}
[arr[i], arr[min]] = [arr[min], arr[i]];
}
console.timeEnd('timer');
} 花費時間如下:
按理說同為n平方的複雜度時間耗費應該相差不大才對,結果由于交換次數的減少導緻耗時大幅下降,感覺Js在這方面效率有點低
4.插入排序
插入排序的原理為将目前下标的數插入之前已經有序的數列中,從後往前周遊找到合适的位置後将值插入,并将該位置之後的元素依次後移進而進行排序
function InsertionSort(arr) {
console.time('timer');
for (let i = 1; i < arr.length; i++) {
for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
}
}
console.timeEnd('timer');
} 同數組耗時如下:
總結:在Js的情況下交換資料應盡量少的使用解構指派,雖然其便利性很強,但是當網頁對性能要求較高時應減少解構指派的使用,如果非用不可,在同等級時間複雜度算法的情況下應使用數字交換次數少的算法以提升頁面性能