[DSA] 排序Sort 方式整理

排序算法是計算機科學中最基礎且最重要的主題之一。以下是一些常見的排序方法，以及它們的簡要描述：

1. **冒泡排序 (Bubble Sort)**

   - 方法：重複地遍歷數組，每次比較兩個相鄰的元素，如果它們的順序錯誤就交換它們。

   - 時間複雜度：最差、平均和最好情況下都是 O(n^2)。

2. **選擇排序 (Selection Sort)**

   - 方法：在未排序的部分中找到最小（或最大）的元素，然後將其放到排序部分的開頭。

   - 時間複雜度：最差、平均和最好情況下都是 O(n^2)。

3. **插入排序 (Insertion Sort)**

   - 方法：從第一個元素開始，重複地取出一個元素並將其插入到前面已排序的部分的正確位置中。

   - 時間複雜度：最差情況下是 O(n^2)，但對於部分排序的數組，其性能可以達到近似 O(n)。

4. **快速排序 (Quick Sort)**

   - 方法：選擇一個'基準'元素，並將數組分為小於基準和大於基準的兩部分，然後遞迴地對這兩部分進行排序。

   - 時間複雜度：平均和最好情況下是 O(n log n)，但最差情況下是 O(n^2)。

5. **合併排序 (Merge Sort)**

   - 方法：將數組分成兩半，遞迴地對每一半進行排序，然後合併這兩部分。

   - 時間複雜度：在最差、平均和最好情況下都是 O(n log n)。

6. **堆排序 (Heap Sort)**

   - 方法：使用數組創建一個最大堆 (max heap) 或最小堆 (min heap)，然後一次取出堆的最大（或最小）元素，直到堆為空。

   - 時間複雜度：在最差、平均和最好情況下都是 O(n log n)。

7. **希爾排序 (Shell Sort)**

   - 方法：是插入排序的一個變體，其中元素首先被分成多個子列表，這些子列表使用插入排序進行排序，隨著算法的進行，子列表的大小逐漸減小。

   - 時間複雜度：因子列表的選擇和大小而異，但對於許多實際的數據集，其性能通常優於 O(n^2)。

這些只是眾多排序算法中的一部分。每種排序算法都有其自己的優點和缺點，適用於不同的情境和需求。

從前輩的LeetCode筆記中 排序相關的題目

Sort algorithm

• Selection/Bubble/Insertion/Heap sort
• Bucket Sort
• 把數字分成一個一個的區段，ex: [0] : 0~9, [1] : 10~19, [2] : 20~29
• Counting/Radix Sort

排序 Sort：”215. Kth Largest Element in an Array” 是一題考查排序的題目。

• Leetcode — 215. Kth Largest Element in an Array (中文)
• https://leetcode.wang/ 215. Kth Largest Element in an Array