一、快速排序(Quick Sort)
快速排序是一種**分治法(Divide and Conquer)**思想的排序算法,它的基本步驟是:
- 選一個基準元素(pivot):通常選第一個元素、最后一個元素,或者隨機一個。
- 分區(Partition):把數組分成兩部分,小于等于 pivot 的放左邊,大于 pivot 的放右邊。
- 遞歸排序:對左右兩部分繼續進行快速排序。
簡單示意圖:
原數組:[8, 3, 5, 1, 9]
選擇 pivot:8
分區后: [3, 5, 1] [8] [9]
遞歸排序左右子數組
最終排序完成
快速排序的時間復雜度:
- 最好情況:O(n log n)
- 平均情況:O(n log n)
- 最壞情況:O(n2)(例如已排好序的數據)
基本C#代碼示例(適合Unity里直接使用):
void QuickSort(int[] arr, int left, int right)
{if