快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字比另一部记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
快速排序的平均时间复杂度为O(nlogn)。
// 快速排序
#include <stdio.h>
#include <malloc.h>
#define N 10 // 数组最大值
#define MAX_LENGTH_INSERT_SORT 7 // 用于快速排序时判断是否选用插入排序阙值
// 顺序表结构
typedef struct {
int value[N + 1]; // 顺序表中的值
int length; // 顺序表长度
} SqList;
/**
* 交换顺序表L中i和j元素的值
* @param L 顺序表
* @param i 元素值
* @param j 元素值
*/
void swap(SqList *L, int i, int j) {
int temp = L->value[i];
L->value[i] = L->value[j];
L->value[j] = temp;
}
/**
* 初始化顺序表
* @param L 顺序表
* @param d 存初始值的数组
*/
void InitSqList(SqList *L, int *d) {
int i;
for (i = 0; i < N; ++i) {
L->value[i + 1] = d[i];
}
L->length = N;
}
/**
* 遍历顺序表中元素的值
* @param L 顺序表元素
*/
void Print(SqList L) {
int i;
printf("顺序表中的值为：");
for (i = 1; i < L.length; i++) {
printf("%d, ", L.value[i]);
}
printf("%d", L.value[i]);
printf("\n");
}
/************** 快速排序 **************/
/**
* 对顺序表进行分割，使在关键字前面的元素都大于它，后面的元素都小于它
* @param L 顺序表
* @param low 起点下标
* @param high 终点下标
* @return 分割成两部分后，关键字的下标
*/
int Partition(SqList *L, int low, int high) {
int pivotkey; // 存储关键字
pivotkey = L->value[low]; // 设置关键字为最小值
while (low < high) { // 低位下标小于高位下标
// 低位下标小于高位下标，并且高位元素的值大于等于关键字
while (low < high && L->value[high] >= pivotkey) {
high--; // 高位下标向前移动
}
swap(L, low, high); // 将比关键字小的元素的值放到前面low的位置
// 低位下标小于高位下标，并且低位元素的值小于等于关键字
while (low < high && L->value[low] <= pivotkey) {
low++; // 低位向后移动
}
swap(L, low, high); // 将比关键字大的元素的值放到后面high的位置
}
return low; // 返回关键字的下标
}
/**
* 快速排序
* @param L 顺序表
* @param low 起点下标
* @param high 终点下标
*/
void QSort(SqList *L, int low, int high) {
int pivot; // 存储分割关键字下标
// 低位小于高位
if (low < high) {
pivot = Partition(L, low, high); // 将L->value[low..high]一分为二，获取关键字下标
QSort(L, low, pivot - 1); // 对前半部分递归排序
QSort(L, pivot + 1, high); // 对后半部分递归排序
}
}
/**
* 调用快速排序
* @param L 顺序表
*/
void QuickSort(SqList *L) {
QSort(L, 1, L->length); // 对整个顺序表进行快速排序
}
/**************************************/
/************** 快速排序（改进版） **************/
/**
* 对顺序表进行分割，使在关键字前面的元素都大于它，后面的元素都小于它
* @param L 顺序表
* @param low 起点下标
* @param high 终点下标
* @return 分割成两部分后，关键字的下标
*/
int Partition2(SqList *L, int low, int high) {
int pivotkey; // 存储关键字
int mid = low + (high - low) / 2; // 计算中间位置的下标
// 使用三数取中法获取更适合的关键字（排序最左边、中间、最右边位置的值，取中间的数）
if (L->value[low] > L->value[high]) {
swap(L, low, high); // 交换最左边和最右边元素，保证左边较小
}
if (L->value[mid] > L->value[high]) {
swap(L, mid, high); // 交换中间和最右边元素，保证中间较小
}
if (L->value[mid] < L->value[low]) {
swap(L, mid, low); // 交换中间和最左边元素，保证左边较小
}
pivotkey = L->value[low]; // 设置关键字为三个数中的最小值
L->value[0] = pivotkey; // 备份关键字到0下标位置
while (low < high) { // 低位下标小于高位下标
// 低位下标小于高位下标，并且高位元素的值大于等于关键字
while (low < high && L->value[high] >= pivotkey) {
high--; // 高位下标向前移动
}
L->value[low] = L->value[high]; // 将比关键字小的元素的值放到前面low的位置
// 低位下标小于高位下标，并且低位元素的值小于等于关键字
while (low < high && L->value[low] <= pivotkey) {
low++; // 低位向后移动
}
L->value[high] = L->value[low]; // 将比关键字大的元素的值放到后面high的位置
}
L->value[low] = L->value[0]; // 将关键字存到低下标位置
return low; // 返回关键字的下标
}
/**
* 直接插入排序
* @param L 顺序表
*/
void InsertSort(SqList *L) {
int i, j;
for (i = 2; i <= L->length; i++) {
// 后面的元素比前面元素小，需将L->value[i]插入有序子表
if (L->value[i] < L->value[i - 1]) {
L->value[0] = L->value[i]; // 设置哨兵
// 将有序子表中，比哨兵位置元素大的元素都向后移动一个位置
for (j = i - 1; L->value[j] > L->value[0]; j--) {
L->value[j + 1] = L->value[j];
}
// 将哨兵位置的元素插入正确的位置
L->value[j + 1] = L->value[0];
}
}
}
/**
* 快速排序（改进版）
* @param L 顺序表
* @param low 起点下标
* @param high 终点下标
*/
void QSort2(SqList *L, int low, int high) {
int pivot; //存储关键字
// 高低位之差大于指定值，调用快速排序
if ((high - low) > MAX_LENGTH_INSERT_SORT) {
// 低位下标小于高位下标
while (low < high) {
// 将L->value[low..high]一分为二，获取关键字下标
pivot = Partition2(L, low, high);
QSort2(L, low, pivot - 1); // 对前半部分进行递归排序
// QSort2(L, pivot + 1, high); // 对后半部分进行递归排序
low = pivot + 1; // 尾递归
}
} else { // 高低位元素之差过小，调用插入排序
InsertSort(L); // 插入排序
}
}
/**
* 调用快速排序（改进版）
* @param L 顺序表
*/
void QuickSort2(SqList *L) {
QSort2(L, 1, L->length); // 对整个顺序表进行快速排序
}
/************************************************/
int main() {
int d[N] = {50, 10, 90, 30, 70, 40, 80, 60, 20, 102}; // 存初始值的数组
SqList L; // 顺序表
InitSqList(&L, d); // 初始化顺序表
printf("在进行初始化之后");
Print(L); // 遍历顺序表
QuickSort(&L); // 对顺序表进行快速排序
printf("快速排序(普通)后");
Print(L); // 遍历顺序表
InitSqList(&L, d); // 初始化顺序表
QuickSort2(&L); // 对顺序表进行快速排序
printf("快速排序(改进版)");
Print(L); // 遍历顺序表
return 0;
}
运行结果
