1、引入
第一节讲的计数排序有很好的运行时间表现，但因为占用空间的问题，只适用于数字非常有限的情况；
第二节讲的冒泡排序解决了计数排序空间的问题，但时间复杂度却变成了O(n^2)。
时间复杂度和空间复杂度
对冒泡排序的过程进行分析，我们可以发现，在每一轮的排序过程中，需要对所有相邻的数字进行比较（当然，除了最后几个最大数字），有的数字第一轮比较过了，第二轮可能还要比较，这就存在了优化的空间。
冒泡排序动态图
针对这个重复比较的问题，快速排序提出了基准数，减小比较次数，实现了算法的优化。
快速排序的过程：
1、选择一个数作为基准数，也就是比较的标准
2、比这个数字小的放左边，大的放右边
3、再对左右区间重复第二步，直到各区间只有一个数
这种重复左右区间直至一个终止条件的方式，就是分治或者递归的过程，所以快速排序算法也叫做分治算法，可以简单理解为分为左右两部分，分别求解。
分治和递归的联系和区别，之后会在《算法思想》中说明，这里可以简单理解为递归是实现分治的方法。
分治和递归
2、核心算法
下面一个动态表现了快速排序的过程
快速排序动图
快速排序的过程也是一个分治或者递归的过程，因为需要递归，即函数调用自身，只是参数不一样，所以需要单独写一个函数。
-
递归函数内部首先就要设置终止条件，具体到快速排序，就是最终只剩下一个数，自然就排序完成了，就不用再递归了；
-
while循环内部就是主体，从左到右找到比基准数大的，从右到左找到比基准数小的，交换位置，直至两个过程相遇；循环完成之后将基准数归位
-
左边和右边分别递归
快速排序过程
核心代码如下，使用C语言：
//快速排序
void quicksort(int left, int right) {
int i, j, temp;
//终止条件
if (left>right)
return;
temp = a[(left + right) / 2];
i = left;
j = right;
//从左到右找到比基准数大的，从右到左找到比基准数小的，交换位置，直至两个过程相遇即全部比较完成
while (i != j) {
while (a[j] >= temp && i<j)
j--;
while (a[i] <= temp && i<j)
i++;
if (i < j) {
int l = a[i];
a[i] = a[j];
a[j] = l;
}
}
//将基准数归位
a[(left + right) / 2] = a[i];
a[i] = temp;
//左边递归过程
quicksort(left, i - 1);
//右边递归过程
quicksort(i + 1, right);
}
3、代码
这里是完整代码，使用C语言
//输入：6 5 3 1 8 7 2 4
//输出：1 2 3 4 5 6 7 8
#include <stdio.h>
using namespace std;
int a[100001];
//快速排序
void quicksort(int left, int right) {
int i, j, temp;
//终止条件
if (left>right)
return;
temp = a[(left + right) / 2];
i = left;
j = right;
//从左到右找到比基准数大的，从右到左找到比基准数小的，交换位置，直至两个过程相遇即全部比较完成
while (i != j) {
while (a[j] >= temp && i<j)
j--;
while (a[i] <= temp && i<j)
i++;
if (i < j) {
int l = a[i];
a[i] = a[j];
a[j] = l;
}
}
//将基准数的位置放在大小分割的中间
a[(left + right) / 2] = a[i];
a[i] = temp;
//左边递归过程
quicksort(left, i - 1);
//右边递归过程
quicksort(i + 1, right);
}
int main() {
int n=8;
//读入数据
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
//快速排序
quicksort(1, n);
//输出结果
for (int i = 1; i <= n; i++)
printf("%d ", a[i]);
getchar(); getchar();
return 0;
}
4、后续
至此，计数排序、冒泡排序、快速排序的就全部完成了，你学会了吗？具体掌握还需要加强练习，下一节，我们通过习题，巩固学习！
加油
网友评论