快速排序快速排序算法的详细解(原理、实现和时间复杂度)快速排序是对冒泡排序的一种改进，通过xydhf (charlesantonyrichardhoare，以前的心链)
快速排序的基本思想是将按一次排序排序的数据划分为两个独立的部分，其中一个部分的所有数据小于其他部分的所有数据，用这种方法分别快速排序两个部分的数据，从而递归地对整个排序过程进行排序
快速排序原理排序算法的思路非常简单，在要排序的数列中，首先查找作为基准数的数字。 为了方便，一般选择第一个数字作为基准数(实际上选择第几个都可以)。 接下来，在要排序的列中，必须将小于标准数量的元素移动到要排序的列的左侧，并将大于标准数量的元素移动到要排序的列的右侧。 此时，左右两个区分的要素相对有序。 然后，继续使用上述两种方法分别为每个分区找到基准数量，并将两个分区的元素移动到每个分区只有一个数量的情况。
这是典型的分治思想，即分治法。 用算法说明实际例子，说明快速排序的排序步骤。
以47、29、71、99、78、19、24和47个要排序的数列为例，为以下47加下划线，以便于区分这两个47 : 也就是说，要排序的数列是47、29、71、99、78、19、24和47。
首先需要从数列中选择基准数。 一般选择中间的数或头尾的数。 在此直接选择第一个数字47作为基准数字，然后将小于47的数字向左移动，将大于47的数字向右移动。 对于相等的数字不移动。 因此，实际上需要找到中间位置k，使得k的左边的值全部小于k上的值，k的右边的值全部大于k上的值。
然后开始移动元素。 怎么移动？ 实际上，鼓泡排序也与元素的移动有关，但这样移动非常累。 例如，如果将最后一种元素移动到第一位，则需要在比较n-1次的同时更换n-1次，效率很低。 其实，把第一个要素和最后一个要素交换就可以了，这个思想在排序时不是有参考价值吗？ 之所以说快速排序是泡沫排序的改进之处，就是这个原因。
快速排序操作首先从数列的右向左查找。 把这个下标设为I。 也就是说，进行负操作(I) )，找到小于基准数的第一个值，与基准值进行交换。 接下来从左向右搜索，将该下标设为j，执行加法操作(j )，找出大于基准数的第一个值，与基准值进行交换； 然后，持续搜索到I和j相遇时结束，最后的基准值所在的位置即k的位置，即k的左边的值都小于k的值，k的右边的值都大于k的值。
因此，对于上面数列47、29、71、99、78、19、24、47，在进行第1次交换的排序的情况下如下，在第1次操作的情况下如下
照片
用1表示。
图111次发现中可以交换的数量
更换后，j移动到下标6的位置，如图2所示对I继续扫描。
图222次可交换值的发现
此时交换的数列为24、29、47、99、78、19、71、47。 接着继续进行I、j的操作，如图3所示，继续进行i--及j的比较操作。
继续图3I和j的移动
进行这两次I、j的移动、比较、交换后，我们最终得到的数列是24、29、19、47、78、99、71、47。 接下来继续i--的操作，I为4时大于47可以不交换，I为3时与j相遇，那时不需要继续移动、比较，已经找到了k，k的值为3。 可以确认当前数列是否k左边的值都小于47，k右边的值都大于47 (为了保持相对位置不变，47同样位于基准值47的右边)。
47这个值已经落到那个位置，第一次排序完成了。 然后根据k分为两个部分，在左右两个部分分别执行上述排序操作，最后的数据分为四个部分，然后操作每个部分，直到每个部分只有一个值。
接下来进行第二次排序。 现在左边的部分是24、29、19。 选择第1个数24作为基准数，然后进行I、j的操作。 I的第一个值是19，小于标准值24，因此与标准值交换后得到的数列是19、29、24。 发现j为1时，29大于24，因此与基准值进行交换得到数列19、24、29。 此时I为2，j为1； 继续i--的话，你会发现I是1，与j相遇，左边的数列k是1，而且左右各只有一个要素。 此时，第二次排序左侧的排序结束，同时左侧的所有数据进行排序。
接下来看看右边的排序。 要排序的数列为78、99、71和47。 同样，选择第一个值78作为基准值，接着与I和j的移动进行比较，可知47小于78，进行交换，得到的数列47、99、71、78； 发现自左向右99大于参考值78，进行交换，得到数列47、7
8、71、99；继续从右向左看，发现 71 比基准值 78 小，进行交换，得到的数列为 47、71、78、99。此时 i 在整体数组中的下标为 6，j 为 5，若继续 j++ 则与 i 相遇，所以完成此轮排序。此时右边数列的 k 为 6，一般会是相遇的位置，也就是基准值所在的位置，这时数列又被分为两部分，左边是 47、71，右边是 99，需要继续对左边部分的数据进行排序，虽然只有两个数据，但我们还是继续按照快速排序的思想操作一下，选择 47 作为基准数，将i进行从右向左的移动、比较，发现 i 与 j 相等时没有产生移动，完成第 2 轮排序。
至此，所有排序都已经完成，最终数列的结果是 19、24、29、47、47、71、78、99，怎么样，快速排序是不是非常简单地完成了所有的排序呢？虽然本次快速排序没有改变相同值的元素的顺序，但是由于快速排序需要对数列中的元素来回移动，有时还是会改变相对顺序的（比如 47 在第 1 轮的移动过程中就被移动到 47 的右边了），所以快速排序并不是一个稳定的算法。
快速排序的实现通过以上的学习，你是否可以自己写出快速排序的实现代码呢？在接着学习之前，最好自己能对代码的实现进行一些思考，然后和下面的内容进行比对，看看自己有哪些疏忽之处。
其实快速排序有一个比较简单的思想，就是递归。对于每一趟排序都是一样的思想，只不过需要进行排序的数组的范围越来越小了，使用递归实现这种排序最适合不过了。
public class QuickSort { private int[] array; public QuickSort(int[] array) { this.array = array; } public void sort() { quickSort(array, 0, array.length - 1); } public void print() { for (int i = 0; i < array.length; i++) { System.out.println(array[i]); } } /** * 递归排序 * @param src * @param begin * @param end */ private void quickSort(int[] src, int begin, int end) { if (begin < end) { int key = src[begin]; int i = begin; int j = end; while (i < j) { while (i < j && src[j] > key) { j--; } if (i < j) { src[i] = src[j]; i++; } while (i < j && src[i] < key) { i++; } if (i < j) { src[j] = src[i]; j--; } } src[i] = key; quickSort(src, begin, i - 1); quickSort(src, i + 1, end); } }}下面是测试代码，用于验证代码的正确性。
public class SortTest { public static void main(String[] args) { testQuickSort(); } /** * 快速排序 */ private static void testQuickSort() { int[] array = {5, 9, 1, 9, 5, 3, 7, 6, 1}; QuickSort quickSort = new QuickSort(array); quickSort.sort(); quickSort.print(); }} 快速排序的特点及性能快速排序是在冒泡排序的基础上改进而来的，冒泡排序每次只能交换相邻的两个元素，而快速排序是跳跃式的交换，交换的距离很大，因此总的比较和交换次数少了很多，速度也快了不少。
但是快速排序在最坏情况下的
时间复杂度
和冒泡排序一样，是 O(n2)，实际上每次比较都需要交换，但是这种情况并不常见。我们可以思考一下如果每次比较都需要交换，那么数列的平均时间复杂度是 O(nlogn)，事实上在大多数时候，排序的速度要快于这个平均时间复杂度。这种算法实际上是一种分治法思想，也就是分而治之，把问题分为一个个的小部分来分别解决，再把结果组合起来。
快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的
空间复杂度
为 O(logn)，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 O(n)。所以我们一般认为快速排序的空间复杂度为 O(logn)。
快速排序是一个不稳定的算法，在经过排序之后，可能会对相同值的元素的相对位置造成改变。
快速排序基本上被认为是相同数量级的所有排序算法中，平均性能最好的。