点击查看代码
//Quick sort
#include<iostream>
using namespace std;
int partition(int A[],int start,int end) {
int pivot = A[end];//默认选取末尾为主元
int pIndex = start;//分区索引初始化
for (int i = start; i < end; i++) {//从索引start开始扫描
if (A[i] < pivot) {
int temp = A[i];
A[i] = A[pIndex];
A[pIndex] = temp;
pIndex++;
}//比主元小的元素全交换在分区索引左边,分区索引右移则A[pIndex]比A[end]大(或相等)
}
int temp = A[end];
A[end] = A[pIndex];
A[pIndex] = temp;//交换后分区索引右边全比主元大或相等
return pIndex;
}
int randomisedpartition(int A[], int start, int end) {
srand(time(0));
int random = (rand() % (end - start + 1)) + start;
int temp = A[end];
A[end] = A[random];
A[random] = temp;//start与end间随机抽取元素作为新end
return partition(A, start, end);//返回分区索引
}
void quicksort(int A[], int start,int end) {
if (start >= end) return;//中止条件
int pIndex = randomisedpartition(A, start, end);//建立分区并返回分区索引
quicksort(A, start, pIndex - 1);//分区索引左侧排序
quicksort(A, pIndex+1,end);//分区索引右侧排序
}//not stable
//average case time complexity:O(nlogn) by using random pIndex
//worst case time complexity:O(n^2)
//average case space complexity:O(logn) by using random pIndex
//worst case space complexity:O(n)
int main() {
int A[] = { 2,7,4,1,5,3 };
quicksort(A, 0,5);
for (int i = 0; i < 6; i++) cout << A[i] << " ";
cout << endl;
}