首页 > 代码库 > partition函数两种实现方法

partition函数两种实现方法

2024-07-15 13:54:38   226人阅读

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 }

 


联系
我们