快速排序的随机化版本
#include<iostream> #include<ctime> using namespace std; void swap(int*a, int *b) { int *c = a; a = b; b = c; } int Partition(int *A, int p, int r) { int x = A[r]; int i = p - 1; for (int 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 Random(int M, int N) { return (int)((double)rand() / (double)RAND_MAX*(N - M + 1) + M); } int Random_Partition(int *A, int p, int r) { int i = Random(p,r); swap(A[r],A[i]); return Partition(A, p, r); } void QuickSort(int *A, int p, int r) { if (p < r) { int q = Random_Partition(A, p, r); QuickSort(A, p, q - 1); QuickSort(A,q+1,r); } } int main() { int A[] = {2,8,7,1,3,5,6,4}; int N = sizeof A / sizeof A[0]; srand((int)time(0));//必须放在调用前,不可放到产生随机数的函数中 QuickSort(A, 0, N-1); for (int i = 0; i < N; i++) cout << A[i] << " "; cout << "\n"; return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。