快速排序partition的写法

2021年5月20日 12点热度 0条评论 来源: LIUHUANUCAS

1.本科时候,严老师的那本书上给的写法

int partition(int A[],int left,int right){
     if(left >= right)
          return left;
     int x = A[left];
     while(left < right){//left should be less than right. left is overwritten....
          while(left < right && A[right] > x)
               --right;
          A[left] = A[right];//left is overwritten 
          while(left < right && A[left] >= x)
               ++left;
          A[right] = A[left];//left is empty now and should be overritten by next loop or end loop;
     }
     A[left] = x;
     return left;
}

left,right 分别可以存储元素。区间表示为 A[left,right]
思想很简单:把枢轴量保存下来,这个时候 left 空闲,分别从尾部和头部开始查找,找到第一个比枢轴量大的值,放在前面空闲的位置,然后从头开始找一个大于枢轴量的值放在后面。
结果这一轮之后, left 表示为空闲的位置, right 表示结尾位置。和最开始情况一样,这样就维持了一个循环不变量。
关于里面的各个部分等号是否能够取得的问题,最简单的方式,就是拿一个比较小的数组进行测式,比如大小为2的数组。

返回的结果: A[left,returnval1],A[returnval],A[returnval+1,right]
数组分为以上三个部分。

2.给出一个SGI STL里面的简化写法
STL 里面的枢轴量的选取是首、中、尾三个数中的中位数,这里简化了。

int partition_ungarded(int A[],int first,int last){
     if(first+1 >= last)
          return first;
     int x = A[(first + last) /2];
     while(1){
          while(A[first] <=x )
               ++first;
          --last;
          while(A[last] > x)//begin to search
               --last;
          if( !( first < last) )
               return first;
          swap(A[first] , A[last]);
          ++first;
     }
}

初始条件: [first,last)
这个时候是不包含 last 指向的元素。
last 表示需要进行partition的最后一个元素的下一个位置,STL里面pass-by-one形式。
首先找到从头一个大于枢轴量的元素,然后从尾部找到一个不比枢轴量大的元素,
如果 fist 已经到达或者越过 last 那么就partition结束了。否则,交换这两个元素。 first 指向下一个元素。
状态: first 指向下一个元素,下一个元素没有被partition
last 指向从尾部来看,最后一个已经被partition的元素,刚好是,左边没有被partition的最后一个元素的下一个位置。符合初始条件。

返回结果: A[first,returnval]A[returnval+1,last)
只有两部分的内容,第一部分肯定不大于枢轴量,但是, returnval 所在的位置并不一定是枢轴量的位置。这点需要注意。这个和平时我们所了解的快排中的partition有点不大一样。所以在进行快排的时候也需要特别注意这点。

3.算法导论上的一种写法

int partition_algorithm(int A[],int begin,int end){
    int pivot = A[end];
    int i = begin;
    for(int j=begin;j<end;++j){
        if(A[j] <= pivot){
            swap(A[j],A[i]);
            i++;
        }
    }
    swap(A[i],A[end]);
    return i;
}

初始条件: nums[begin,end]
把最后一个元素作为枢轴量, i 指向开始位置,实际运行过程当中 i 左边的元素不大于枢轴量。也可以认为 i 是第一个大于枢轴量的位置。
j 表示的就是遍历指针。
A[0...i1]pivot
所以在循环结束的时候,交换 A[i],A[end]pivot=A[end] 表示把枢轴量放在左边不大于枢轴量,右边大于枢轴量。
最后 i 就是枢轴量的位置。
返回结果: A[begin...retval1]A[retval]A[retval+1...end]

    原文作者:LIUHUANUCAS
    原文地址: https://blog.csdn.net/liu2012huan/article/details/52619417
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。