随手编程

背景

快速排序，是在上世纪60年代，由美国人东尼·霍尔提出的一种排序方法。这种排序方式，在当时已经是非常快的一种排序了。因此在命名上，才将之称为“快速排序”。这个算法是二十世纪的七大算法之一，平均情况下时间复杂度为Ο(nlogn)，而且在O(nlogn)的情况下，实际的运算速度都要快于其他同时间复杂度的排序方法。

对东尼·霍尔以及快速排序的提出背景感兴趣的同学，可以看看这篇介绍：http://www.nowamagic.net/librarys/veda/detail/2391

排序思想

快速排序的思路想到很困难，但是理解起来却非常容易

他的思路是这样的：

1、先选定队列中，某一个元素为基数Value（一般选择头元素，或尾元素）。

2、将基数Value依次与所有元素比较大小。按照比较结果将元素分为两个队列A、B。一个所有元素比基数Value大，一个所有元素比基数Value小。

3、将A作为新的队列，再次选定基数，然后分成两个更小的队列

4、就这样一直将每一个小的队列无限的拆分成更小的两个队列。

5、一直到一个队列已经拆分成不能拆封为止（也就是一个元素）

6、因为队列之间的顺序都是固定的。将这些队列一次组合起来，整体的排序就算完成了。

(防盗连接：本文首发自http://www.cnblogs.com/jilodream/ )

注意这里有两个最核心的步骤，就是

1、选出Value元素，将整体队列划分成两个子队列

2、然后将子队列重新作为一个新的，整体规模比当前要小的，新的队列，进行计算，直到计算起来非常容易为止。

这两个核心步骤造就了快排天生的优势：

1、通过比较大小划分到子队列中的元素，在未来的比较过程中，这个元素的比较范围始终都停留在这个子队列中，不再做多余的比较。这使得早期的比较对后期的比较仍然有很大的影响。而类似于冒泡的排序方法，则前期很多的比较，对后期的作用非常小。这点和kmp算法很像，前期的比较尽量做到最大的利用。

2、将原有规模的队列，拆分成若干个规模小的子队列，这些子队列要(防盗连接：本文首发自http://www.cnblogs.com/jilodream/ )解决的问题与原有队列一致，只是规模变小了。这样不断的拆分，形成一种分而治之的思想。这种思想与背包算法也是不谋而合。

对于文字理解起来有困难的同学，可以看下下边这张网上经典的动态图，非常生动：

下边是java实现的代码

 1 import java.util.Arrays; 2  3 public class QuickSort 4 { 5   public static void main(String args[]) 6   { 7     QuickSort quicksort = new QuickSort(); 8     int[] arrays = new int[] 9     { 1, 12, 2, 13, 3, 14, 4, 15, 5, 16, 17, 17, 177, 18, 8, 8, 19 };10     quicksort.quickSort(arrays);11     System.out.println(Arrays.toString(arrays));12   }13   14   private void quickSort(int[] arrays)15   {16     subQuickSort(arrays, 0, arrays.length - 1);17   }18   19   private void subQuickSort(int[] arrays, int start, int end)20   {21     if (start >= end)22     {23       return;24     }25     int middleIndex = subQuickSortCore(arrays, start, end);26     subQuickSort(arrays, start, middleIndex - 1);27     subQuickSort(arrays, middleIndex + 1, end);28   }29   30   private int subQuickSortCore(int[] arrays, int start, int end)31   {32     int middleValue = arrays[start];33     while (start < end)34     {35       while (arrays[end] >= middleValue && start < end)36       {37         end--;38       }39       arrays[start] = arrays[end];40       while (arrays[start] <= middleValue && start < end)41       {42         start++;43       }44       arrays[end] = arrays[start];45     }46     arrays[start] = middleValue;47     return start;48   }49 }

原标题：随手编程

关键词：