排序演算法 — Bubble、Merge、Quick Sort 等十大排序完整比較 | 資料結構與演算法

function bubbleSort(arr: number[]): number[] {
  const a = [...arr]; // 不修改原陣列
  const n = a.length;

  for (let i = 0; i < n - 1; i++) {
    let swapped = false;

    // 每輪結束後，最後 i 個元素已就位，不需再比較
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]]; // 解構交換
        swapped = true;
      }
    }

    // 若本輪無任何交換，陣列已有序，提前結束
    if (!swapped) break;
  }

  return a;
}

// 測試
console.log(bubbleSort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]

function selectionSort(arr: number[]): number[] {
  const a = [...arr];
  const n = a.length;

  for (let i = 0; i < n - 1; i++) {
    let minIdx = i; // 假設當前位置是最小值

    // 在未排序區間 [i+1, n-1] 中找真正的最小值
    for (let j = i + 1; j < n; j++) {
      if (a[j] < a[minIdx]) {
        minIdx = j;
      }
    }

    // 若最小值不在 i，就交換到正確位置
    if (minIdx !== i) {
      [a[i], a[minIdx]] = [a[minIdx], a[i]];
    }
  }

  return a;
}

// 測試
console.log(selectionSort([64, 25, 12, 22, 11]));
// [11, 12, 22, 25, 64]

function insertionSort(arr: number[]): number[] {
  const a = [...arr];
  const n = a.length;

  for (let i = 1; i < n; i++) {
    const key = a[i]; // 待插入的元素
    let j = i - 1;

    // 將比 key 大的元素往右移，騰出空位
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }

    // 將 key 插入正確位置
    a[j + 1] = key;
  }

  return a;
}

// 測試
console.log(insertionSort([12, 11, 13, 5, 6]));
// [5, 6, 11, 12, 13]

function mergeSort(arr: number[]): number[] {
  // 遞迴基底：長度 0 或 1 的陣列已有序
  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: number[], right: number[]): number[] {
  const result: number[] = [];
  let i = 0;
  let j = 0;

  // 比較兩個有序陣列的頭部，取較小者放入結果
  while (i < left.length && j < right.length) {
    // 注意：使用 <= 而非 <，保證穩定性（相等時優先取左側）
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  // 接上剩餘未處理的元素（只有其中一側會有剩餘）
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);

  return result;
}

// 測試
const arr1 = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(arr1)); // [3, 9, 10, 27, 38, 43, 82]

// Hoare Partition：效率較高，交換次數少
function quickSortHoare(arr: number[], low = 0, high = arr.length - 1): void {
  if (low >= high) return;

  const pivotIdx = hoarePartition(arr, low, high);
  quickSortHoare(arr, low, pivotIdx);       // 排序左半
  quickSortHoare(arr, pivotIdx + 1, high);  // 排序右半
}

function hoarePartition(arr: number[], low: number, high: number): number {
  // 隨機選 pivot，避免對已排序陣列退化為 O(n²)
  const randIdx = low + Math.floor(Math.random() * (high - low + 1));
  [arr[low], arr[randIdx]] = [arr[randIdx], arr[low]];

  const pivot = arr[low];
  let i = low - 1;
  let j = high + 1;

  while (true) {
    do { i++; } while (arr[i] < pivot); // 從左找 >= pivot 的元素
    do { j--; } while (arr[j] > pivot); // 從右找 <= pivot 的元素
    if (i >= j) return j;               // 兩指標相遇，分割完成
    [arr[i], arr[j]] = [arr[j], arr[i]]; // 交換兩側不對的元素
  }
}

// 三路分割（Dutch National Flag）— 處理大量重複元素的最佳化
// 將陣列分為三區：[< pivot] [== pivot] [> pivot]
function quickSort3Way(arr: number[], low = 0, high = arr.length - 1): void {
  if (low >= high) return;

  const pivot = arr[low + Math.floor(Math.random() * (high - low + 1))];
  let lt = low;   // arr[low..lt-1] 全 < pivot
  let gt = high;  // arr[gt+1..high] 全 > pivot
  let i = low;    // i 為當前考察指標

  while (i <= gt) {
    if (arr[i] < pivot) {
      [arr[lt], arr[i]] = [arr[i], arr[lt]];
      lt++;
      i++;
    } else if (arr[i] > pivot) {
      [arr[i], arr[gt]] = [arr[gt], arr[i]];
      gt--;
      // i 不前進！換過來的 arr[i] 還未比較
    } else {
      i++; // arr[i] === pivot，直接略過
    }
  }

  // arr[lt..gt] 全等於 pivot，已就位，不需再遞迴這段
  quickSort3Way(arr, low, lt - 1);
  quickSort3Way(arr, gt + 1, high);
}

