问题描述:

标题:三部排序
一般的排序有许多经典算法,如快速排序、希尔排序等。 但实际应用时,经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法,可以根据实际情况建立更好的解法。 比如,对一个整型数组中的数字进行分类排序: 使得负数都靠左端,正数都靠右端,0在中部。注意问题的特点是:负数区域和正数区域内并不要求有序。可以利用这个特点通过1次线性扫描就结束战斗!! 以下的程序实现了该目标。 其中x指向待排序的整型数组,len是数组的长度。

void sort3p(int* x, int len)
{
	int p = 0;
	int left = 0;
	int right = len-1;
	
	while(p<=right){
		if(x[p]<0){
			int t = x[left];
			x[left] = x[p];
			x[p] = t;
			left++;
			p++;
		}
		else if(x[p]>0){
			int t = x[right];
			x[right] = x[p];
			x[p] = t;
			right--;
		}
		else{
			  ______________________________//填空部分
		}
	}
}

来分析一下这道题,相信会写快速排序的同学应该可以秒写这个填空部分。程序一开始定义了三个变量,p,left和right,结合下面的代码,我们可以分析出,left指向的就是数组的最左端,而right指向的是数组的最右端,p就起到一个哨兵的作用。

当p指向的内容是小于0的数时,就把它和left指向的元素交换位置,并且p再往前探路,然后left右移一位,表示左边的就不用管了。当p指向的内容是大于0的数时,就把它和right指向的元素交换位置,再将right左移一位,表示后面的就不用管了。

既然对大于0和小于0的数都已经进行移位操作了,等于0的时候其实时不需要操作的(这个地方得好好体会),就只用移动指针就行了,那么要移动哪个呢,现在有left,p和right,right肯定是不可能动的,因为如果此时right指向的是一个小于0的数,左移就错了。 (显然,,别打我) 而left同理,如果此时left指向的是一个大于0的数,将left右移的话,那肯定也错了。所以就只用将哪个探路的指针向后移动就可以了。程序如下:

#include <iostream>
using namespace std;

void sort3p(int* x, int len)
{
	int p = 0;
	int left = 0;
	int right = len-1;
	
	while(p<=right){
		if(x[p]<0){
			int t = x[left];
			x[left] = x[p];
			x[p] = t;
			left++;
			p++;
		}
		else if(x[p]>0){
			int t = x[right];
			x[right] = x[p];
			x[p] = t;
			right--;
		}
		else{
			  p++;
		}
	}
}

int main()
{
	int x[14] = {25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0};
	sort3p(x , 14);
	
	for(int i = 0 ; i < 14 ; ++i)
		cout << x[i] << " ";
	return 0;
 } 

完,读到这里的同学可以去复习或者学习一下快速排序。


立志成为一名攻城狮