下面这个程序时快速排序的实现,不知道哪儿出有关问题,求指教
下面这个程序时快速排序的实现,不知道哪儿出问题,求指教?
这个快速排序为什么不对呢?着重看下QSort这个函数,不知道为什么两种写法,结果会不一样?
------解决思路----------------------
具体的实现方法没看
while (low < high)
{
pivot = Partition(a,low,high);
// QSort(a,low,pivot);
// low = pivot+1;
/****如果按照上面两句就是对的,但如果换成下面两行代码就不对,这有什么区别呢?****/
QSort(a,low,pivot);
QSort(a,pivot+1,high); //使用下面这个不是在while(1) 中么?
}
------解决思路----------------------
while (low < high) low和high如果都不变,这个语句没法退出,既然是递归实现,这个while就没必要,你要while就不要递归。
------解决思路----------------------
int swap(int *a, int s, int t)
{
int temp = a[s];
a[s] = a[t];
a[t] = temp;
}
int Partition(int *a, int low, int high)
{
int pivotkeydata,i,j,temp;
int m = low + (high - low)/2;
pivotkeydata = a[m];
i = low;
j = high;
while(i<j)
{
while(i<j && a[j] >= pivotkeydata)
j--;
swap(a,i,j);
while(i<j && a[i] <= pivotkeydata)
i++;
swap(a,i,j);
}
return i;
}
int QSort(int *a, int low, int high)
{
int pivot;
while (low < high)
{
pivot = Partition(a,low,high);
// QSort(a,low,pivot);
// low = pivot+1;
/****如果按照上面两句就是对的,但如果换成下面两行代码就不对,这有什么区别呢?****/
QSort(a,low,pivot);
QSort(a,pivot+1,high);
}
return 0;
}
int quickSort(int *a, int n)
{
QSort(a,0,n-1);
return 0;
}
这个快速排序为什么不对呢?着重看下QSort这个函数,不知道为什么两种写法,结果会不一样?
------解决思路----------------------
具体的实现方法没看
while (low < high)
{
pivot = Partition(a,low,high);
// QSort(a,low,pivot);
// low = pivot+1;
/****如果按照上面两句就是对的,但如果换成下面两行代码就不对,这有什么区别呢?****/
QSort(a,low,pivot);
QSort(a,pivot+1,high); //使用下面这个不是在while(1) 中么?
}
------解决思路----------------------
while (low < high) low和high如果都不变,这个语句没法退出,既然是递归实现,这个while就没必要,你要while就不要递归。
------解决思路----------------------
int QSort(int *a, int low, int high)
{
int pivot;
while (low < high)
{
pivot = Partition(a,low,high);
// QSort(a,low,pivot);
// low = pivot+1;
/****如果按照上面两句就是对的,但如果换成下面两行代码就不对,这有什么区别呢?****/
/*答:上面两句每执行一次while循环,QSort函数只执行一次,low位置改变一次,下面两行要执行QSort函数两次,low位置改变一次*/
QSort(a,low,pivot);
QSort(a,pivot+1,high);
}
return 0;
}