作者：[柒号华仔]个人信条：星光不问赶路人,岁月不负有心人。
个人方向：专注于5G领域，同时兼顾其他网络协议，编解码协议，C/C++，linux等，感兴趣的小伙伴可以关注我，一起交流。
1. 快速排序介绍
1.1 定义
快速排序是一种分治排序方法，通过多次比较和交换来实现排序，其基本操作是将无序表不断拆分和交换，直到拆分到最小时，整个表就成为了一个有序表，从而得到一个新的、记录数量增1的有序表。在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。
1.2 基本原理
快速排序的基本原理：
- 从无序表中选择一个基准元素，将比它小的元素移动到左边，比它大的元素移动到右边，该元素便实现了分区操作；
- 左右两个分区分别独立排序，在各自的分区中选择一个基准元素，分区中比基准小的元素移动左边，比基准大的元素移动到右边；
- 不断重复上述分区和移动操作，最终实现整个数组变为有序表。
简单的说，就是每一次都让基准左边的元素比它小，基准右边的元素比它大，这样无限拆分循环下去，数组自然就变为有序数组了。
下面的动图诠释了快速排序的过程：
1.3 时间复杂度
最优的情况下，时间复杂度为O(nlogn)；
最坏的情况下，无序表完全正序或者倒序，每次划分只得到一个比上一次划分少一个记录的子序列，时间复杂度为O($n^2$)。
1.4 空间复杂度
空间的消耗主要是递归造成的栈空间使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。
1.5 优缺点
优点：算法简单，排序效率高，最好情况下的时间复杂度为O(nlogn)
缺点：非稳定排序
2. 代码实现
#include "stdio.h"
void printArray(int array[], int size)
{
int i;
for (i = 0; i < size; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
void quickSort(int array[],int left,int right)
{
if(left >= right)
return;
int pivot = array[left];
int i = left, j = right;
while(i < j){
while (i < j && array[j] >= pivot)
j--;
array[i] = array[j];
while (i < j && array[i] < pivot)
i++;
array[j] = array[i];
}
array[i] = pivot;
quickSort(array, left, i-1);
quickSort(array, i+1, right);
}
int main()
{
int array[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
quickSort(array,0,sizeof(array)/sizeof(int));
printArray(array, sizeof(array)/sizeof(int));
return 0;
}
运行结果：
2 3 4 5 15 19 26 27 36 38 44 46 47 48 50
