数据结构和算法快速排序


快速排序是一种高效的排序算法,它基于将数据阵列划分为更小的数组。一个大型数组被分成两个数组,其中一个数组的值小于指定的值,比如pivot,根据该数组创建分区,另一个数组保存的值大于数据透视值。

快速排序对数组进行分区,然后递归调用两次以对两个结果子数组进行排序。该算法对于大尺寸数据集非常有效,因为其平均和最差情况复杂度为0(n 2),其中 n 是项目数。

快速排序中的分区

以下动画表示解释了如何在数组中查找透视值。

快速排序分区动画

数据透视值将列表分为两部分。并且递归地,我们找到每个子列表的轴,直到所有列表只包含一个元素。

快速排序枢轴算法

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

**Step 1**  Choose the highest index value has pivot
**Step 2**  Take two variables to point left and right of the list excluding pivot
**Step 3**  left points to the low index
**Step 4**  right points to the high
**Step 5**  while value at left is less than pivot move right
**Step 6**  while value at right is greater than pivot move left
**Step 7**  if both step 5 and step 6 does not match swap left and right
**Step 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

快速排序算法

递归地使用pivot算法,我们最终得到更小的可能分区。然后处理每个分区以进行快速排序。我们为quicksort定义递归算法如下 -

**Step 1**  Make the right-most index value pivot
**Step 2**  partition the array using pivot value
**Step 3**  quicksort left partition recursively
**Step 4**  quicksort right partition recursively

快速排序伪代码

要了解更多信息,请参阅伪代码以进行快速排序算法

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