|
#include <stdio.h>
#include <stdlib.h>
int a[101],n;//全局变量定义
void quicksort(int left,int right)//写快速排序函数
{
int i,j,t,temp;
if(left>right)//如果左起数比右起数大,就返回主函数
return;
temp=a[left];//输入的数组a的最左边的数为基准数
i=left;//i是左边的数组a[]下标变量
j=right;//j是右边的数组a[]下标变量
while(i!=j)//当i不等于j时一直循环
{
while(a[j]>=temp && i<j)//当数组a右边的数大于基准数并且i小于j时不必交换
j--;//j-1,这样右边往左一格,当右边的数小于基准数或i大于j执行下一句(没搞十分明白
while(a[i]<=temp && i<j)//当左边的数小于基准数并且i小于j时
i++;//左边往右走
if(i<j)//上面的执行完后,程序必然找到左边的大于基准数的数,右边的小于基准数的数
//如果i小于j交换两个数
{
t=a[i];
a[i]=a[j];
a[j]=t;//交换两个数执行完后跳回循环头j继续向右,碰到比基准数小的数就会停下来
//此时i继续自加,当遇到j也就是i=j时每次都是j先动所以最后留的数必定小于基准数!
}
}
//当i=j时执行下面的语句
a[left]=a[i];
a[i]=temp;
//此时i应该等于j
quicksort(left,i-1);//left的实参在主函数里面被赋值为1
//现在数已经被分为两段,左边全是比基准数小的,还是从a[1]开始找,
//左边的数的最后一个是上个基准数的地址-1,a[i]i就是基准数的位置所以要减1
//递归调用快排函数,它调用了它自己。
quicksort(i+1,right);//右边的数全是比上个基准数大的。a[i]就是基准数位置
//a[i]+1就是右边的第一个数,把它的位置做实参赋给快排函数形参left,
//形参right的数值没变还是最后一个数。也就是主函数里面赋给它的n。总共有n个数
//所以最右边的一定是第n个数。
}
int main()
{
int i,j,t;
scanf("%d",&n);
for(i=1;i<n;i++)
scanf("%d",&a[i]);
quicksort(1,n);
for(i=1;i<=n;i++)
printf("%d ",a[i]);
system("pause");
return 0;
}
|
|