使用C++實現快速排序算法

快速排序基於分治法，平均時間複雜度O(n log n)，在實際應用中廣泛使用。其核心思想爲：選擇基準元素(pivot)，將數組分區爲小於和大於基準的兩部分，再遞歸排序子數組。分區採用Lomuto方案，以最右側元素爲基準，通過遍歷數組將小於基準的元素移至左側，最後交換基準至最終位置（i+1處）。 C++實現包含分區函數（partition）和遞歸排序主函數（quickSort），分區操作在原數組完成，實現原地排序。遞歸終止條件爲子數組長度≤1（left≥right）。時間複雜度平均O(n log n)，最壞O(n²)（如已排序數組選最左/右爲基準），可通過隨機選基準優化。 關鍵特性：原地排序，無需額外空間；遞歸終止條件明確；平均高效，最壞情況可優化。快速排序是面試與開發高頻算法，掌握其分區邏輯和遞歸思想是理解高效排序的關鍵。