自己写的快速排序算法，可以执行，但是结果有问题。。。求高手帮看。。。急求

Question

template<class Elem>
void qsort(Elem A[], int i, int j) { //Quicksort
if(j <= i)return;
int pivotindex = (j+i)/2;
int K=i;
for(int n=i; n<=j; n++)
if(A[n] < A[pivotindex])
K++;
Swap(A[pivotindex], A[K]);
printArray(A,20);
int i1 = i;
int i2 = K+1;
while(i1<K && i2<=j){
if(A[i1] > A[K]){
while(i2<=j){
if(A[i2] < A[K]){
Swap(A[i1], A[i2]);
printArray(A, 20);
i2++;
break;
}
i2++;
}
}
i1++;
}
qsort(A, i, K-1);
qsort(A, K+1, j);
}

Answer 1

我写了一个,不过没考虑有相等元素的情况:
void tqsort(int A[],int i,int j)
{
if(j <= i)
return;
int key = A[i],parami = i,paramj = j;
while(i != j)
{
if(A[i] < key) //左指针小于关键字则右移
i++;
else if(A[j] > key) //右指针大于关键字则左移
j--;
else //可以交换
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
tqsort(A,parami,i-1);
tqsort(A,j+1,paramj);
}

追问

我那个有什么问题能帮看一下么。。。而且是有时能有正确结果，有时又不能。。。我使用随机数组测试的

追答

你的排序思路是什么呢,你的代码我没看太懂
for(int n=i; n<=j; n++)
if(A[n] < A[pivotindex])
K++;
Swap(A[pivotindex], A[K]);
这里为什么要交换一次?

快速排序应当是指针从两端向中间移动,最后关键字位于两部分的中间,这样关键字左边的值都比关键字小,右边的都比关键字大.你的算法先确定了关键字的位置,这样不能确保将数列分成左小右大的两部分.

追问

我是先确定其位置，然后将比关键字小的都放左边，其余放右边。

追答

又看了看,你的思路应该没有问题,只是也没有考虑有重复元素的情况.

追问

重复元素情况？我明白了。。。谢谢提醒。。。