快速排序 - 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
}