数据结构和算法 - 快速排序

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

快速排序对数组进行分区,然后递归调用两次以对两个生成的子数组进行排序.该算法对于大型数据集非常有效,因为它的平均和最差情况复杂度为Ο(n 2 ),其中 n 是项目数./p>

快速排序中的分区

以下动画表示说明了如何在数组中查找数据透视值.

快速排序分区动画

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

快速排序枢轴算法

基于我们的理解对于快速排序的分区,我们现在尝试为它编写一个算法,如下所示.

 步骤1  : 选择最高指数值有枢轴步骤2  : 取两个变量指向列表的左右两边,不包括pivot 步骤3  : 左点指向低指数第4步 : 正确指向高第5步 : 而左边的值小于枢轴移动右边步骤6  : 而右边的值大于枢轴移动左边第7步 : 如果步骤5和步骤6都不匹配交换左和右步骤8  : 如果离开≥是的,他们遇到的点是新枢轴

快速排序枢轴伪代码

上述算法的伪代码可以派生为去;

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

   while True do
      while A[&plus;&plus;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

快速排序算法

递归使用数据透视算法,我们最终会得到更小的分区.然后处理每个分区以进行快速排序.我们为快速排序定义递归算法,如下所示;

 步骤1  : 使最右侧的索引值枢轴步骤2  : 使用透视值步骤3  : 对数组进行分区快速离开分区递归第4步 :  quicksort右分区递归

快速排序伪代码

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

procedure quickSort(left, right)

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

要了解C编程语言中的快速排序实现.