快速排序(quick sort)
Jimmy
posted @ 2011年10月21日 16:58
in Algorithm Basics
, 1210 阅读
#include <stdio.h>
#include <stdlib.h>
int partition(int *array, int p, int r)
{
int x, i, j;
int tmp;
x = array[r];
i = p - 1;
for(j=p; j<=r-1; j++)
{
if(array[j] <= x)
{
i++;
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
tmp = array[r];
array[r] = array[i+1];
array[i+1] = tmp;
return i+1;
}
void quickSort(int *array, int p, int r)
{
int q;
if(p < r)
{
q = partition(array, p, r);
quickSort(array, p, q-1);
quickSort(array, q+1, r);
}
}
int main()
{
int *array, n;
int i;
while(scanf("%d",&n) != EOF)
{
array = (int*)malloc(sizeof(int)*n);
for(i=0; i<n; i++)
scanf("%d", array+i);
quickSort(array, 0, n-1);
for(i=0; i<n; i++)
printf("%d ", array[i]);
printf("\n");
}
return 0;
}