递归过程:
/**************************************************\
函数功能:递归调用分解函数,进行快速排序
输入:原始数组、要对数组进行操作的起始和结束下标
输出:无
\**************************************************/
void QuickSort(int* Array,int n,int p,int r)
{
int q=0;
if(p<r)
{
q=Partition(Array,n,p,r);
QuickSort(Array,n,p,q-1);
QuickSort(Array,n,q+1,r);
}
}
完整实例:
#include<stdio.h>
int Partition(int*Array,int n,int p,int r);
void QuickSort(int* Array,int n,int p,int r);
void main()
{
int Array[8]={2,8,7,1,3,5,6,4};
int n=sizeof(Array)/sizeof(int);
int p=0;
int r=n-1;
QuickSort(Array,n,p,r);
for(int k=0;k<n;k++)
printf("%d ",Array[k]);
printf("\n");
}
/**************************************************\
函数功能:将原数组分成全大于和全小于x的两个子数组
输入:原始数组、要对数组进行操作的起始和结束下标
输出:x在数组中的位置
\**************************************************/
int Partition(int*Array,int n,int p,int r)
{
int x=Array[r];
int i=p-1;
int temp=0;
for(int j=p;j<=r-1;j++)
{
if(Array[j]<=x)
{
i++;
temp=Array[i];
Array[i]=Array[j];
Array[j]=temp;
}
}
temp=Array[i+1];
Array[i+1]=Array[r];
Array[r]=temp;
return i+1;
}
/**************************************************\
函数功能:递归调用分解函数,进行快速排序
输入:原始数组、要对数组进行操作的起始和结束下标
输出:无
\**************************************************/
void QuickSort(int* Array,int n,int p,int r)
{
int q=0;
if(p<r)
{
q=Partition(Array,n,p,r);
QuickSort(Array,n,p,q-1);
QuickSort(Array,n,q+1,r);
}
}
注意:我是在vs2008上运行的,与vc 6.0有点区别,主要是循环体中的循环变量的作用域,出错体现在循环变量的重复定义上。例如:在vs2008或vs2010上,程序为:
#include<stdio.h>
void main()
{
int i=0;
for(int i=0;i<5;i++)
printf("%d ",i);
}
则在VC 6.0上需改为:
#include<stdio.h>
void main()
{
int i=0;
for(i=0;i<5;i++)
printf("%d ",i);
}
原文:http://blog.csdn.net/tengweitw/article/details/9627659
作者:nineheadedbird