// 測試
const arr2 = [3, 6, 8, 10, 1, 2, 1];
quickSortHoare(arr2);
console.log(arr2); // [1, 1, 2, 3, 6, 8, 10]

const arr3 = [1, 1, 1, 2, 1, 1, 1]; // 大量重複，三路分割效率極佳
quickSort3Way(arr3);
console.log(arr3); // [1, 1, 1, 1, 1, 1, 2]

function heapSort(arr: number[]): void {
  const n = arr.length;

  // 建最大堆（從最後一個非葉節點開始，向上做 sift down）
  // O(n) 建堆，比逐一 push O(n log n) 更快
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // 逐步取出堆頂（最大值），放到陣列末尾
  for (let i = n - 1; i > 0; i--) {
    // 將當前最大值（arr[0]）與末尾交換
    [arr[0], arr[i]] = [arr[i], arr[0]];
    // 對縮小後的堆頂重新 sift down，維持堆性質
    heapify(arr, i, 0);
  }
}

// Sift Down：將節點 i 下沉到正確位置（在大小為 n 的堆中）
function heapify(arr: number[], n: number, i: number): void {
  let largest = i;           // 假設根節點最大
  const left = 2 * i + 1;   // 左子節點索引
  const right = 2 * i + 2;  // 右子節點索引

  // 找出根、左子、右子中最大者
  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;

  // 若最大值不在根，交換並繼續向下調整
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

// 測試
const arr4 = [12, 11, 13, 5, 6, 7];
heapSort(arr4);
console.log(arr4); // [5, 6, 7, 11, 12, 13]

function countingSort(arr: number[]): number[] {
  if (arr.length === 0) return [];

  const max = Math.max(...arr);
  const min = Math.min(...arr);
  const range = max - min + 1;

  // 計數每個值出現的次數
  const count = new Array<number>(range).fill(0);
  for (const num of arr) {
    count[num - min]++; // 以 num - min 為索引，支援負數
  }

  // 累積計數：count[i] 表示 <= (i + min) 的元素共有幾個
  // 用於計算每個元素在輸出中的最終位置
  for (let i = 1; i < range; i++) {
    count[i] += count[i - 1];
  }

  // 從右往左填入輸出陣列（保持穩定性）
  const output = new Array<number>(arr.length);
  for (let i = arr.length - 1; i >= 0; i--) {
    const idx = arr[i] - min;
    output[count[idx] - 1] = arr[i];
    count[idx]--;
  }

  return output;
}

// 測試
const arr5 = [4, 2, 2, 8, 3, 3, 1];
console.log(countingSort(arr5)); // [1, 2, 2, 3, 3, 4, 8]

function radixSort(arr: number[]): number[] {
  if (arr.length === 0) return [];

  const max = Math.max(...arr);
  let exp = 1; // 當前處理的位數（1 = 個位，10 = 十位，...）

  let result = [...arr];

  // 對每一位數執行一次穩定的 Counting Sort
  while (Math.floor(max / exp) > 0) {
    result = countingSortByDigit(result, exp);
    exp *= 10;
  }

  return result;
}

function countingSortByDigit(arr: number[], exp: number): number[] {
  const n = arr.length;
  const output = new Array<number>(n).fill(0);
  const count = new Array<number>(10).fill(0); // 十進位，0-9

  // 統計當前位數各數字出現次數
  for (const num of arr) {
    const digit = Math.floor(num / exp) % 10;
    count[digit]++;
  }

  // 累積計數
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }

  // 從右往左輸出，保持穩定性（這是 Radix Sort 正確性的關鍵）
  for (let i = n - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    output[count[digit] - 1] = arr[i];
    count[digit]--;
  }

  return output;
}

