快速排序（QuickSort）是对冒泡排序的一种改进。由 C. A. R. Hoare 在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法过程设要排序的数组是 A[0] …… A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是：
设置两个变量 I、J，排序开始的时候：I = 0，J = N - 1；
以第一个数组元素作为关键数据，赋值给 key，即 key = A[0]；
从 J 开始向前搜索，即由后开始向前搜索（ J = J - 1），找到第一个小于 key 的值 A[ J ] ，并与 A[ I ] 交换；
从 I 开始向后搜索，即由前开始向后搜索（ I = I + 1 ），找到第一个大于 key 的 A[ I ]，与 A[ J ] 交换；
重复第3、4、5步，直到 I = J； (3,4步是在程序中没找到时候 j = j - 1，i = i + 1，直至找到为止。找到并交换的时候 i， j 指针位置不变。另外当 i = j这过程一定正好是i+或j-完成的最后另循环结束)
上面这种算法的描述理解起来有点绕（通过Java代码做了示例），但是这种算法通过交换的方式节省了空间。在现在内存空间比较大的情况下，可以考虑下面这种算法（通过Python代码做了示例）：
从数组 A 中取一个中间值 t，创建两个数组B、C，一个（B）用来存放小于 t 的数据，另一个（C）用来存放大于 t 的数据。
遍历数组 A 并与中间值 t 进行比较，将小于中间值的数据放入数组 B，将大于中间值的数据放入数组 C。
对数组 B、C 按照1、2步进行排序。
将 B、t、C组合后输出为排序后的结果。
Java示例 class QuickSort { public static int[] qsort(int arr[], int start, int end){ int refNumber = arr[start]; int i = start; int j = end; while( i < j ){ while( (i < j) && (arr[j] > refNumber) ){ j--; } while( (i < j) && (arr[i] < refNumber) ){ i++; } if( (arr[i] == arr[j]) && (i < j)){ i++; }else{ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } if( i - 1 > start) arr = qsort(arr, start, i - 1); if( j + 1 < end ) arr = qsort(arr, j + 1 ,end); return arr; } public static void main(String[] args){ int arr[] = new int[]{ 5, 10, 2, 15, 21, 99, 3, 1, 17, 23, 1, 35}; int len = arr.length - 1; arr = qsort(arr, 0, len); for(int i:arr){ System.out.print(i + "\t"); } } } Python示例这个算法使用的数组支持不定长，对于其他语言来说不一定适用。
# -*- coding: utf-8 -*- def quick_sort(data): if len(data) >= 2: # 递归入口及出口 mid = data[0] # 选取基准值，也可以选取第一个或最后一个元素 left, right = [], [] # 定义基准值左右两侧的列表 data.remove(mid) # 从原始数组中移除基准值 for num in data: if num >= mid: right.append(num) else: left.append(num) return quick_sort(left) + [mid] + quick_sort(right) else: return data array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12] print(quick_sort(array)) # 输出为[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17] 算法变种快速排序(Quicksort)有几个值得一提的变种算法，这里进行一些简要介绍：
随机化快排：快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”
平衡快排（Balanced Quicksort）：每次尽可能地选择一个能够代表中值的元素作为关键数据，然后遵循普通快排的原则进行比较、替换和递归。通常来说，选择这个数据的方法是取开头、结尾、中间3个数据，通过比较选出其中的中值。取这3个值的好处是在实际问题（例如信息学竞赛……）中，出现近似顺序数据或逆序数据的概率较大，此时中间数据必然成为中值，而也是事实上的近似中值。万一遇到正好中间大两边小（或反之）的数据，取的值都接近最值，那么由于至少能将两部分分开，实际效率也会有2倍左右的增加，而且利于将数据略微打乱，破坏退化的结构。