partition函数两种实现方法

patition函数根据某种比较关系将数组分成两部分，下面根据元素比某个数字大或小，以此为基准划分，给出两种实现方式

1）若数组为a[0]~a[n-1],函数调用如下

partition（a，-1，n-1）a[n-1]一般作为基准元素所在的位置，返回基准元素应该放置的下标

int partition(int *a, int i, int j, int pivot){
	do{
		while (a[++i] < pivot);
		while ((j > 0) && (a[--j] >= pivot));
		swap(a, i, j);
	} while (i < j);
	swap(a, i, j);
	return i;
}

2）基于循环的partition元素，把比基准元素小的放在数组前面

 1 int partition(int *a, int start, int end){
 2     //首先注意最主要的情况，再注意特殊情况,如start和end相同，
 3     if (start == end) return -1;
 4     //找到随意下标
 5     int randomIndex = randomlyfind(start, end);
 6     //将随意值放在最后
 7     swap(a, end, randomIndex);
 8     //比较，将比随意值小的数放在其左边,交换随意值，返回随意值原本位置
 9     int small = start-1;
10     for (int index = start; index < end; index++){
11         if (a[index] < a[end]){
12             small++;
13             if (small < index){
14                 swap(a, small, index);
15             }
16         }
17     }
18     small++;
19     swap(a, small, end);
20     return small;
21 
22 }

partition函数两种实现方法

相关推荐