// 測試
const arr6 = [170, 45, 75, 90, 802, 24, 2, 66];
console.log(radixSort(arr6)); // [2, 24, 45, 66, 75, 90, 170, 802]

function bucketSort(arr: number[], bucketCount = 10): number[] {
  if (arr.length === 0) return [];

  const max = Math.max(...arr);
  const min = Math.min(...arr);
  const range = max - min;

  // 建立空桶
  const buckets: number[][] = Array.from({ length: bucketCount }, () => []);

  // 將每個元素分配到對應的桶
  for (const num of arr) {
    // 計算元素屬於哪個桶（最後一個元素特殊處理避免越界）
    const bucketIdx = Math.min(
      Math.floor(((num - min) / (range + 1)) * bucketCount),
      bucketCount - 1
    );
    buckets[bucketIdx].push(num);
  }

  // 對每個桶內部排序（這裡使用 Insertion Sort，適合小規模）
  // 再依序合併所有桶
  return buckets.flatMap(bucket => insertionSort(bucket));
}

// 測試（適合均勻分布的浮點數）
const floats = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68];
console.log(bucketSort(floats));
// [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

#include <algorithm>
#include <vector>
#include <functional>

void cppSortExamples() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3};

    // 1. std::sort — 預設升序，使用 IntroSort（Quick + Heap + Insertion 混合）
    //    保證 O(n log n) 最壞時間，實務上極快
    std::sort(v.begin(), v.end());
    // v = {1, 2, 3, 5, 8, 9}

    // 2. 降序排列（使用預設比較器 greater<int>）
    std::sort(v.begin(), v.end(), std::greater<int>());
    // v = {9, 8, 5, 3, 2, 1}

    // 3. Lambda 自訂比較器 — 按絕對值升序
    std::vector<int> v2 = {-3, 1, -5, 2, -1};
    std::sort(v2.begin(), v2.end(), [](int a, int b) {
        return std::abs(a) < std::abs(b);
    });
    // v2 = {1, -1, -3, 2, -5}

    // 4. std::stable_sort — 使用 Merge Sort，保證穩定性
    //    同值元素的相對順序保持不變
    struct Student { std::string name; int grade; };
    std::vector<Student> students = {
        {"Alice", 90}, {"Bob", 85}, {"Charlie", 90}
    };
    std::stable_sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            return a.grade > b.grade; // 按成績降序
        }
    );
    // Alice 和 Charlie 同分，相對順序保持 Alice 在前

    // 5. 多欄位排序（不需要穩定排序時的另一種寫法）
    std::sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            if (a.grade != b.grade) return a.grade > b.grade; // 成績降序
            return a.name < b.name;                            // 同分按名字升序
        }
    );

    // 6. std::partial_sort — 只排序前 k 個最小元素，O(n log k)
    std::vector<int> v3 = {5, 2, 8, 1, 9, 3, 4};
    std::partial_sort(v3.begin(), v3.begin() + 3, v3.end());
    // v3 前 3 個是最小的 3 個，已排序：{1, 2, 3, ?, ?, ?, ?}

    // 7. std::nth_element — 保證第 k 個位置就位，左側 <= 右側，O(n) 期望
    std::vector<int> v4 = {5, 2, 8, 1, 9, 3, 4};
    std::nth_element(v4.begin(), v4.begin() + 3, v4.end());
    // v4[3] 是第 4 小的元素
}

// K-way merge 核心邏輯（模擬外部排序的合併階段）
// runs 為多個已排序的子陣列
function kWayMerge(runs: number[][]): number[] {
  // 使用最小堆追蹤每個 run 的當前最小值
  // [value, runIndex, itemIndex]
  const heap: [number, number, number][] = [];
  const result: number[] = [];

  // 初始化：每個 run 的第一個元素加入堆
  for (let i = 0; i < runs.length; i++) {
    if (runs[i].length > 0) {
      heap.push([runs[i][0], i, 0]);
    }
  }

  // 簡化版：使用陣列模擬最小堆（實務中應使用真正的堆）
  heap.sort((a, b) => a[0] - b[0]);

  while (heap.length > 0) {
    const [value, runIdx, itemIdx] = heap.shift()!;
    result.push(value);

    // 若該 run 還有剩餘元素，將下一個加入堆
    const nextIdx = itemIdx + 1;
    if (nextIdx < runs[runIdx].length) {
      const nextVal = runs[runIdx][nextIdx];
      // 插入並維持排序（實務中用堆 push + sift up）
      const insertPos = heap.findIndex(([v]) => v > nextVal);
      if (insertPos === -1) {
        heap.push([nextVal, runIdx, nextIdx]);
      } else {
        heap.splice(insertPos, 0, [nextVal, runIdx, nextIdx]);
      }
    }
  }

  return result;
}

