概念
快速排序（Quicksort）是对冒泡排序的一种改进。
原理
快速排序采用的思想是分治思想。
- 选择一个基准元素,通常选择第一个元素或者最后一个元素,
- 通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
- 此时基准元素在其排好序后的正确位置
- 然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
快速排序的示例：
（a）一趟排序的过程：
（b）排序的全过程
算法描述（C语言）
void quick_sort(int *a, int left, int right) {
if (left >= right) {
//如果左边索引大于或者等于右边的索引就代表已经整理完成一组了
return;
}
int i = left;
int j = right;
int key = a[left];
while (i < j) {
while (i < j && key <= a[j]) {
//寻找结束的条件就是
//1.找到一个小于或者大于key的数(大于或小于取决于你想升序还是降序)
//2.没有符合条件1的，并且i与j的大小没有反转
j--;//向前寻找
}
a[i] = a[j];
//找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是a[left],那么就是给key）
while (i < j && key >= a[i]) {
//这是i在当前组向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
//因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反
i++;
}
a[j] = a[i];
}
a[i] = key;//当在当组内找完一遍后就把中间数key回归
quick_sort(a, left, i - 1);//最后用同样的方式对分出来的左边的小组进行同样的做法
quick_sort(a, i + 1, right);//用同样的方式对分出来的右边的小组进行同样的做法 直到每一组的i = j为止
}
int main() {
int a[] = {49, 38, 65, 97, 76, 13, 27, 49};
int len = sizeof(a)/sizeof(int);
quick_sort(a, 0, len);
for (int i = 0; i < len; i++) {
printf("%d\n", a[i]);
}
return 0;
}
算法稳定性
不稳定
算法分析
时间复杂度为O(n²)。
