问题描述：
标题：三部排序
一般的排序有许多经典算法，如快速排序、希尔排序等。 但实际应用时，经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法，可以根据实际情况建立更好的解法。 比如，对一个整型数组中的数字进行分类排序： 使得负数都靠左端，正数都靠右端，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;
}
完，读到这里的同学可以去复习或者学习一下快速排序。
Comments NOTHING