快速排序(随机化版本)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 100

void swap(int *x, int *y)
{
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

int RandomPivot(int p, int r)
{
	srand((int)time(NULL));
	
	return (rand()%(r-p+1) + p);      //返回一个p,r值之间的数
}

int Partition(int *A, int p, int r)
{
    int x, i, j;

    x = A[r];
    i = p - 1;
    for(j = p; j < r; j++)
    {
        if(A[j] <= x)
        {
            i++;
            swap(&A[i],&A[j]);
        }
    }

    swap(&A[i+1],&A[r]);

    return i+1;
}
int RandomPartition(int *A, int p, int r)
{
	int i;
	i = RandomPivot(p,r);
	swap(&A[r],&A[i]);
	return Partition(A,p,r);
}
void RandomQuickSort(int *A, int p, int r)
{
	int q;
	if(p < r)
	{
	q = RandomPartition(A,p,r);

	RandomQuickSort(A,p,q-1);
	RandomQuickSort(A,q+1,r);
	}
}


void PrintResult(int *A, int size)
{
	int i;
    for(i = 0; i < size; i++)
    {
        printf("%-2d",A[i]);
    }
    putchar('\n');
}

int main(void)
{
    int i, sum;		
    int A[SIZE];

    printf("输入需排序的元素个数(0-100): ");
    scanf("%d",&sum);
	
    printf("请输入%d个元素:\n",sum);

    for(i = 0; i < sum; i++)
    {
	scanf("%d",&A[i]);
    }

    RandomQuickSort(A,0,sum-1);
	
    printf("排序结果:\n");
    PrintResult(A,sum);

}