快速排序是由所发展的一种。在平均状况下，排序 n 个项目要(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实作出来，且在大部分真实世界的资料，可以决定设计的选择，减少所需时间的二次方项之可能性。
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。然后分别递归的排序关键数据前面和后面两段数据。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
在具体实现上，如何吧将所有比它小的数都放到它前面，所有比它大的数都放到它后面是关键。也有不同的版本。先来第一个版本：
1 import java.util.Arrays; 2 import java.util.Random; 3 4 /** 5 * User: laichendong 6 * Date: 12-3-14 7 * Time: 上午9:57 8 */ 9 public class QuickSort { 10 private static Random random = new Random(); 11 12 public static void main(String[] args) { 13 int[] array = {49, 38, 52, 44, 81, 97, 76, 13, 27, 65}; 14 qsort(array, 0, array.length - 1); 15 System.out.println(Arrays.toString(array)); 16 } 17 18 private static int partionSort(int[] array, int begin, int end) { 19 int index = begin + random.nextInt(end - begin + 1); 20 int key = array[index]; 21 swap(array, index, end); 22 for (int k = index = begin; k < end; k++) { 23 if (array[k] < key) { 24 swap(array, index, k); 25 index++; 26 } 27 } 28 swap(array, index, end); 29 return index; 30 } 31 32 private static void qsort(int[] array, int begin, int end) { 33 if (begin < end) { 34 int index = partionSort(array, begin, end); 35 qsort(array, begin, index - 1); 36 qsort(array, index, end); 37 } 38 } 39 40 private static void swap(int[] a, int i, int j) { 41 int t = a[i]; 42 a[i] = a[j]; 43 a[j] = t; 44 } 45 } 第二个版本：
1 import java.util.Arrays; 2 import java.util.Random; 3 4 /** 5 * User: laichendong 6 * Date: 12-3-14 7 * Time: 上午9:57 8 */ 9 public class QuickSort { 10 private static Random random = new Random(); 11 12 public static void main(String[] args) { 13 int[] array2 = {49, 38, 52, 44, 81, 97, 76, 13, 27, 65}; 14 qsort2(array2, 0, array2.length - 1); 15 System.out.println(Arrays.toString(array2)); 16 } 17 18 private static void qsort2(int[] array, int begin, int end) { 19 if (begin < end) { 20 int index = partionSort2(array, begin, end); 21 if(begin < end - 1){ 22 qsort(array, begin, index - 1); 23 qsort(array, index, end); 24 } 25 } 26 } 27 28 private static int partionSort2(int[] array, int begin, int end){ 29 int key = array[begin]; 30 int i = begin; 31 int j = end; 32 while (i <= j){ 33 if(array[j] <= key){ 34 if(array[i] >= key){ 35 swap(array, i, j); 36 j--; 37 }else { 38 i++; 39 } 40 }else{ 41 j--; 42 } 43 } 44 return i; 45 } 46 47 private static void swap(int[] a, int i, int j) { 48 int t = a[i]; 49 a[i] = a[j]; 50 a[j] = t; 51 } 52 } 推荐使用第一个版本，比较好理解。最后，发一个对应版本二的动画演示：