算法基础：排序基础：分区算法之双向循环法

分区算法也被称为分割算法，实际上它是快速排序的核心内容，此部分内容如果理解了，快排就剩下一个三行的递归套路需要写了。这篇文章来介绍一下快排的内核：分区算法。

算法思路

• 分区算法也体现了分而治之的思想，在待排的序列中选取基准值pivot，根据基准值将待排序列分为两个区域，如果是升序方式的左边都是小于或等于基准值的部分，而右边则都是大于基准值的部分。分区算法执行一次之后，一般来说序列仍然是无序的状态，唯一在后续排列中不需要再移动位置的就是基准值，分区算法执行一次之后产生的效果是：
  • 基准值归位：基准值的位置已经是整体排序之后的正确位置，后续的排序继续抛开基准值进行分而治之分别排序即可，这也是和归并排序的一个不同之处，边界处理的方式是不同的，而根本之处在于算法的核心是不同的。
  • 左右分区：整体将数据分为左右两个分区，这也是此算法名称的来源，整体大致有序，分区还需继续迭代，这也是分区算法一次执行之后的效果

基准值的选择

基准值的选择方式很重要，但是这个意义只是相对于快排来说的，比如一个已经是升序的排序序列使用以分区算法为主要要点的快排，基准值顺次从左到右选择的话，实际效率反而会恶化至很差的情形，也非常容易理解，因为分区算法的优势没有体现出来，分区没有太大意义。

双向循环方式

分区算法可以使用双向循环方式，主要的算法要点如下所示，

• 基准值：为了理解简单，本文基准值缺省选取数组的第一个元素，也可以选择最后一个元素，或者随机选择，这并不是本算法本身的核心，在快排的时候还会展开。
• 双向指针：对于序列分别提供left和right两个指针，left指针指向左侧第一个元素，right指针指向右侧第一个元素
• 指针移动方式：分别对每个元素进行判断，left指针所指向的元素如果小于或等于基准值的话就应该继续移动，指针++，同理，right指针所指向的元素如果大于基准值的话也应该继续移动，指针–，当然每次移动之前还需要同时对两个指针是否已经相遇进行判断，应该保证left < right的条件
• 指针停下条件：左右指针相遇（值相等），或者分别找到了无法移动的位置。
• 元素交换：指针移动到无法移动的位置，说明分别找到需要交换的位置，进行交换，此处正是快排不是稳定排序的根源，交换使得相同元素的位置在排序后发生了变化。
• 基准值定位：两个元素最终相遇的位置即为基准值最后落座的位置，直接进行交换即可
• 指针移动顺序：本文条件下应当right指针先移动，这个非常容易理解，主要在于两个指针最终相遇的位置，最后一步如果是left指针先移动，会停在比基准值大的元素上，这个位置如果和基准值进行交换的话，本文条件中的第一个元素会被交换成一个比基准大的元素。

模拟实现

int partition(int* arr, int start, int end) { int left=start, right=end; if (left >= right ) return right; int pivot = arr[left]; while (left != right) { while (left < right && arr[right] > pivot) right--; while (left < right && arr[left] <= pivot) left++; if (left < right) { int tmp = arr[left]; arr[left]=arr[right]; arr[right]=tmp; } } arr[start]=arr[left]; arr[left]=pivot; return right; } 

注意点：此处第一个while循环的right右侧指针移动时的判断条件arr[right] > pivot，有些算法基础数中写的是>=，同时在left指针移动的时候是<=，在快速排序中可能对于某些数据没有问题，但是对于分区算法这里就显得非常扎眼。

结果验证

加上打印和调用的示例代码，可以使用如下方式进行验证

#include  #include  #include  int partition(int* arr, int start, int end) { int left=start, right=end; if (left >= right ) return right; int pivot = arr[left]; while (left != right) { while (left < right && arr[right] > pivot) right--; while (left < right && arr[left] <= pivot) left++; if (left < right) { int tmp = arr[left]; arr[left]=arr[right]; arr[right]=tmp; } } arr[start]=arr[left]; arr[left]=pivot; return right; } void print_array(int* arr, int num) { for (int i=0; i<num; i++) printf("%d ",arr[i]); printf("\n"); } int main() { int n = 0; while (scanf("%d",&n) != EOF) { int* array = (int *)malloc(sizeof(int)*n); memset(array,0,sizeof(int)*n); for (int i=0; i<n; i++) { scanf("%d",&array[i]); } partition(array,0,n-1); print_array(array,n); free(array); array= NULL; } } 

执行结果示例

9
4 6 4 5 2 6 4 4 9
2 4 4 4 4 6 5 6 9

如果上述的arr[right] > pivot被写成arr[right] >= pivot的情况下，执行结果会如下所示：

9
4 6 4 5 2 6 4 4 9
2 4 4 5 6 6 4 4 9