排序是学习编程这个过程中一定会学习的算法，也是程序员的一项基本技能。今天就给大家讲一下编程里面常用的快速排序。
- 优点
快速排序是一种非常快的排序算法，基于“二分”思想，时间复杂度是O(Nlog2N)。由于算法需要使用递归，空间复杂度最好情况为O(log2N), 最差为log(N)
且不会浪费储存空间 - 实现
1.找枢轴
假设我们现在要对3, 5, 2, 1, 8, 9, 10 ,7, 4,6 这10个数进行排序。首先我们需要在数列里面找一个基准数，又称枢轴。我们一般取第一个为枢轴。
3, 5, 2, 1, 8, 9, 10 ,7, 4,6
2.交换
我们要让数列左边的数都小于枢轴，右边的数都大于枢轴。我们一般取第一个数为枢轴，类似与下面这个样子。
2 1 3 5 8 9 10 7 4 6
如何实现呢？
有点类似与冒泡排序的交换，大家可以思考一下再往下看
思维导图
我们可以设置两个哨兵i, j， 让i,j 分别从数组的两边来进行搜索。j哨兵先从数组右边找一个比枢轴小的数(j--)，i数组再从数组左侧找一个比枢轴大的数(i++)，如果此时i < j，则将i, j哨兵所在的两个数交换。
图片描述
如下图，枢轴为6，j哨兵找到第一个小于6的数5，然后停止。接着，i哨兵开始行动了，往右找到第一个大于6的数7，此时，i < j, 交换两个哨兵的值，即7 与 5位置交换。
第一次交换
接着，两个哨兵重复上面的步骤，j找到小于6的数4，i找到大于6的数9，而且 i < 9,则将4与9交换。
第二次
重复上面步骤，j找到了小于6的数3，i往右探测，发现自己与j相遇了，然后就可以停止探测，将枢轴与i与j相遇的位置交换。
image
相遇
这时我们发现我们已经到底目的了，枢轴左边的数都小于枢轴，右边的数大于枢轴。
不过，枢轴左边与右边的数列还不是有序的，我们只需要对枢轴左边与右边的数列重复上面的步骤就行了，
3 1 2 5 4 //重复上面步骤，找3为基准数
9 7 10 8 //重复上面步骤，找9为基准数
不断重复直到不能拆分为子序列为止
-
处理过程如下
过程 算法描述
void Qsort(int arr[], int left, int right)
{
if(left >= right)
return;
int i, j, temp, t;
i = left;
j = right;
temp = arr[i]; /*将基准数放在temp里面*/
while(i < j)
{
while(arr[j] >= temp && i < j) /*不能没有等于*/
j--;
while(arr[i] <= temp && i < j)
i++;
if(i < j) /*交换i,j 需要判断是否i < j;*/
{
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i]; /*基准数交换*/
arr[i] = temp;
Qsort(arr, left, i-1); /*处理枢轴左边，递归*/
Qsort(arr, i+1, right); /*处理枢轴右边，递归*/
}
- 缺点，快速排序虽然香，但依然有缺点。
- 排序过程需要定位数列的左边与右边，适合顺序储存结构，不适合链式储存结构
- 排序过程无法保证相同元素的顺序，所有是不稳定的
以上图片来自与网络。
