冒泡排序
通過相鄰元素的比較和交換，使得每一趟循環都能找到未有序數組的最大值或最小值。
内循環： 使用相鄰雙指針 j , j + 1 從左至右周遊，依次比較相鄰元素大小，若左元素大于右元素則将它們交換；周遊完成時，最大元素會被交換至數組最右邊 。
外循環： 不斷重複「内循環」，每輪将目前最大元素交換至 剩餘未排序數組最右邊 ，直至所有元素都被交換至正确位置時結束。
/**
* 冒泡
* 每一趟找出最大的,總共比較次數為arr.length-1次,每次的比較次數為arr.length-1-i次，依次遞減
* @param {*} arr
* @returns array
*/
function bubbleSort(arr) {
/**
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
針對所有的元素重複以上的步驟，除了最後一個。
持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
相同元素的前後順序并沒有改變，是以冒泡排序是一種穩定排序算法。
原始數組： [ 99, 88, 66, 101, 90, 45 ]
第1次循環 [ 88, 66, 99, 90, 45, 101 ]
第2次循環 [ 66, 88, 90, 45, 99, 101 ]
第3次循環 [ 66, 88, 45, 90, 99, 101 ]
第4次循環 [ 66, 45, 88, 90, 99, 101 ]
第5次循環 [ 45, 66, 88, 90, 99, 101 ]
*/
let len = arr.length;
if (!len) {
return [];
}
console.log('原始數組：', arr);
//外循環，對被排序的數組進行周遊，輪數為數組的長度
for (let i = 0; i < len - 1; i++) {
// 内循環，循環比較相鄰元素
for (let j = 0; j < len - 1 - i; j++) {
//如果前一個元素大于後一個元素的話，就交換兩個元素的位置，最後是以從大到小的順序輸出
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; //元素交換
}
}
console.log(`第${i+1}次循環`, arr);
}
return arr;
}
優化
普通冒泡排序的時間複雜度恒為 O(N2)，與輸入數組的元素分布無關。
通過增加一個标志位 flag ，若在某輪「内循環」中未執行任何交換操作，則說明數組已經完成排序，直接傳回結果即可。
優化後的冒泡排序的最差和平均時間複雜度仍為 O(N2) ;在輸入數組 已排序 時，達到 最佳時間複雜度 (N)
function bubbleSort(arr) {
let len = arr.length;
if (!len) {
return [];
}
console.log('原始數組：', arr);
//外循環，對被排序的數組進行周遊，輪數為數組的長度
for (let i = 0; i < len - 1; i++) {
let flag = false; // 初始化标志位
// 内循環，循環比較相鄰元素
for (let j = 0; j < len - 1 - i; j++) {
//如果前一個元素大于後一個元素的話，就交換兩個元素的位置，最後是以從大到小的順序輸出
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; //元素交換
flag = true; // 記錄交換元素
}
}
if (!flag) break; // 内循環未交換任何元素，則跳出
console.log(`第${i+1}次循環`, arr);
}
return arr;
}
選擇排序
思路：依次找到剩餘元素的最小值或者最大值，放置在末尾或者開頭。
/**
* 選擇排序
* 依次找到剩餘元素的最小值或者最大值，放置在末尾或者開頭。
* @param {Array} arr
* @returns
*/
function selectionSort(arr) {
let len = arr.length;
let minIndex;
for (let i = 0; i < len - 1; i++) {
minIndex = i;//先假設第一個數字最小
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { //尋找最小的數
minIndex = j; //将最小數的索引儲存
}
}
[arr[minIndex], arr[i]] = [arr[i], arr[minIndex]]//交換兩個元素
}
return arr;
}
插入排序
思路：以第一個元素為有序數組，其後的元素通過再這個已有序的數組中找到合适的元素并插入。
function insertSort(arr) {
let length = arr.length,
preIndex, current;
for (let i = 1; i < length; i++) {
preIndex = i - 1;
current = arr[i];
// 和已經排序好的序列進行比較，插入到合适的位置
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
console.log(`第${i}次循環`, arr);
}
return arr;
}
希爾排序
通過某個增量 gap，将整個序列分給若幹組，從後往前進行組内成員的比較和交換，随後逐漸縮小增量至 1。希爾排序類似于插入排序，隻是一開始向前移動的步數從 1 變成了 gap
function shellSort(arr) {
let len = arr.length;
// 初始步數
let gap = parseInt(len / 2);
// 逐漸縮小步數
while (gap) {
// 從第gap個元素開始周遊
for (let i = gap; i < len; i++) {
// 逐漸其和前面其他的組成員進行比較和交換
for (let j = i - gap; j >= 0; j -= gap) {
if (arr[j] > arr[j + gap]) {
[arr[j], arr[j + gap]] = [arr[j + gap], arr[j]];
} else {
break;
}
}
}
gap = parseInt(gap / 2);
}
}
歸并排序
遞歸将數組分為兩個序列，有序合并這兩個序列。作為一種典型的分而治之思想的算法應用，歸并排序的實作由兩種方法：
- 自上而下的遞歸（所有遞歸的方法都可以用疊代重寫，是以就有了第2種方法）。
- 自下而上的疊代。
function /**
* 歸并排序
*/
mergeSort(arr) {
let len = arr.length;
if (len < 2) {
return arr;
}
let middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
console.log(`處理過程：`, arr);
return this.merge(this.mergeSort(left), this.mergeSort(right));
},
/**
* 歸并排序輔助方法
*/
function merge(left, right) {
let result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) {
result.push(left.shift());
}
while (right.length){
result.push(right.shift());
}
return result;
}
快速排序
快速排序算法是一種基于分治思想的排序算法，其核心思路在于通過選取一個基準值，将待排序數組劃分為左右兩個子序列，其中左側序列所有元素均小于基準值，右側序列所有元素均大于基準值。之後對左右子序列遞歸進行快排操作，最終将整個序列排好序。
以下是使用 TypeScript 實作的快速排序算法代碼：
function quickSort(arr: number[]): number[] {
if (arr.length <= 1) {
return arr;
}
const pivotIndex = Math.floor(arr.length / 2);
const pivot = arr[pivotIndex];
const left = [];
const right = [];
for (let i = 0; i < arr.length; i++) {
if (i === pivotIndex) {
continue;
}
const currentItem = arr[i];
if (currentItem < pivot) {
left.push(currentItem);
} else {
right.push(currentItem);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
堆排序
堆排序算法是一種基于堆資料結構的排序算法，其核心思路在于将待排序數組看做二叉樹，通過建構大頂堆或小頂堆來實作排序。對于大頂堆，每個節點的值均大于或等于它的子節點；對于小頂堆，每個節點的值均小于或等于它的子節點。排序時，取堆頂元素，将其存儲到已排序數組中，并從堆中删除；然後重新調整剩餘元素形成新的堆，重複以上操作直至所有元素排序完成。
以下是使用 TypeScript 實作的堆排序算法代碼：
function heapSort(arr: number[]): number[] {
const len = arr.length;
// 初始化大頂堆，從第一個非葉子結點開始
for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
heapify(arr, len, i);
}
// 排序，每次将堆頂元素與未排定部分的最後一個元素交換，并重新構造大頂堆
for (let i = len - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, i, 0);
}
return arr;
}
// 堆化函數，将以i為根節點的子樹調整為大頂堆
function heapify(arr: number[], len: number, i: number) {
let largest = i; // 最大值預設為根節點
const left = 2 * i + 1; // 左子節點下标
const right = 2 * i + 2; // 右子節點下标
// 如果左子節點比目前最大值大，則更新最大值
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子節點比目前最大值大，則更新最大值
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根節點，則交換根節點和最大值，并繼續調整以最大值為根的子樹
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, len, largest);
}
}
記數排序
記數排序（Counting Sort）是一種非基于比較的排序算法，其時間複雜度為O(n+k)，其中k表示待排序數組中最大元素與最小元素之差加1。該算法的基本思想是統計每個元素在待排序數組中出現的次數，然後根據統計結果建構有序序列。
/**
* 計數排序
* @param arr 待排序數組
* @returns 排序後數組
*/
function countingSort(arr: number[]): number[] {
const max = Math.max(...arr);
const count = new Array(max + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
count[arr[i]]++;
}
const res = [];
for (let i = 0; i <= max; i++) {
while (count[i]--) {
res.push(i);
}
}
return res;
}
桶排序
桶排序（Bucket Sort）是一種線性排序算法，它利用了函數的映射關系，将要排序的資料分到有限數量的桶子裡，每個桶子再分别排序。桶排序的時間複雜度取決于桶的數量和桶内使用的排序算法，通常情況下是O(n+k)。
/**
* 桶排序
* @param arr 待排序數組
* @param bucketSize 桶大小
* @returns 排序後數組
*/
function bucketSort(arr: number[], bucketSize = 5): number[] {
if (arr.length === 0) {
return arr;
}
// 找出最大值和最小值
let min = arr[0];
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
} else if (arr[i] > max) {
max = arr[i];
}
}
// 計算桶的數量
const bucketCount = Math.floor((max - min) / bucketSize) + 1;
const buckets: number[][] = [];
for (let i = 0; i < bucketCount; i++) {
buckets[i] = [];
}
// 将元素配置設定到桶中
for (let i = 0; i < arr.length; i++) {
const index = Math.floor((arr[i] - min) / bucketSize);
buckets[index].push(arr[i]);
}
// 對每個桶進行排序，并将結果合并
const res = [];
for (let i = 0; i < buckets.length; i++) {
if (buckets[i]) {
const sortedBucket = countingSort(buckets[i]);
for (let j = 0; j < sortedBucket.length; j++) {
res.push(sortedBucket[j]);
}
}
}
return res;
}
基數排序
基數排序（Radix Sort）是一種多關鍵字排序算法，可用于對數字序列進行排序。基數排序先按照最低有效位（LSB）對元素進行排序，然後依次按照次低有效位、次次低有效位……最高有效位進行排序。該算法的時間複雜度為O(d*(n+k))，其中d表示數字位數，k表示每個數字可能的取值範圍。
/**
* 基數排序
* @param arr 待排序數組
* @returns 排序後數組
*/
function radixSort(arr: number[]): number[] {
const max = Math.max(...arr);
const buckets: number[][] = [];
// 初始化桶
for (let i = 0; i < 10; i++) {
buckets[i] = [];
}
// 計算最大數字的位數
let digitCount = 0;
while (max > 0) {
max = Math.floor(max / 10);
digitCount++;
}
// 根據每一位進行排序
for (let i = 0; i < digitCount; i++) {
for (let j = 0; j < arr.length; j++) {
const num = arr[j];
const digit = Math.floor(num / Math.pow(10, i)) % 10;
buckets[digit].push(num);
}
arr = [];
for (let k = 0; k < buckets.length; k++) {
while (buckets[k].length) {
arr.push(buckets[k].shift()!);
}
}
}
return arr;
}