1 package cn.itcast; 2 3 /* 4 * 快速排序基本思路是: 5 * 一趟快速排序的算法是: 6 * 1)设置两个变量i、j,排序开始的时候:i=0,j=N-1; 7 * 2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0]; 8 * 3)从j开始向前搜索,即由后开始向前搜索(j=j-1即j--), 9 * 找到第一个小于key的值A[j],A[i]与A[j]交换; 10 * 4)从i开始向后搜索,即由前开始向后搜索(i=i+1即i++), 11 * 找到第一个大于key的A[i],A[i]与A[j]交换; 12 * 5)重复第3、4、5步,直到 i=j。 13 * (3,4步是在程序中没找到时候,j=j-1,i=i+1,直至找到为止。 14 * 找到并交换的时候i,j指针位置不变。 15 * 另外当i=j这过程一定正好是i++或j--完成的,最后令循环结束。) 16 */ 17 public class QuickSort { 18 public static void sort(int[] data) { 19 quickSort(data, 0, data.length - 1); 20 } 21 22 private static void quickSort(int[] data, int i, int j) { 23 int pivotIndex = (i + j) / 2; 24 // swap 25 SortTest.swap(data, pivotIndex, j); 26 27 int k = partition(data, i - 1, j, data[j]); 28 SortTest.swap(data, k, j); 29 if ((k - i) > 1) 30 quickSort(data, i, k - 1); 31 if ((j - k) > 1) 32 quickSort(data, k + 1, j); 33 34 } 35 36 /** 37 * @param data 38 * @param i 39 * @param j 40 * @return 41 */ 42 private static int partition(int[] data, int l, int r, int pivot) { 43 do { 44 while (data[++l] < pivot) 45 ; 46 while ((r != 0) && data[--r] > pivot) 47 ; 48 SortTest.swap(data, l, r); 49 } while (l < r); 50 SortTest.swap(data, l, r); 51 return l; 52 } 53 }