1.基本思想
从待排序列中选取一元素作为轴值(也叫主元)。
将序列中的剩余元素以该轴值为基准，分为左右两部分。左部分元素不大于轴值，右部分元素不小于轴值。轴值最终位于两部分的分割处。
对左右两部分重复进行这样的分割，直至无可分割。
从快速排序的算法思想可以看出，这是一递归的过程。
2.实现原理
对于n个数据的记录。
从数据中取出第一个元素作为分界值、放在中间，所有比分界值小的元素放在左边，所有比分界值大的元素放在右边。然后对左右两个序列进行递归，重新选择分界值并进行移动。这样层层递归下去，直到每个子序列的元素只剩下一个。
3.代码实例
(1)代码:
public static void subSort(int[] source, int begin, int end) { if (begin < end) { // 标记1从开始起,因为不包括base，而且使用前要++,所以为这个数 int sign1 = begin; // 标记2从结束起，使用前要--,所以为这个数 int sign2 = end + 1; // 假设第一个为base int base = source[begin]; while (true) { // 从左向右找第一个比base大的数，用sign1标记索引 while (source[++sign1] < base && sign1 < end) {} // 从右到左找第一个比base小的数，用sign2标记索引 while (source[--sign2] > base && sign2 > begin) {} // 若此时sign1和sign2没有碰头，就交换它们 if (sign1 < sign2) { int temp = source[sign1]; source[sign1] = source[sign2]; source[sign2] = temp; // 若已经碰头，就结束循环 } else { break; } } //将base和sign2换一下，这样，已经将原数组分成2部分，中间的那个为base int temp = source[begin]; source[begin] = source[sign2]; source[sign2] = temp; subSort(source, begin, sign2 - 1); subSort(source, sign2 + 1, end); } } public static void main(String[] args) { int[] array = { 83, 7, 11, 47, 66, 26, 85, 79, 44, 14}; System.out.print("排序前: "); for (int num : array) System.out.print(num + " "); System.out.println(); subSort(array,0, array.length - 1); System.out.print("排序后: "); for (int num : array) System.out.print(num + " "); System.out.println(); }
(2)结果:
排序前: 83 7 11 47 66 26 85 79 44 14
排序后: 7 11 14 26 44 47 66 79 83 85
4.算法分析
快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(nlogn)。
最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况
最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况
这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。
(01) 为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因 此，快速排序的遍历次数最少是lg(N+1)次。
(02) 为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。
快速排序是不稳定的算法，它不满足稳定算法的定义。
算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！