快速排序的递归算法问题？
小弟最近学数据结构学到了快速排序,在上机试验时,在给出的两个排序函数下,却始终写不对主函数,望各位大虾指点迷津,最好能够给出主函数原码!!函数如下:
#include<stdio.h>
void quickpass(int r[6],int h,int p,int i)
{
int j,x;
i=h;j=p;x=r[i];/*置初值*/
while(i<j)
{
while((r[j]>=x)&&(i<j))
j--; /*自尾端进行比较*/
if(i<j)
{
r[i]=r[j];i++;/*将r[j]<x的记录移至i所指位置*/
while((r[i]<=x)&&(i<j);
i++;/*自首端进行比较*/
if(i<j)
{
r[j]=r[i];j--;/*r[i]>x的记录移到j所指位置*/
}
}
}
r[i]=x;/*将X移到正确位置*/
}
void quicksort(int r[6],int s,int t)/*用递归算法进行快速排序*/
{
if(s<t)
{
quickpass(r,s,t,i);
quicksort(r,s,i-1);
quicksort(r,i+1,t);
}
}
void main()
{
/*如何调用递归函数quicksort*/
}
问题点数：50、回复次数：4Top
1 楼ylbug（臭虫）回复于 2002-08-26 18:37:55 得分 0
quicksort函数中，i是什么东东？Top
2 楼lizhongkun（泛型）回复于 2002-08-26 19:06:14 得分 25
#include<stdio.h>
void quickpass(int r[],int low,int h)
{
r[0]=r[low];
pivotkey=r[low].key;/*置初值*/
while(i<j)
{
while(low<h&&r[h].key>=pivotkey)
h--; /*自尾端进行比较*/
r[low++]=r[h];
while(low<h&&r[low].key<=pivotkey)
++low;
r[h--]=r[low];
}
r[low]=r[0];
returnlow;
}
void quicksort(int r[],int s,int t)/*用递归算法进行快速排序*/
{
if(s<t-1)
{
pivot=quickpass(r,s,t,i);
quicksort(r,s, pivot-1);
quicksort(r, pivot+1,t);
}
}
void main()
{ int^^^^^^;
~~~~~~~~~~~~~~
/*如何调用递归函数quicksort*/
void quicksort( int b[],low,high);
}
Top
3 楼wu4long（）回复于 2002-08-26 19:22:14 得分 25
#include<stdio.h>
//这里我设成quickpass（）的返回值为INT，因为我猜你的意思是返回当前快速插入最后的位置，如果用int i作为函数的参数，则这是传值，而不会改变外面的值。说的清楚一点，函数参数传入到函数中时，做了一个拷贝，而外面的int i没有调用。所以为了达到你的目的，我让其返回一个int 值，当然还有方法是传入int *i。
int quickpass(int r[6],int h,int p)
{
int j,x,i;
i=h;j=p;x=r[i];/*置初值*/
while(i<j)
{
while((r[j]>=x)&&(i<j))
j--; /*自尾端进行比较*/
if(i<j)
{
r[i]=r[j];i++;/*将r[j]<x的记录移至i所指位置*/
while((r[i]<=x)&&(i<j))
i++;/*自首端进行比较*/
if(i<j)
{
r[j]=r[i];j--;/*r[i]>x的记录移到j所指位置*/
}
}
}
r[i]=x;/*将X移到正确位置*/
return i;
}
void quicksort(int r[6],int s,int t)/*用递归算法进行快速排序*/
{
int i=0;
if(s<t)
{
i=quickpass(r,s,t);
quicksort(r,s,i-1);
quicksort(r,i+1,t);
}
}
void main()
{
/*如何调用递归函数quicksort*/
int r[6]={1,90,23,43,34,44};
int i=0;
quicksort(r,0,5);
for(i=0;i<6;i++)
printf("%d\t",r[i]);
}
Top
4 楼visiond（vision）回复于 2002-09-15 17:48:27 得分 0
C++Primer上的SAMPLE
#ifndef ALGO_C
#define ALGO_C
template <class Type>
Type min( Type a, Type b ) {
return a < b ? a : b;
}
template <class elemType>
void swap( Array<elemType> &array, int i, int j )
{
elemType tmp = array[ i ];
array[ i ] = array[ j ];
array[ j ] = tmp;
}
template <class elemType>
void sort( Array<elemType> &array, int low, int high ) {
if ( low < high ) {
int lo = low;
int hi = high + 1;
elemType elem = array[lo];
for (;;) {
while ( min( array[++lo], elem ) != elem && lo < high ) ;
while ( min( array[--hi], elem ) == elem && hi > low ) ;
if (lo < hi)
swap( array, lo, hi );
else break;
}
swap( array, low, hi );
sort( array, low, hi-1 );
sort( array, hi+1, high );
}
}
template <class elemType>
void display( Array<elemType> &array )
{ // display format: < 0 1 2 3 4 5 >
cout << "< ";
for ( int ix = 0; ix < array.size(); ++ix )
cout << array[ix] << " ";
cout << ">\n";
}
#endif
Top
