1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
| #include <iostream> #include <cstdio> #include <ctime> #include <cstdlib> using namespace std;
int n, a[100010];
void swap(int &a, int &b) { int tmp = a; a = b; b = tmp; }
void insertSort(int a[], int left, int right) { for (int i = left + 1; i <= right; i++) for (int j = i; j > 0 && a[j] < a[j-1]; j--) swap(a[j], a[j-1]); }
void quickSort(int a[], int left, int right) { if (left >= right) return; if (right - left + 1 < 10) { insertSort(a, left, right); return; } int i = left, j = right, k, flag = 0, pivot = rand() % (right - left + 1) + left; swap(a[left], a[pivot]); while (i < j) { while (j > i && a[j] >= a[left]) { if (a[j] == a[left]) { for (k = j-1; k > i; k--) if (a[k] != a[j]) { swap(a[k], a[j]); break; } if (k == i) { if (a[left] >= a[i]) swap(a[left], a[i]); else { swap(a[i], a[j]); swap(a[left], a[i-1]); i--; j--; } flag = 1; break; } else continue; } j--; } if (flag) break; while (i < j && a[i] <= a[left]) { if (a[i] == a[left] && i != left) { for (k = i+1; k < j; k++) { if (a[k] != a[i]) { swap(a[k], a[i]); break; } } if (k == j) { swap(a[left], a[j]); flag = 1; break; } else continue; } i++; } if (flag) break; swap(a[i], (i == j) ? a[left] : a[j]); } quickSort(a, left, i-1); quickSort(a, j+1, right); }
int main() { srand((int)time(NULL)); 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-1; i++) printf("%d ", a[i]); printf("%d\n", a[n-1]); return 0; }
|