作者简介：
🍀姓姜，字君竹。
🍁浅薄观点：科以载文，文以载道
🌱软件技术升计科，计划考研
🌾要有最朴素的生活和最遥远的梦想，即使明日，天寒地冻，路遥马亡
1.概念及介绍
快速排序是对冒泡排序的改进算法，主要思想是在待排序列中取一个元素（通常为第一个）作为参照，将序列分为两个子序列，比参照值小的元素和笔参照值大的元素各自组成一个子序列。每趟排序会使参照元素归位，并且得到两个子序列。在子序列中继续执行该步骤，知道子序列的长度为0或1。
快速排序是一种划分交换排序方法，采用了分治策略。首先将原问题划分成若干个规模更小，与原问题相似的子问题，让后用递归方法解决这些子问题，最后再将它们组合成原问题的解。
第一次排好序列中的一个数，放在它应该在的位置上，同时得到两个子序列，左侧都是比它小的数，右侧都是比它大的数（升序排序），接下来每个子序列中不断重复归位一个元素，得到子序列这个过程，直到子序列的长度为1或0，此时整体的序列已经有序。
2. 时间空间复杂度
对于快速排序有个不确定因素，就是每次待排元素的选择并不固定，但是由于序列也是随机的，所以我们可以忽略这个问题。
对于快速排序来说，由于无论如何划分，比较多 次数都是固定的，不会超过O(n)，那么划分的次数就非常重要了。
如果初始序列有序，那么每次排好一个元素，并且都要挨个比较一次。重点是划分得到的子序列只有一个，如果按照快速排序的定义，每次选取区域右端点作为待排元素，那么每次只会得到一个较小的子序列，在这个序列中再次重复划分的步骤，同样只能得到一个较小的子序列，这和冒泡排序非常相似，都是每次排好一个元素，对其他元素进行一次比较，此时的时间复杂度为O(n2)。
由于算符是在子序列上不断进行递归，如果说每次待排元素恰好都在中间位，将院优序列分成两个等长的子序列，每次划分都是这样的，那么总共的划分次数就可以用O(log2n)表示，时间复杂度为O(n log2n)。
快速排序是基于关键字比较的内部排序算法中速度最快的，平均性能可以达到O(n log2n)。
因为使用了递归，所以在执行过程中需要在栈中保存相关信息，需要的空间就和递归次数相关，在平均情况下需要O(log2n)，即使是最坏的情况也不会超过O(n)。
3.图解
- 代码实现
void quickSort(int* number, int first, int last) { int i, j, pivot; int temp; if (first < last) { pivot = first; i = first; j = last; while (i < j) { while (number[i] <= number[pivot] && i < last) i++; while (number[j] > number[pivot]) j--; if (i < j) { temp = number[i]; number[i] = number[j]; number[j] = temp; } } temp = number[pivot]; number[pivot] = number[j]; number[j] = temp; quickSort(number, first, j - 1); quickSort(number, j + 1, last); } } int main() { int a[] = { 2, 8, 7, 1, 3, 5, 6, 4 }; int sz = sizeof(a) / sizeof(a[0]); quickSort(&a, 0, sz - 1); int i = 0; for (i = 0; i < sz; i++) { printf("%d ", a[i]); } return 0; }
学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。
