原始QuickSort算法：
算法平均复杂度：[latex]\Theta(n\lg{n})[/latex]（一般情况下）
算法在最坏情况下的复杂度：[latex]\Theta(n^2)[/latex](在输入序列为排列好的数的情况下)
在实际应用中，快速排序算法通常比归并排序算法快三倍左右。
// 数组划分子程序
int Partition(int *data, int start, int end)
{
int key = data[start];
int i = start; // 小于等于key与大于key的元素的交界处
int temp;
for (int j=i+1; <=end; ++j)
{
if (data[j] <= key)
{
++i;
temp = data[j];
data[j] = data[i];
data[i] = temp;
}
}
// 将主元(pivot)移动到交界处
temp = data[i];
data[i] = data[start];
data[start] = temp;
return i;
}
// 快速排序
void QuickSort(int *data, int start, int end)
{
if (start < end) // 修改临界条件，使用其他快速排序方法可改善快速排序的性能
{
int partitionPos = Partition(data, start, end);
QuickSort(data, start, partitionPos-1);
QuickSort(data, partitionPos+1, end);
}
}优化的QuickSort算法：Randomized QuickSort
算法复杂度：[latex]\Theta(n\lg{n})[/latex]
为了避免出现最糟的情况：可随机选择主元pivot或者对输入序列进行随机排列。这里使用随机选择主元的方法。
这样的话：
1）运行时间不依赖与输入序列。
2) 没有特定的输入序列使的算法出现最差情况，最差情况仅由随机数产生器产生。
// 数组划分子程序
int RandomizedPartition(int *data, int start, int end)
{
// 随机选择主元
int temp;
int keyPos = (double)rand() / (RAND_MAX+1) * (end-start) + start;
temp = data[keyPos]; // 将主元与首个元素交换
data[keyPos] = data[start];
data[start] = temp;
// 标准划分过程
int key = data[start];
int i = start; // 小于等于key与大于key的元素的交界处
for (int j=i+1; j<=end; ++j)
{
if (data[j] <= key)
{
++i;
temp = data[j];
data[j] = data[i];
data[i] = temp;
}
}
// 将主元pivot移动到交界处
temp = data[i];
data[i] = data[start];
data[start] = temp;
return i;
}
// 核心递归程序
void RandomizedQuickSortCore(int *data, int start, int end)
{
if (start < end)
{
int partitionPos = RandomizedPartition(data, start, end);
RandomizedQuickSortCore(data, start, partitionPos-1);
RandomizedQuickSortCore(data, partitionPos+1, end);
}
}
// 随机化快速排序
void RandomizedQuickSort(int *data, int start, int end)
{
srand(time(0)); // 初始化随机数(仅初始化一次即可)
RandomizedQuickSortCore(data, start, end);
}