十大基础排序 · 四 --- 快速排序（不稳定）挖坑填补法+区间分割法+3种优化方法

本文主要是介绍十大基础排序 · 四 --- 快速排序（不稳定）挖坑填补法+区间分割法+3种优化方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 分析

/*4. 快速排序（QuickSort）
#平均时间复杂度： O(nlogn) 
#最坏时间复杂度：O(n2) （有序的情况）
#空间复杂度：需要一个栈空间，若每趟排序将记录均匀分割成两个相近的子序列，则栈的最大深度为 向下取整[logn]+1；若偏向一边， 最坏情况，栈最大深度为n；在一趟分割后比较分割后的长度，先对短序列排序，则栈最大深度为O(logn);#特点： 快速排序是比较次数最少的排序，当待排数组基本有序时退化为冒泡排序。
#基本思想： 快速排序是对冒泡排序的一种改进。通过一趟排序将待排记录分割成独立两部分，其中一部分记录关键字均比另一部分记录的关键字小。则可分别对这两部分记录继续进行排序，以达整个序列有序。实现方法：递归
#方法一：挖坑填补法1. 选取一个标记（第一个点）2. 从后向前找第一个比标记小的，然后放到 空出来的位置3. 从前向后遍历，找第一个比标记大的，然后放到空出来的位置4. 继续从后向前找，重复25. 继续从前向后找大的，重复36. 直到 前后的 遇到&#