快速排序
快速排序技术是通过将列表分为两部分来完成的。最初，通过划分算法选择枢轴元素。枢轴的左侧部分的值小于枢轴，右侧部分的值较大。分区后，将使用相同的过程对每个单独的列表进行分区。
快速排序技术的复杂性
时间复杂度：最佳情况和平均情况为O（nlogn），最坏情况为O（n^2）。
空间复杂度：O（logn）
输入输出
Input: The unsorted list: 90 45 22 11 22 50 Output: Array before Sorting: 90 45 22 11 22 50 Array after Sorting: 11 22 22 45 50 90
算法
分区（数组，下，上）
输入： 数据集数组，下边界和上边界
输出：枢轴位于正确的位置
Begin
pivot := array[lower]
start := lower and end := upper
while start < end do
while array[start] <= pivot AND start < end do
start := start +1
done
while array[end] > pivot do
end := end – 1
done
if start < end then
swap array[start] with array[end]
done
array[lower] := array[end]
array[end] := pivot
return end
EndquickSort（array，left，right
输入-数据数组以及数组的上下限
输出-排序的数组
Begin
if lower < right then
q = partition(arraym left, right)
quickSort(array, left, q-1)
quickSort(array, q+1, right)
End示例
#include<iostream>
using namespace std;
void swapping(int &a, int &b) { //swap the content of a and b
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
int partition(int *array, int lower, int upper) {
//Hoare分区技术以找到正确的枢轴位置
int pivot, start, end;
pivot = array[lower]; //first element as pivot
start = lower; end = upper;
while(start < end) {
while(array[start] <= pivot && start<end) {
start++; //start pointer moves to right
}
while(array[end] > pivot) {
end--; //end pointer moves to left
}
if(start < end) {
swap(array[start], array[end]); //swap smaller and bigger element
}
}
array[lower] = array[end];
array[end] = pivot;
return end;
}
void quickSort(int *array, int left, int right) {
int q;
if(left < right) {
q = partition(array, left, right);
quickSort(array, left, q-1); //sort left sub-array
quickSort(array, q+1, right); //sort right sub-array
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "输入元素：" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
quickSort(arr, 0, n-1); //(n-1) for last index
cout << "Array after Sorting: ";
display(arr, n);
}输出结果
Enter the number of elements: 6 输入元素： 90 45 22 11 22 50 Array before Sorting: 90 45 22 11 22 50 Array after Sorting: 11 22 22 45 50 90