菜鸟提问 c语言关于快速排序

Question

#include<stdio.h>
#include<stdlib.h>
void quicksort(int R[],int s,int t)
{
int i=s,j=t;
int temp;
if(s<t)
{
temp=R[s];
while(i!=j)
{
while(j>i && R[j]>temp)
j--;
while(i<j && R[i]<temp)
i++;
R[j]^=R[i];
R[i]^=R[j];
R[j]^=R[i];
}
R[i]=temp;
quicksort(R,s,i-1);
quicksort(R,i+1,t);
}
}
int main()
{
int i;
int a[]={5,3,2,1,9,8,7,4,5};
quicksort(a,0,sizeof(a)/sizeof(int)-1);
for(i=0;i<sizeof(a)/sizeof(int);i++)
printf("%d ",*(a+i));
system("pause");
}
当数组中有重复的数字时，就排不出来了，只有数组中数字都不一样时排出的结果才正确。哪位高手能帮忙修正一下。
如果能给出快速排序的非递归代码就太感谢了，我会再加分的。
由于小弟我刚接触C语言没多久，希望能解释的浅显点。十分感谢！！！！

Answer 1

其实，最想说明的是那段交换的代码
R[j]^=R[i];
R[i]^=R[j];
R[j]^=R[i];
一定要排除 i==j 的情况。即自己与自己交换的情况。
如：
a=9;
a^=a;/*a=0*/
a^=a;/*a=0*/
a^=a;/*a=0*/
a就不再是10了。

#include<stdio.h>
#include<stdlib.h>
void quicksort(int R[],int s,int t)
{
int i,j;
int temp;
if(s<t)
{
temp=R[s];/*选第一个数作为参照*/
/*while(i!=j)不要用这种方法判定循环结束，万一i==j-1，i++，j--后 i〉j了，！=这个条件就救不了你了*/
for(i=s+1,j=t;i<=j;i++,j--)/*不包括参照数，进行左右阵营站队*/
{
while(j>i && R[j]>=temp)/*R[j]>=temp不要 = 也行，加了更好，毕竟相等的无论站左站右，哪边都无所谓*/
j--;
while(i<j && R[i]<=temp)
i++;
if(i!=j){/*i千万不能等于j*/
R[j]^=R[i];
R[i]^=R[j];
R[j]^=R[i];
}
}
i--;
if(R[s]<R[i])i--;/*调整i的值，使i指向最后一个小于等于参照数的位置*/
/*将参照数 与 最后一个小于等于参照数的数进行交换，这样就真正把左右两个阵营分开了*/
R[s]=R[i];
R[i]=temp;
quicksort(R,s,i-1);
quicksort(R,i+1,t);
}
}
int main(void)
{
int i;
int a[]={5,3,2,1,9,8,7,4,5};
quicksort(a,0,sizeof(a)/sizeof(int)-1);
for(i=0;i<sizeof(a)/sizeof(int);i++)
printf("%d ",*(a+i));
return 0;
}

Answer 2

R[j]^=R[i];
R[i]^=R[j];
R[j]^=R[i];
你的代码里面R[i]^，R[j]^从何而来？不理解，不好改。
快速排序作为c语言中速度最快的一种排序，肯定能处理数字相同的情况，而且快速排序肯定是用递归算法。你的问题是算法，这里有个带注释的快速排序，win-tc和Dev-c++下运行通过。
#include <stdio.h>
#include <conio.h>
#define MAX 255
int R[MAX];

int Partition(int i,int j)
{/* 调用Partition(low，high)时，对R[low..high]做划分，*/
/* 并返回基准记录的位置 */
int pivot=R[i]; /* 用区间的第1个记录作为基准 */
while(i<j)
{ /* 从区间两端交替向中间扫描，直至i=j为止 */
while(i<j&&R[j]>=pivot) /* pivot相当于在位置i上 */
j--; /* 从右向左扫描，查找第1个关键字小于pivot.key的记录R[j] */
if(i<j) /* 表示找到的R[j]的关键字<pivot.key */
R[i++]=R[j]; /* 相当于交换R[i]和R[j]，交换后i指针加1 */
while(i<j&&R[i]<=pivot) /* pivot相当于在位置j上*/
i++; /* 从左向右扫描，查找第1个关键字大于pivot.key的记录R[i] */
if(i<j) /* 表示找到了R[i]，使R[i].key>pivot.key */
R[j--]=R[i]; /* 相当于交换R[i]和R[j]，交换后j指针减1 */
}
R[i]=pivot; /* 基准记录已被最后定位*/
return i;
}

void Quick_Sort(int low,int high) /* 对R[low..high]快速排序 */
{ int pivotpos; /* 划分后的基准记录的位置 */
if(low<high)
{/* 仅当区间长度大于1时才须排序 */
pivotpos=Partition(low,high); /* 对R[low..high]做划分 */
Quick_Sort(low,pivotpos-1); /* 对左区间递归排序 */
Quick_Sort(pivotpos+1,high); /* 对右区间递归排序 */
}
}

main()
{int i,n;
clrscr();
puts("Please input total element number of the sequence:");
scanf("%d",&n);
if(n<=0||n>MAX)
{ printf("n must more than 0 and less than %d.\n",MAX);
exit(0);
}
puts("Please input the elements one by one:");
for(i=1;i<=n;i++)
scanf("%d",&R[i]);
puts("The sequence you input is:");
for(i=1;i<=n;i++)
printf("%4d",R[i]);
Quick_Sort(1,n);
puts("\nThe sequence after quick_sort is:");
for(i=1;i<=n;i++)
printf("%4d",R[i]);
puts("\n Press any key to quit...");
getch();
}

Answer 3

#include<stdio.h>
#include<stdlib.h>

void swap(int &a,int &b){ //交换两个数
int temp=a;
a=b;
b=temp;
}
void quicksort(int R[],int s,int t)
{
int i=s,j=t;
int temp;
if(s<t)
{
temp=R[s];
while(i<j) //while(i!=j)
{
while(j>i && R[j]>=temp) //改成等号
j--;
while(i<j && R[i]<=temp)
i++;
swap(R[i],R[j]); //交换,你是想交换吧，虽然可以通过异或交换，但难以理解.
}
R[s]=R[i]; //增加的，交换中间数和第一个数
R[i]=temp;
quicksort(R,s,i-1);
quicksort(R,i+1,t);
}
}
int main()
{
int i;
int a[]={5,3,2,1,9,8,7,4,5};
int n = sizeof(a)/sizeof(int);
quicksort(a,0,n-1);
for(i=0;i<n;i++)
printf("%d ",*(a+i));
// system("pause");
return 1;
}

Answer 4

R[j]^=R[i];
R[i]^=R[j];
R[j]^=R[i];

就是交换R[i]和R[j]