快速排序是一种高效的排序算法,它基于将数据阵列划分为更小的数组.一个大数组被分成两个数组,其中一个数组的值小于指定的值,比如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[++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+1,right) end if end procedure
要了解C编程语言中的快速排序实现.