快速排序 - O(n log n)複雜時間

Quicksort 是一種先進的演算法。它具有 O（n log n）的時間複雜度，並採用分而治之的策略。這種組合產生了先進的演算法效能。Quicksort 首先將一個大陣列分成兩個較小的子陣列：低元素和高元素。Quicksort 然後可以遞迴地對子陣列進行排序。

步驟是：

1. 從陣列中選擇一個稱為 pivot 的元素。

2. 對陣列重新排序，使得值小於 pivot 的所有元素都在 pivot 之前，而值大於 pivot 的所有元素都在它之後（相同的值可以是任意一種）。在此分割槽之後，樞軸處於其最終位置。這稱為分割槽操作。

3. 遞迴地將上述步驟應用於具有較小值的元素的子陣列，並分別應用於具有較大值的元素的子陣列。

   mutating func quickSort() -> Array<Element> {
   
   func qSort(start startIndex: Int, _ pivot: Int) {
   
       if (startIndex < pivot) {
           let iPivot = qPartition(start: startIndex, pivot)
           qSort(start: startIndex, iPivot - 1)
           qSort(start: iPivot + 1, pivot)
       }
   }
   qSort(start: 0, self.endIndex - 1)
   return self
   

   }

   mutating func qPartition（start startIndex：Int，_ pivot：Int） - > Int {

   var wallIndex: Int = startIndex
   
   //compare range with pivot
   for currentIndex in wallIndex..<pivot {
   
       if self[currentIndex] <= self[pivot] {
           if wallIndex != currentIndex {
               swap(&self[currentIndex], &self[wallIndex])
           }
   
           //advance wall
           wallIndex += 1
       }
   }
   

    //move pivot to final position
    if wallIndex != pivot {
        swap(&self[wallIndex], &self[pivot])
    }
    return wallIndex
}