快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
010 public class QuickSort {
011
024 // 定义了一个这样的公有方法sort，在这个方法体里面执行私有方法quckSort（这种方式值得借鉴）。
025 public void sort(Integer[] array, int from, int end) {
026 quickSort(array, from, end);
027 }
028
041 private void quickSort(Integer[] array, int low, int high) {
046 if (low < high) {
047 // 对分区进行排序整理
048
049 // int pivot = partition1(array, low, high);
050 int pivot = partition2(array, low, high);
051 // int pivot = partition3(array, low, high);
052
058 quickSort(array, low, pivot - 1);
059 quickSort(array, pivot + 1, high);
060 }
061
062 }
063
077 private int partition1(Integer[] array, int low, int high) {
078 Integer pivotElem = array[low];// 以第一个元素为中枢元素
079 // 从前向后依次指向比中枢元素小的元素，刚开始时指向中枢，也是小于与大小中枢的元素的分界点
080 int border = low;
081
086 for (int i = low + 1; i <= high; i++) {
087 // 如果找到一个比中枢元素小的元素
088 if ((array[i].compareTo(pivotElem)) < 0) {
089 swap(array, ++border, i);// border前移，表示有小于中枢元素的元素
090 }
091 }
099 swap(array, border, low);
100 return border;
101 }
102
116 private int partition2(Integer[] array, int low, int high) {
117 int pivot = low;// 中枢元素位置，我们以第一个元素为中枢元素
118 // 退出条件这里只可能是 low = high
119 while (true) {
120 if (pivot != high) {// 如果中枢元素在低指针位置时，我们移动高指针
121 // 如果高指针元素小于中枢元素时，则与中枢元素交换
122 if ((array[high].compareTo(array[pivot])) < 0) {
123 swap(array, high, pivot);
124 // 交换后中枢元素在高指针位置了
125 pivot = high;
126 } else {// 如果未找到小于中枢元素，则高指针前移继续找
127 high--;
128 }
129 } else {// 否则中枢元素在高指针位置
130 // 如果低指针元素大于中枢元素时，则与中枢元素交换
131 if ((array[low].compareTo(array[pivot])) > 0) {
132 swap(array, low, pivot);
133 // 交换后中枢元素在低指针位置了
134 pivot = low;
135 } else {// 如果未找到大于中枢元素，则低指针后移继续找
136 low++;
137 }
138 }
139 if (low == high) {
140 break;
141 }
142 }
143 // 返回中枢元素所在位置，以便下次分区
144 return pivot;
145 }
146
160 private int partition3(Integer[] array, int low, int high) {
161 int pivot = low;// 中枢元素位置，我们以第一个元素为中枢元素
162 low++;
163 // ----调整高低指针所指向的元素顺序，把小于中枢元素的移到前部分，大于中枢元素的移到后面部分
164 // 退出条件这里只可能是 low = high
165
166 while (true) {
167 // 如果高指针未超出低指针
168 while (low < high) {
169 // 如果低指针指向的元素大于或等于中枢元素时表示找到了，退出，注：等于时也要后移
170 if ((array[low].compareTo(array[pivot])) >= 0) {
171 break;
172 } else {// 如果低指针指向的元素小于中枢元素时继续找
173 low++;
174 }
175 }
176
177 while (high > low) {
178 // 如果高指针指向的元素小于中枢元素时表示找到，退出
179 if ((array[high].compareTo(array[pivot])) < 0) {
180 break;
181 } else {// 如果高指针指向的元素大于中枢元素时继续找
182 high--;
183 }
184 }
185 // 退出上面循环时 low = high
186 if (low == high) {
187 break;
188 }
189
190 swap(array, low, high);
191 }
192
193 // ----高低指针所指向的元素排序完成后，还得要把中枢元素放到适当的位置
194 if ((array[pivot].compareTo(array[low])) > 0) {
195 // 如果退出循环时中枢元素大于了低指针或高指针元素时，中枢元素需与low元素交换
196 swap(array, low, pivot);
197 pivot = low;
198 } else if ((array[pivot].compareTo(array[low])) <= 0) {
199 swap(array, low - 1, pivot);
200 pivot = low - 1;
201 }
202
203 // 返回中枢元素所在位置，以便下次分区
204 return pivot;
205 }
206
217 public void swap(Integer[] array, int i, int j) {
218 if (i != j) {// 只有不是同一位置时才需交换
219 Integer tmp = array[i];
220 array[i] = array[j];
221 array[j] = tmp;
222 }
223 }
224
225 /**
226 * 测试
227 *
228 * @param args
229 */
230 public static void main(String[] args) {
231 Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
232 QuickSort quicksort = new QuickSort();
233 quicksort.sort(intgArr, 0, intgArr.length - 1);
234 for (Integer intObj : intgArr) {
235 System.out.print(intObj + " ");
236 }
237 }
238 }