1. WIKI教程
2. 数据结构和算法
3. DSA - 快速排序(Quick Sort)

DSA - 快速排序(Quick Sort)

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

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

快速排序中的分区

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

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

快速排序枢轴算法

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

<b class="notranslate">Step 1</b> − Choose the highest index value has pivot
<b class="notranslate">Step 2</b> − Take two variables to point left and right of the list excluding pivot
<b class="notranslate">Step 3</b> − left points to the low index
<b class="notranslate">Step 4</b> − right points to the high
<b class="notranslate">Step 5</b> − while value at left is less than pivot move right
<b class="notranslate">Step 6</b> − while value at right is greater than pivot move left
<b class="notranslate">Step 7</b> − if both step 5 and step 6 does not match swap left and right
<b class="notranslate">Step 8</b> − 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定义递归算法如下 -

<b class="notranslate">Step 1</b> − Make the right-most index value pivot
<b class="notranslate">Step 2</b> − partition the array using pivot value
<b class="notranslate">Step 3</b> − quicksort left partition recursively
<b class="notranslate">Step 4</b> − 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

要了解C编程语言中的快速排序实现，请单击此处 。