Data Structures Algorithms 简明教程
Quick Sort Algorithm
快速排序是一种高效的排序算法，它基于将数据数组分区为更小的数组。一个大数组被分为两个数组，其中一个数组包含小于指定值（即作为分区的基准）的值，另一个数组包含大于基准值的值。
Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.
Quicksort 对一个数组进行分区，然后递归调用自身两次，对两个生成的子数组进行排序。该算法对于大规模数据集非常有效，因为它的平均复杂度和最坏情况复杂度分别为 O(n2)。
Quicksort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst-case complexity are O(n2), respectively.
Partition in Quick Sort
下面借助动画展示了如何在数组中找到基准值。
Following animated representation explains how to find the pivot value in an array.
基准值将列表分成两部分。并且通过递归，我们为每个子列表找到基准值，直到所有列表只包含一个元素。
The pivot value divides the list into two parts. And recursively, we find the pivot for each sub-lists until all lists contains only one element.
Quick Sort Pivot Algorithm
基于我们对快速排序中分区过程的理解，我们现在将尝试为其编写一个算法，如下所示。
Based on our understanding of partitioning in quick sort, we will now try to write an algorithm for it, which is as follows.
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 pivotQuick Sort Pivot Pseudocode
上文伪代码可得出如下内容 −
The pseudocode for the above algorithm can be derived as −
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 functionQuick Sort Algorithm
使用枢轴算法递归，我们最终得到了更小的可能分区。然后针对快速排序处理每个分区。我们定义快速排序的递归算法如下 −
Using pivot algorithm recursively, we end up with smaller possible partitions. Each partition is then processed for quick sort. We define recursive algorithm for quicksort as follows −
1. Make the right-most index value pivot
2. Partition the array using pivot value
3. Quicksort left partition recursively
4. Quicksort right partition recursivelyQuick Sort Pseudocode
为了更深入地了解，我们来看快速排序算法的伪代码 −
To get more into it, let see the pseudocode for quick sort algorithm −
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