Data Structures Algorithms 简明教程

Quick Sort Algorithm

快速排序是一种高效的排序算法，它基于将数据数组分区为更小的数组。一个大数组被分为两个数组，其中一个数组包含小于指定值（即作为分区的基准）的值，另一个数组包含大于基准值的值。

Quicksort 对一个数组进行分区，然后递归调用自身两次，对两个生成的子数组进行排序。该算法对于大规模数据集非常有效，因为它的平均复杂度和最坏情况复杂度分别为 O(n2)。

Partition in Quick Sort

下面借助动画展示了如何在数组中找到基准值。

基准值将列表分成两部分。并且通过递归，我们为每个子列表找到基准值，直到所有列表只包含一个元素。

Quick Sort Pivot Algorithm

基于我们对快速排序中分区过程的理解，我们现在将尝试为其编写一个算法，如下所示。

1. Choose the highest index value has pivot
2. Take two variables to point left and right of the list
excluding pivot
3. Left points to the low index
4. Right points to the high
5. While value at left is less than pivot move right
6. While value at right is greater than pivot move left
7. If both step 5 and step 6 does not match swap left and right
8. If left ≥ right, the point where they met is new pivot

Quick Sort Pivot Pseudocode

上文伪代码可得出如下内容 −

function partitionFunc(left, right, pivot)
   leftPointer = left
   rightPointer = right - 1

   while True do
      while A[++leftPointer] < pivot do
      //do-nothing
      end while

      while rightPointer > 0 && A[--rightPointer] > pivot do
         //do-nothing
      end while

      if leftPointer >= rightPointer
         break
      else
         swap leftPointer,rightPointer
      end if
   end while

   swap leftPointer,right
   return leftPointer
end function

Quick Sort Algorithm

使用枢轴算法递归，我们最终得到了更小的可能分区。然后针对快速排序处理每个分区。我们定义快速排序的递归算法如下 −

1. Make the right-most index value pivot
2. Partition the array using pivot value
3. Quicksort left partition recursively
4. Quicksort right partition recursively

Quick Sort Pseudocode

为了更深入地了解，我们来看快速排序算法的伪代码 −

procedure quickSort(left, right)
   if right-left <= 0
      return
   else
      pivot = A[right]
      partition = partitionFunc(left, right, pivot)
      quickSort(left,partition-1)
      quickSort(partition+1,right)
   end if
end procedure

Analysis

快速排序算法的最坏情况复杂度为 O(n2) 。然而，使用此技术，我们通常在平均情况下在 O (n log n) 时间内获得输出。

Implementation

以下是各种编程语言中快速排序算法的实现示例 −