C ++程序在给定复杂性约束下实现快速排序
快速分类基于分而治之。该算法的平均时间复杂度为O（n*log(n)），但最坏情况下的复杂度为O（n^2）。为了减少最坏情况的发生，此处使用随机化来实现Quicksort。
算法
分区（inta[]，intl，inth）
Begin
pivot = h
Index = l
start = l and end = h
while start < end do
while a[start] <= pivot AND start < end do
start = start +1
done
while a[end] > pivot do
end = end – 1
done
if start < end then
swap a[start] with a[end]
done
a[low] = a[end]
a[end] = pivot
return end
EndRandomPivotPartition（inta[]，intl，inth）
Begin n = rand() pivot = l + n%(h-l+1); Swap a[h] with a[pivot] return Partition(a, l, h) End
QuickSort（inta[]，intl，inth）
Begin
int pindex;
If (l<h)
pindex = RandomPivotPartition(a, l, h)
QuickSort(a, l, pindex-1)
QuickSort(a, pindex+1, h)
return 0
End范例程式码
#include<iostream>
#include<cstdlib>
using namespace std;
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int Partition(int a[], int l, int h) {
int pivot, index, i;
index = l;
pivot = h;
for(i = l; i < h; i++) {
if(a[i] < a[pivot]) {
swap(&a[i], &a[index]);
index++;
}
}
swap(&a[pivot], &a[index]);
return index;
}
int RandomPivotPartition(int a[], int l, int h) {
int pvt, n, temp;
n = rand();
pvt = l + n%(h-l+1);
swap(&a[h], &a[pvt]);
return Partition(a, l, h);
}
int QuickSort(int a[], int l, int h) {
int pindex;
if(l < h) {
pindex = RandomPivotPartition(a, l, h);
QuickSort(a, l, pindex-1);
QuickSort(a, pindex+1, h);
}
return 0;
}
int main() {
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;
int arr[n];
for(i = 0; i < n; i++) {
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}
QuickSort(arr, 0, n-1);
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}输出结果
Enter the number of data element to be sorted: 4 Enter element 1: 3 Enter element 2: 4 Enter element 3: 7 Enter element 4: 6 Sorted Data ->3->4->6->7