快速排序(QuickSort)是对起泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
假设待排序的序列为{ L.r[s],L.r〔s+l],...,L.r[t]} ,首先任意选取一个记录(通常可选第一个记录L.r[s])作为枢轴(或支点)(pivot),然后按下述原则重新排列其余记录:将所有关键字较它小的记录都安置在它的位置之前,将所有关键字较它大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所落的位置i作分界线,将序列{L.r[s],...,L.r[t]}分割成两个子序列{L.r[s],L.r[s+l],...,L.r[i-1]}和{L.r[i+1],L.r[i+2],...,L.r[t]}。这个过程称做一趟快速排序(或一次划分)。
一趟快速排序的具体做法是:附设两个指针 low 和 high ,它们的初值分别为 low 和high ,设枢轴记录的关键字为 pivotkey ,则首先从 high 所指位置起向前搜索找到第一个关键宇小于 pivotkey 的记录和枢轴记录互相交换,然后从 low 所指位置起向后搜索,找到第一个关键宇大于 pivotkey 的记录和枢轴记录互相交换,重复这两步直至 low=high为止。
#include <iostream>
#define SPACE 0x100
using namespace std;
struct Data
{
int key;
};
struct SqList
{
Data r[SPACE];
int length;
};
int Partition(SqList &L, int low, int high)
{
// 交换顺序表 L 中子表 L.r[low .. high].key的记录,使枢轴记录到位,并返回其所在位置,此时
// 在它之前(后)的记录均不大(小)于它。
int pivotkey = L.r[low].key; // 用子表的第一个记录作枢轴记录
Data temp;
// 从表的两端交替地向中间扫描
while (low < high)
{
while (low < high && L.r[high].key >= pivotkey)
{
--high;
}
// 将比枢轴记录小的记录交换到低端
temp = L.r[high];
L.r[high] = L.r[low];
L.r[low] = temp;
while (low < high && L.r[low].key <= pivotkey)
{
++low;
}
// 将比枢轴记录大的记录交换到高端
temp = L.r[high];
L.r[high] = L.r[low];
L.r[low] = temp;
}
return low; //返回枢轴所在位置
}
void print(SqList &L, int low, int high)
{
cout << "[ ";
for (int i = low; i <= high; i++)
{
cout << L.r[i].key << ", ";
}
cout << "]" << endl;
}
int main()
{
SqList list = {NULL, 74, 99, 86, 95, 85, 29, 37, 4, 7, 34};
list.length = 10;
print(list, 1, list.length);
int result = Partition(list, 1, list.length);
print(list, 1, list.length);
return 0;
}运行结果如下：
[ 74, 99, 86, 95, 85, 29, 37, 4, 7, 34, ]
[ 34, 7, 4, 37, 29, 74, 85, 95, 86, 99, ]具体实现上述算法时,每交换一对记录需进行 3 次记录移动(赋值)的操作。而实际上,在排序过程中对枢轴记录的赋值是多余的,因为只有在一趟排序结束时,即 low=high 的位置才是枢轴记录的最后位置。由此可改写上述算法,先将枢轴记录暂存在 r[O]的位置上,排序过程中只作 r[low]或 r[high]的单向移动,直至一趟排序结束后再将枢轴记录移至正确位置上。
#include <iostream>
#define SPACE 0x100
using namespace std;
struct Data
{
int key;
};
struct SqList
{
Data r[SPACE];
int length;
};
int Partition(SqList &L, int low, int high)
{
// 交换顺序表 L 中子表 L.r[low .. high].key的记录,使枢轴记录到位,并返回其所在位置,此时
// 在它之前(后)的记录均不大(小)于它。
L.r[0] = L.r[low]; // 用子表的第一个记录作枢轴记录
int pivotkey = L.r[low].key; // 枢轴记录关键字
// 从表的两端交替地向中间扫描
while (low < high)
{
while (low < high && L.r[high].key >= pivotkey)
{
--high;
}
// 将比枢轴记录小的记录交换到低端
L.r[low] = L.r[high];
while (low < high && L.r[low].key <= pivotkey)
{
++low;
}
// 将比枢轴记录大的记录交换到高端
L.r[high] = L.r[low];
}
L.r[low] = L.r[0]; // 枢轴记录到位
return low; //返回枢轴所在位置
}
void print(SqList &L, int low, int high)
{
cout << "[ ";
for (int i = low; i <= high; i++)
{
cout << L.r[i].key << ", ";
}
cout << "]" << endl;
}
int main()
{
SqList list = {NULL, 74, 99, 86, 95, 85, 29, 37, 4, 7, 34};
list.length = 10;
print(list, 1, list.length);
int result = Partition(list, 1, list.length);
print(list, 1, list.length);
return 0;
}
运行结果如下：
[ 74, 99, 86, 95, 85, 29, 37, 4, 7, 34, ]
[ 34, 7, 4, 37, 29, 74, 85, 95, 86, 99, ]整个快速排序的过程可递归进行。若待排序列中只有一个记录,显然已有序,否则进行一趟快速排序后再分别对分割所得的两个子序列进行快速排序。
#include <iostream>
#define SPACE 0x100
using namespace std;
struct Data
{
int key;
};
struct SqList
{
Data r[SPACE];
int length;
};
int Partition(SqList &L, int low, int high)
{
// 交换顺序表 L 中子表 L.r[low .. high].key的记录,使枢轴记录到位,并返回其所在位置,此时
// 在它之前(后)的记录均不大(小)于它。
L.r[0] = L.r[low]; // 用子表的第一个记录作枢轴记录
int pivotkey = L.r[low].key; // 枢轴记录关键字
// 从表的两端交替地向中间扫描
while (low < high)
{
while (low < high && L.r[high].key >= pivotkey)
{
--high;
}
// 将比枢轴记录小的记录交换到低端
L.r[low] = L.r[high];
while (low < high && L.r[low].key <= pivotkey)
{
++low;
}
// 将比枢轴记录大的记录交换到高端
L.r[high] = L.r[low];
}
L.r[low] = L.r[0]; // 枢轴记录到位
return low; //返回枢轴所在位置
}
void QSort(SqList &L, int low, int high)
{
// 对顺序表 L 中的子序列 L.r[low .. high]作快速排序
if (low < high) // 长度大于 1
{
int pivotloc = Partition(L, low, high); // 将 L.r[low .. high]一分为二
QSort(L, low, pivotloc - 1); // 对低子表递归排序, pivotloc 是枢输位置
QSort(L, pivotloc + 1, high); // 对商子表递归排序
}
}
void QuickSort(SqList &L)
{
// 对顺序表 L 作快速排序。
QSort(L, 1, L.length);
}
void print(SqList &L, int low, int high)
{
cout << "[ ";
for (int i = low; i <= high; i++)
{
cout << L.r[i].key << ", ";
}
cout << "]" << endl;
}
int main()
{
SqList list = {NULL, 74, 99, 86, 95, 85, 29, 37, 4, 7, 34};
list.length = 10;
print(list, 1, list.length);
QuickSort(list);
print(list, 1, list.length);
}运行结果如下：
[ 74, 99, 86, 95, 85, 29, 37, 4, 7, 34, ]
[ 4, 7, 29, 34, 37, 74, 85, 86, 95, 99, ]快速排序的平均时间为 Tavg(n) =knlnn , 其中 n 为待排序序列中记录的个数, k 为某个常数,经验证明,在所有同数量级的此类(先进的〉排序方法中,快速排序的常数因子 k 最小。因此,就平均时间而言,快速排序是目前被认为是最好的一种内部排序方法。
通常,快速排序被认为是,在所有同数量级(O(nlogn))的排序方法中,其平均性能最好。但是,若初始记录序列按关键字有序或基本有序时,快速排序将蜕化为起泡排序（冒泡排序）,其时间复杂度为 O(n2)。
快速排序的关键字比较次数与元素初始排列次序是有关系的
北京邮电大学 2016 年硕士研究生入学考试试题就考到了这个，原因是在进行二分递归的时候，如果其中有一边长度为1的话，则在算法中是不会进行比较的，具体原因还是看个人怎么理解。举个例子：
#include <iostream>
#define SPACE 0x100
#define ADD_FIX
using namespace std;
int amount; //用于统计判断次数
struct Data
{
int key;
};
struct SqList
{
Data r[SPACE];
int length;
};
int Partition(SqList &L, int low, int high)
{
// 交换顺序表 L 中子表 L.r[low .. high].key的记录,使枢轴记录到位,并返回其所在位置,此时
// 在它之前(后)的记录均不大(小)于它。
L.r[0] = L.r[low]; // 用子表的第一个记录作枢轴记录
int pivotkey = L.r[low].key; // 枢轴记录关键字
// 从表的两端交替地向中间扫描
while (low < high)
{
while (++amount && low < high && L.r[high].key >= pivotkey)
{
--high;
}
// 将比枢轴记录小的记录交换到低端
L.r[low] = L.r[high];
#ifdef ADD_FIX // 无论是否中间判断一次，结果都是不同的
if (low == high)
{
break;
}
#endif
while (++amount && low < high && L.r[low].key <= pivotkey)
{
++low;
}
// 将比枢轴记录大的记录交换到高端
L.r[high] = L.r[low];
}
L.r[low] = L.r[0]; // 枢轴记录到位
return low; //返回枢轴所在位置
}
void QSort(SqList &L, int low, int high)
{
// 对顺序表 L 中的子序列 L.r[low .. high]作快速排序
if (low < high) // 长度大于 1
{
int pivotloc = Partition(L, low, high); // 将 L.r[low .. high]一分为二
QSort(L, low, pivotloc - 1); // 对低子表递归排序, pivotloc 是枢输位置
QSort(L, pivotloc + 1, high); // 对商子表递归排序
}
}
void QuickSort(SqList &L)
{
// 对顺序表 L 作快速排序。
QSort(L, 1, L.length);
}
void print(SqList &L, int low, int high)
{
cout << "[ ";
for (int i = low; i <= high; i++)
{
cout << L.r[i].key << ", ";
}
cout << "]" << endl;
}
int main()
{
//list1 的结果
amount = 0;
SqList list1 = {NULL, 74, 99, 86, 95, 85, 29, 37, 4, 7, 34};
list1.length = 10;
print(list1, 1, list1.length);
QuickSort(list1);
print(list1, 1, list1.length);
cout << amount << endl
<< endl;
//list2 的结果
amount = 0;
SqList list2 = {NULL, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
list2.length = 10;
print(list2, 1, list2.length);
QuickSort(list2);
print(list2, 1, list2.length);
cout << amount << endl;
}
运行结果如下：
[ 74, 99, 86, 95, 85, 29, 37, 4, 7, 34, ]
[ 4, 7, 29, 34, 37, 74, 85, 86, 95, 99, ]
40
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ]
54资料来源：《数据结构》严蔚敏版
考研笔记，为了更好的自己