排序算法是計算機科學(xué)中的基本算法，它們將一個無序的數(shù)組或列表按特定順序進行排列（如升序或降序）。常見的排序算法可以根據(jù)其時間復(fù)雜度、空間復(fù)雜度和適用場景分類。以下是幾種常見的排序算法：

1. 冒泡排序（Bubble Sort）

冒泡排序是一種簡單的比較排序算法。它通過不斷比較相鄰元素，并根據(jù)需要交換它們，逐漸將最大（或最小）的元素“冒泡”到數(shù)組的一端。

• 時間復(fù)雜度：O(n2)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：穩(wěn)定
• 適用場景：適合小規(guī)模數(shù)據(jù)集，但效率較低，不適合大數(shù)據(jù)集。

算法步驟：

• 從數(shù)組的開頭開始，依次比較相鄰的元素，如果順序錯誤則交換它們。
• 每一輪會把當(dāng)前未排序部分中最大的元素放在最后的位置。
• 重復(fù)該過程，直到?jīng)]有元素需要交換。

function bubbleSort(arr) {
? ? for (let i = 0; i < arr.length; i++) {
? ? ? ? for (let j = 0; j < arr.length - 1 - i; j++) {
? ? ? ? ? ? if (arr[j] > arr[j + 1]) {
? ? ? ? ? ? ? ? [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return arr;
}

---

2. 選擇排序（Selection Sort）

選擇排序通過在未排序的部分中找到最小（或最大）的元素，并將其與未排序部分的第一個元素交換，逐步構(gòu)建有序序列。

• 時間復(fù)雜度：O(n2)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：不穩(wěn)定
• 適用場景：適合數(shù)據(jù)規(guī)模較小，簡單實現(xiàn)，但效率較低。

算法步驟：

• 遍歷數(shù)組，找到未排序部分的最小元素，將其與當(dāng)前未排序部分的第一個元素交換。
• 重復(fù)此過程，直到整個數(shù)組排序完畢。

function selectionSort(arr) {
? ? for (let i = 0; i < arr.length; i++) {
? ? ? ? let minIndex = i;
? ? ? ? for (let j = i + 1; j < arr.length; j++) {
? ? ? ? ? ? if (arr[j] < arr[minIndex]) {
? ? ? ? ? ? ? ? minIndex = j;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
? ? }
? ? return arr;
}

---

3. 插入排序（Insertion Sort）

插入排序通過從頭開始逐一將元素插入到已排序部分的正確位置，從而逐步形成一個有序序列。

• 時間復(fù)雜度：O(n2)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：穩(wěn)定
• 適用場景：適合數(shù)據(jù)量較小或部分有序的數(shù)據(jù)集。

算法步驟：

• 從數(shù)組的第二個元素開始，將其與已排序部分的元素進行比較，并插入到正確的位置。
• 對每個元素重復(fù)此操作，直到整個數(shù)組排序完畢。

function insertionSort(arr) {
? ? for (let i = 1; i < arr.length; i++) {
? ? ? ? let key = arr[i];
? ? ? ? let j = i - 1;
? ? ? ? while (j >= 0 && arr[j] > key) {
? ? ? ? ? ? arr[j + 1] = arr[j];
? ? ? ? ? ? j--;
? ? ? ? }
? ? ? ? arr[j + 1] = key;
? ? }
? ? return arr;
}

---

4. 歸并排序（Merge Sort）

歸并排序是基于分治思想的排序算法，將數(shù)組不斷拆分成子數(shù)組，分別對其排序后再合并。

• 時間復(fù)雜度：O(n log n)
• 空間復(fù)雜度：O(n)
• 穩(wěn)定性：穩(wěn)定
• 適用場景：適合大規(guī)模數(shù)據(jù)集，具有較高效率。

算法步驟：

• 遞歸地將數(shù)組分成兩個子數(shù)組。
• 對每個子數(shù)組分別進行排序。
• 合并兩個有序子數(shù)組為一個完整的有序數(shù)組。

function mergeSort(arr) {
? ? if (arr.length <= 1) return arr;
? ? const mid = Math.floor(arr.length / 2);
? ? const left = mergeSort(arr.slice(0, mid));
? ? const right = mergeSort(arr.slice(mid));

? ? return merge(left, 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());
? ? ? ? }
? ? }
? ? return result.concat(left, right);
}
?

---

5. 快速排序（Quick Sort）

快速排序也是基于分治思想。它通過選擇一個“基準”元素，將數(shù)組分為兩部分，一部分比基準元素小，另一部分比基準元素大，然后遞歸地對兩部分進行排序。

• 時間復(fù)雜度：O(n log n)（最壞情況 O(n2)）
• 空間復(fù)雜度：O(log n)（遞歸?？臻g）
• 穩(wěn)定性：不穩(wěn)定
• 適用場景：在平均情況下非常高效，適合大多數(shù)數(shù)據(jù)集。

算法步驟：

• 選擇一個基準元素（通常為第一個或最后一個）。
• 將數(shù)組分為兩部分，一部分比基準小，另一部分比基準大。
• 對兩部分遞歸進行快速排序。
• 合并兩部分。

function quickSort(arr) {
? ? if (arr.length <= 1) return arr;
? ? const pivot = arr[arr.length - 1];
? ? let left = [];
? ? let right = [];
? ? for (let i = 0; i < arr.length - 1; i++) {
? ? ? ? if (arr[i] < pivot) left.push(arr[i]);
? ? ? ? else right.push(arr[i]);
? ? }
? ? return [...quickSort(left), pivot, ...quickSort(right)];
}

---

6. 堆排序（Heap Sort）

堆排序是一種基于二叉堆的數(shù)據(jù)結(jié)構(gòu)的排序算法。通過構(gòu)建最大堆或最小堆，每次將堆頂元素與末尾元素交換，然后繼續(xù)調(diào)整堆。

• 時間復(fù)雜度：O(n log n)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：不穩(wěn)定
• 適用場景：適合需要在原地排序的數(shù)據(jù)集。

算法步驟：

• 構(gòu)建最大堆。
• 每次將堆頂元素與數(shù)組末尾元素交換，縮小堆的范圍后重新調(diào)整堆。

function heapify(arr, length, i) {
? ? let largest = i;
? ? let left = 2 * i + 1;
? ? let right = 2 * i + 2;

? ? if (left < length && arr[left] > arr[largest]) {
? ? ? ? largest = left;
? ? }
? ? if (right < length && arr[right] > arr[largest]) {
? ? ? ? largest = right;
? ? }
? ? if (largest !== i) {
? ? ? ? [arr[i], arr[largest]] = [arr[largest], arr[i]];
? ? ? ? heapify(arr, length, largest);
? ? }
}

function heapSort(arr) {
? ? let length = arr.length;
? ??
? ? // 構(gòu)建最大堆
? ? for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
? ? ? ? heapify(arr, length, i);
? ? }

? ? // 堆排序
? ? for (let i = length - 1; i > 0; i--) {
? ? ? ? [arr[0], arr[i]] = [arr[i], arr[0]];
? ? ? ? heapify(arr, i, 0);
? ? }
? ? return arr;
}
?

---

總結(jié)：

• O(n2) 的算法：冒泡排序、選擇排序、插入排序——這些算法適合小規(guī)模數(shù)據(jù)集。
• O(n log n) 的算法：歸并排序、快速排序、堆排序——適合大規(guī)模數(shù)據(jù)集，其中快速排序通常表現(xiàn)最好，但最壞情況為 O(n2)。