Question

C++，如何用指针数组进行快速排序？

Answer 1

这是一个利用指针数组进行快速排序的例子，希望对你有所帮助。
快速排序
快速排序是目前使用的较好的排序算法.它是由C.A.Hoare发明并命名的.他是这样操作的:先要在排序的数中选出作为一个比较标准的数,然后把余下的数都与它做大小比较,凡比他大的数都放在他的一侧,而比他小的数都放在另一侧,经过一遍比较后,实际上已经确定了这个数的最终位置.然后对他们2侧的数据在分别进行上面的操作.例如数据:
5 8 1 9 6 3 4 0 7 2
首先选择中间的数6作为比较数,然后逐个比较其他的数,5<6,不交换,8<6,记住8的位置,再从后面向前比较,2<6,次序不对,这时8与2互换.得到:
5 2 1 9 6 3 4 0 7 8
再从刚换完的下一个位置继续比较,1<6不换,9>6,记住位置,从后面比较,7>6,不换0<6,做9与0的互换!得到:
5 2 1 0 6 3 4 9 7 8
由于6前面的数都小于6,所以只对其后的数做比较,从4开始,由于4<6,则6与4互换,得到:
5 2 1 0 4 3 6 9 7 8
还剩4后的一个数没有比较,再与6比较,3<6,并且3在6左面,不必交换,于是一遍比较结束.这时确定了6的最终位置(6前面的都小于6,后面的都大于6).下面对2侧的数据分别重复上面的操作.

代码:

#include <stdio.h>

#define SIZE 10

void main()
{
void quick(int v[],int n);
int shuzu[SIZE];

for(int i=0;i<SIZE;i++)
{
scanf("%d",&shuzu[i]);
}

quick(shuzu,SIZE);

for(i=0;i<SIZE;i++)
{
printf("%4d",shuzu[i]);
}
}

void quick(int v[],int n)
{
void qs(int v[],int left,int right);
qs(v,0,n-1);
}

void qs(int v[],int left,int right)
{
int i,j,x,temp;
i=left; //左侧位置
j=right; //右侧位置
x=v[(left+right)/2]; //取一个比较数

while(i<j)
{
while(v[i]<x && i<right)
{
i++; //跳过左侧比x小的值
}
while(v[j]>x && j>left)
{
j--; //跳过右侧比x大的值
}
if(i<=j)
{
temp=v[i];
v[i]=v[j];
v[j]=temp;
//移动位置
i++;
j--;
}
}
//左侧继续排序
if(left<j)
qs(v,left,j);
//右侧继续排序
if(i<right)
qs(v,i,right);

}

指针函数部分如下:

//仅仅写函数部分

void quick(int *v,int n)
{
void qs(int *v,int *m);

qs(v,v+n-1);
}
void qs(int *v,int *m)
{
int *x,*left,*right;

int temp; //申明为整数

left=v;
right=m;
x=v+(m-v)/2;

while(left<right)
{
while(left<x && left<right) //排除左侧小于比较数
{
left++;
}
while(right>x && right>left) //排除右侧大于比较数
{
right--;
}

if(right>=left) //此句说明指针的位置左右比较
{

temp=*left; //互相交换数值.
*left=*right;
*right=*temp;

left++; //再次移动指针??????从新进入while的外层循环
right--;
}

if(v<right)
qs(v,right);
if(left<m)
qs(left,m); //右侧排序

}
}