快速排序||随机划分

#include <cstdio> #include <cstdlib> #include <cmath> #include <ctime> #include <algorithm> using namespace std; const int maxn = 101; int Partition(int a[], int left, int right); void QuickSort(int a[], int left, int right); int RandPartition(int a[], int left, int right); int main() { srand((unsigned)time(NULL)); int n,a[maxn]; scanf("%d",&n); for(int i = 0; i < n; i++) { scanf("%d",&a[i]); } QuickSort(a, 0, n - 1); for(int i = 0; i < n; i++) { printf("%d",a[i]); if(i != n - 1) { printf(" "); } } return 0; } //划分 /*int Partition(int a[], int left, int right) { int temp = a[left]; while(left < right) { while(left < right && a[right] > temp) right--; a[left] = a[right]; while(left < right && a[left] <= temp) left++; a[right] = a[left]; } a[left] = temp; return left; } */ //快速排序 void QuickSort(int a[], int left, int right) { if(left < right) { int pos = RandPartition(a, left, right); QuickSort(a, left, pos - 1); QuickSort(a, pos + 1, right); } } //随机划分 int RandPartition(int a[], int left, int right) { int p = (int)round(1.0 * rand() / RAND_MAX * (right - left) + left); swap(a[left], a[p]); int temp = a[left]; while(left < right) { while(left < right && a[right] > temp) right--; a[left] = a[right]; while(left < right && a[left] < temp) left++; a[right] = a[left]; } a[left] = temp; return left; }