快速排序算法的思路及C代码实现
1. 概念
快速排序（Quick Sort)算法顾名思义，就是自诩排序速度最快的方法，大致就是利用冒泡排序改进而来，冒泡排序利用相邻的两个元素进行比较，这样一次交换只能消除一个逆序排列，而快排利用不相邻的两个元素进行比较，这样一次交换可能消除了多个逆序排列，这样也就节省了时间。
平均时间复杂度：O(nlog2n)
2. 算法思路
- ** **
Partition函数用于将一个【low...high】序列进行一趟排序，选取low为枢轴元素并保存，先从右往左检查比枢轴元素小的元素，没有的话继续往左找（high--，low<high)，直到找到并将其移到左边（low)，然后从左往右（low++，low<high）检查比枢轴元素大的元素，直到找到并将其移到右边。最终low==high时，说明已经将全部元素与枢轴比较过，此时满足左<枢轴<右。 Qsort函数调用Partition函数后，再递归调用Qsort分别对【low...枢轴-1】【枢轴+1...high】排序，直到low==high为止。
3. 完整代码参考（C语言）
// 堆排序c算法实现
#include <stdlib.h>
#define MAXSIZE 10 // 静态顺序表最大长度
typedef int ElemType; // 假设数据类型为int类
typedef struct { // 静态顺序表数据元素
ElemType data[MAXSIZE + 1]; // 数据项 [0]不放数据，用于保存枢轴元素
int length;
}SqList;
void initList(SqList* L) { // 初始化顺序表
L->length = MAXSIZE;
for (int i = 1;i <= L->length;i++) {
L->data[i] = rand(); // 随机初始化数据
}
}
void printData(SqList* L) {
for (int i = 1; i <= L->length; i++) {
printf("%d ", L->data[i]);
}
puts();
}
int Partition(SqList* L, int low, int high) { // 将给定的序列分割为左<根<右的二叉树（仅根部满足）
L->data[0] = L->data[low];
int pivotkey = L->data[0]; // 枢轴关键字
while (low < high) {
while (low < high && L->data[high] >= pivotkey) high--;
L->data[low] = L->data[high]; // 先从右往左检查，找到第一个小于枢轴的元素，将[1]的枢轴位置填补
while (low < high && L->data[low] <= pivotkey) low++;
L->data[high] = L->data[low]; // 此时，右部分空缺一个位置，从左往右检查找到一个大于枢轴的元素填补
}
L->data[low] = L->data[0]; // 此时，low == high且位置空缺，将枢轴元素补上
return low; // 返回当前序列的中心节点（根节点）
}
void QSort(SqList* L, int low, int high) { // 将[low...high]中的元素快速排序
if (low < high) { // 序列仅有一个元素时已经有序，跳过排序
int pivotloc = Partition(L, low, high); // 将序列一分为二，接收中心节点位置
QSort(L, low, pivotloc - 1); // 将[low...pivotloc-1]中的元素快速排序
QSort(L, pivotloc + 1, high); // 将[pivtoloc+1...high]中的元素快速排序
}
}
void QuickSort(SqList* L) { // 快速排序算法
QSort(L, 1, L->length);
}
void main() {
SqList L;
initList(&L);
printData(&L);
QuickSort(&L);
printData(&L);
}
4. 后记
还是要自己动手实现一下代码才能印象深刻，只是每次实现一个算法都要耗费不少时间，对比一下现在我的复习进度，感觉时间不够用了，408刚刚复习完数据结构，实在是有点龟速了，欢迎和大家一起交流进步。