#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); }