高等排序之分割法（partition）

雨点打透心脏的1/2处 2022-02-23 15:52 186阅读 0赞

首先先给出Partition函数的伪代码：

partition(A,p,r)                //r是数组A末尾元素的下标，
    		x=A[r]						 //分割时以A[r]为基准进行分割
        	i=p-1
        	for j = p to r-1
         		if A[j] <= x
            		i=i+1
            		交换A[i]与A[j]
        	交换A[i+1]与A[r]
        	return i+1
        	//该函数作用就是将A[p...r]分割为A[p...q-1]和A[q+1,r]两个部分，并返回下标q的值。

下面根据伪代码对其作出分析：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzOTAyNQ_size_16_color_FFFFFF_t_70]  
如上图所示，要将数组A从p到r进行分割（包含两点）.这里以A\[r\]为基准进行分割（即x）。接下来我们移动A中的元素，将小于等于x的元素移至p到i的范围内（包含i）,大于x的元素移至i+1到j的范围内（不含j）。其中i初始化为p-1，j初始化为p。  
j每经过一轮运算就会向后移动一个位置，从而依次决定每个A\[j\]应该归入哪一组：

（1）**A\[j\]大于x时，元素不移动，直接让j向前移动一个位置，将A\[j\]归入“大于x的一组”.**  
（2）**A\[j\]小于等于x时，则先让i向前移动一个位置，然后交换A\[i\]和A\[j\]。这样的话，A\[j\]就进入了“小于等于x的一组”，而随着j向前移动一个位置，原来位置上的A\[i\]元素又会回到“大于x的组中”。**

此算法的复杂度：  
因为j要从p移动到r-1,因此其分割处理的**复杂度为O(n).**  
下面是分割法的一个例子：

#include<stdio.h>
    #define MAX 100000
    
    int A[MAX],n;
    int partition(int p,int r){ 
      int x=A[r],t;
      int i=p-1;
      for(int j=p;j<r;j++){ 
        if(A[j]<=x){ 
          i++;
          t=A[i];
          A[j]=A[i];
          A[i]=t;
        }
      }
      t=A[i+1];A[i+1]=A[r];A[r]=t;   //最后，将A[i+1]与A[r]交换，完成分割
      return i+1;
    }
    
    int  main(int argc, char const *argv[]) { 
      scanf("%d",&n);
      for(int i=0;i<n;i++) scanf("%d",&A[i]);
      int q=partition(0,n-1);
      for(int i=0;i<n;i++){ 
        if(i) printf(" ");
        if(i==q) printf("[");
        printf("%d",A[i]);
        if(i==q) printf("]");
      }
      printf("\n");
      return 0;
    }

输入输出示例：  
![在这里插入图片描述][20190408155721654.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzOTAyNQ_size_16_color_FFFFFF_t_70]: /images/20220223/5be8ea65b17a41969dfaa0dd051e6612.png
[20190408155721654.png]: /images/20220223/7d7e4d551d214912ba24382c463d22c5.png