// 測試
const runs = [[1, 4, 7], [2, 5, 8], [3, 6, 9]];
console.log(kWayMerge(runs)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

// 陷阱：不提供比較函式時，數字被轉成字串排序！
const nums = [10, 9, 2, 21, 3];
nums.sort();               // [10, 2, 21, 3, 9] ← 字典序，錯誤！
nums.sort((a, b) => a - b); // [2, 3, 9, 10, 21] ← 數值升序，正確

// 好消息：ES2019 起，V8 的 Array.sort 使用 Timsort，保證穩定性

function sortColors(nums: number[]): void {
  let low = 0;                    // [0, low) 全是 0
  let high = nums.length - 1;     // (high, n-1] 全是 2
  let mid = 0;                    // [low, mid) 全是 1

  while (mid <= high) {
    if (nums[mid] === 0) {
      // 將 0 換到左區，low 和 mid 同步前進
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 2) {
      // 將 2 換到右區，只縮小 high
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
      // 注意：mid 不前進！換過來的元素尚未檢查
    } else {
      // nums[mid] === 1，直接前進
      mid++;
    }
  }
}

// 測試
const colors = [2, 0, 2, 1, 1, 0];
sortColors(colors);
console.log(colors); // [0, 0, 1, 1, 2, 2]

function merge(intervals: number[][]): number[][] {
  if (intervals.length <= 1) return intervals;

  // 按起點升序排列
  intervals.sort((a, b) => a[0] - b[0]);

  const result: number[][] = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const curr = intervals[i];
    const last = result[result.length - 1];

    if (curr[0] <= last[1]) {
      // 重疊（當前起點 <= 上一個終點）：合併，取終點最大值
      last[1] = Math.max(last[1], curr[1]);
    } else {
      // 不重疊：直接加入結果
      result.push(curr);
    }
  }

  return result;
}

// 測試
console.log(merge([[1,3],[2,6],[8,10],[15,18]])); // [[1,6],[8,10],[15,18]]
console.log(merge([[1,4],[4,5]]));                // [[1,5]]

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function sortList(head: ListNode | null): ListNode | null {
  // 長度 0 或 1，直接回傳
  if (!head || !head.next) return head;

  // 快慢指標找中點（slow 停在左半末尾）
  let slow: ListNode = head;
  let fast: ListNode | null = head.next;

  while (fast && fast.next) {
    slow = slow.next!;
    fast = fast.next.next;
  }

  // 切斷鏈結，分成左右兩半
  const mid = slow.next;
  slow.next = null;

  // 遞迴排序兩半
  const left = sortList(head);
  const right = sortList(mid);

  // 合併兩個有序鏈結串列
  return mergeLists(left, right);
}

function mergeLists(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  const dummy = new ListNode(0); // 虛擬頭節點，簡化邊界處理
  let curr = dummy;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      curr.next = l1;
      l1 = l1.next;
    } else {
      curr.next = l2;
      l2 = l2.next;
    }
    curr = curr.next;
  }

  // 接上剩餘節點
  curr.next = l1 ?? l2;
  return dummy.next;
}

function largestNumber(nums: number[]): string {
  const strs = nums.map(String);

  // 自訂比較：比較 a+b 和 b+a 哪個更大
  strs.sort((a, b) => {
    const ab = a + b;
    const ba = b + a;
    return ba.localeCompare(ab); // 降序：大的在前
  });

  // 特殊情況：全是 0（如 [0, 0]）
  if (strs[0] === '0') return '0';

  return strs.join('');
}

// 測試
console.log(largestNumber([3, 30, 34, 5, 9])); // "9534330"
console.log(largestNumber([10, 2]));             // "210"