重庆分公司
重庆分公司，新征程启航
为企业提供网站建设、域名注册、服务器等服务
经典排序之快速排序-创新互联
一、概述
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，
按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。快速排序的关键点在于如何按照基准值划分区间。快速排序递归实现的框架（本文以升序排序为基础）：
本文名称：经典排序之快速排序-创新互联
URL网址：http://cqcxhl.com/article/dphghe.html
// 按照升序对a数组中[left, right)区间中的元素进行排序
void QuickSort(int* a, int left, int right) {
if (left+1>=right) {
return;
}
// 按照基准值对a数组的 [left, right)区间中的元素进行划分
int div = partion(a, left, right);
//以div为边界递归左右区间
QuickSort(a, left, div - 1);
QuickSort(a, div+1, right);
}
首先选取一个key值，一般选取最左或最右。当选最左为key值时需要R先移动，当R所在位置的数值小于key值时停下，L移动找到比key值大的位置，然后交换L和R的数值，重复以上操作直到L和R相遇。一趟排序完成后key值被放在了正确的位置即左子序列均小于key值，右子序列均大于key值。这里值得注意的是当key值选取最左端时需要R先移动，选取最右端时需要L先移动。这是因为相遇时的数值与后移动的一方有关，如果key值选左而L先移动那么就会将比key值大的数字交换到最左边，这不符合规则。hoare版本划分区间代码：
int Partion(int* a, int left, int right) {
int key = left;
while (left< right) {
while (left< right && a[right] >= a[key]) {
right--;
}
while (left< right && a[left]<= a[key]) {
left++;
}
swap(&a[left], &a[right]);
}
swap(&a[key], &a[left]);
return left;
}
挖坑法是hore法的一种变形 ，先将第一个数据存放在临时变量key中，形成一个坑位。R移动找到比key值小的就停下与坑位交换，L再移动找到比key值大的与坑位交换。相遇时将key值填入坑位。挖坑法划分区间代码：
int partion(int* a, int left, int right) {
int key = a[left];
int pivot = left;
while (left< right) {
while (left< right && a[right] >= key) {
right--;
}
a[pivot] = a[right];
pivot = right;
while (left< right && a[left]<= key) {
left++;
}
a[pivot] = a[left];
pivot = left;
}
a[pivot] = key;
return pivot;
}
初始时pre指向序列起始位置，cur指向其后。cur移动找到比key值小的时停下，交换cur的值和pre后一位置的值。cur继续移动重复操作直到越界。
int partion(int* a, int left, int right) {
int pre = left;
int key = left;
int cur = pre + 1;
while (cur<= right) {
if (a[cur]< a[key] && ++pre != cur) {
swap(&a[pre], &a[cur]);
}
cur++;
}
swap(&a[key], &a[pre]);
return pre;
}递归版本中每个创建的栈帧都保存了当前区间的left和right值，我们也可以利用栈这种数据结构存入待处理的区间，每次取出区间后按key值划分区间，并将形成的两个新区间压入栈中，当划分的区间内没有值时停止压栈，重复操作直到栈空。
//写的栈的代码就不列出
void QuickSortNonR(int* a, int left, int right) {
ST st;//创建栈
StackInit(&st);//初始化栈
//将左右区间值压入栈中
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st)) {
//取出栈中存放的左右区间值
int left=StackTop(&st);
StackPop(&st);
int right=StackTop(&st);
StackPop(&st);
//划分区间，前面已讲
int div = partion(a, left, right);
//区间内有值继续压入栈中
if (div + 1< right) {
StackPush(&st, right);
StackPush(&st, div+1);
}
if (left + 1< div) {
StackPush(&st, div-1);
StackPush(&st, left);
}
}
StackDestroy(&st);//销毁栈
}理想情况下快速排序的时间复杂度为O(n*logn),但是如果待排序的序列是有序的，每次划分区间时选择左值为key值，划分后左子区间都是是不存在的，此时时间复杂度变成了O(n^2).
解决方法：
（1）.随机选择key值，不推荐
（2）.三数取中，选择left、right、left+（right-left)/2,这三个位置的中间大小的数值做key值。
2.递归到小的子区间时，考虑使用插入排序与二叉树结构类似，当递归到最后几层时，大量的小区间调用了函数，代价较大。于是就有了小区间优化的概念。当区间的序列个数小于一定数时（这里取十），采用插入排序。
快速排序优化版本完整代码：
int FindMiddle(int* a, int left, int right) {
int middle = left+(right-left)/2;
if (a[right] >a[middle]) {
if (a[middle] >a[left]) {
return middle;
}
else {
return left;
}
}
else {
if (a[right] >a[left]) {
return right;
}
else {
return left;
}
}
}
//前后指针法划分区间
int partion(int* a, int left, int right) {
int mid = FindMiddle(a,left,right);//取中
swap(&a[left],&a[mid);//交换mid位置的值和left的值
int pre = left;
int key=left;
int cur = pre + 1;
while (cur<= right) {
if (a[cur]< a[key] && ++pre != cur) {
swap(&a[pre], &a[cur]);
}
cur++;
}
swap(&a[key], &a[pre]);
return pre;
}
void QuickSort(int* a, int left, int right) {
if (left+1>=right) {
return;
}
//小区间优化，区间内的个数小于10时采用插入排序
if(right-left<10){
InsertSort(a,right-left+1);
}else{
int div = partion(a, left, right);
QuickSort(a, left, div - 1);
QuickSort(a, div+1, right);
}
}特殊情况：当待排序序列为同一个值或者大量相同数值时，优化也不能解决此类问题，此时不建议采用快速排序。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文名称：经典排序之快速排序-创新互联
URL网址：http://cqcxhl.com/article/dphghe.html