如果仅仅实现快速排序是不能排除输入的影响的，如果在最坏的情况下，快速排序的时间复杂度是 Θ(n2) ，如果是面试官出类似这一类排序的问题，例如要求时间复杂度为 Θ(nlgn) ,那么回答快排并不是正确答案！
#include <QCoreApplication> #include <iostream> #include <cstdlib> #include <ctime> using namespace std; void swap(int *a, int *b); int randomized_partition(int A[], int p, int r); int partition(int A[], int p, int r); void randomized_quicksort(int A[], int p, int r); int main(int argc, char *argv[]) { QCoreApplication a(argc, argv); int array[8] = {2, 8, 7, 1, 3, 5, 6, 4}; cout << "the unsorted array is :" << endl; for (int i = 0; i < 8; i++) { cout << array[i] << " "; } cout << endl; randomized_quicksort(array, 0, 7); cout << "the sorted array is : " << endl; for (int i = 0; i < 8; i++) { cout << array[i] << " "; } cout << endl; return a.exec(); } void swap(int *a, int *b)//交换两个变量 { int t; t = *a; *a = *b; *b = t; cout << "a = " << *a << " b " << *b << endl; } int randomized_partition(int A[], int p, int r) { int i = rand()%(r-p+1)+p;//随机数生成的方法，加上ctime，cstdlib两个头文件 swap(A[r], A[i]); return partition(A, p, r); } 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 = i+1; swap(A[i], A[j]); } } swap(A[i+1], A[r]); return i+1; } void randomized_quicksort(int A[], int p, int r) { if (p < r) { int q = randomized_partition(A, p, r); randomized_quicksort(A, p, q-1); randomized_quicksort(A, q+1, r); } }虽然当中犯了一个非常低级的错误，不过好在排查出来了。。。
