# 快速排序(Quick Sort)

``public class QuickSort3 {``

`private static Scanner scanner;`

`public static void main(String[] args) {`

`System.out`

`.println("Please input integers split by comma (do not input blank): ");`

`scanner = new Scanner(System.in);`

`String sc = scanner.next();`

`String[] ints = sc.split(",");`

`int[] arrays = new int[ints.length];`

`for (int i = 0; i < ints.length; i++) {`

`arrays[i] = Integer.parseInt(ints[i]);`

`// System.out.println(arrays[i]);`

`}`

`QuickSort3 qs = new QuickSort3();`

`qs.quickSort(arrays, 0, arrays.length - 1);`

`for (int i = 0; i < ints.length; i++) {`

`System.out.print(arrays[i] + ", ");`

`}`

`}`

`// 把基准值放到合适的位置后，并返回基准值的 index`

`public int moveBase(int[] list, int left, int right) {`

`if (list.length == 1 || left == right) {`

`return left;`

`}`

`int baseIndex = left;`

`int base = list[baseIndex]; // 数组的第一个作为基准值`

`while (left + 1 < right) { // 这里比较的是哨兵的 index，左边哨兵的 index = left + 1`

`while (left + 1 < right && list[right] >= base) {`

`right--;`

`}`

`while (left + 1 < right && list[left + 1] <= base) {`

`left++;`

`}`

`int tmp = list[left + 1];`

`list[left + 1] = list[right];`

`list[right] = tmp;`

`}`

`// 交换基准值和 left 哨兵位置的值`

`list[baseIndex] = list[left + 1];`

`list[left + 1] = base;`

`return left + 1; // 返回基准值的 index`

`}`

`/**`

`* `

`* @param list`

`* array`

`* @param left`

`* left index`

`* @param right`

`* right index`

`*/`

`public void quickSort(int[] list, int left, int right) {`

`if (left < right) {`

`int baseIndex = moveBase(list, left, right); // 将 list 数组进行一分为二`

`quickSort(list, left, baseIndex - 1); // 对左边的元素排序`

`quickSort(list, baseIndex + 1, right); // 对右边的元素排序`

`}`

`}`

``}``

// 将基准量移动到合适的位置，并返回基准值的 index

`public int getMiddle(int[] list, int low, int high) {`

`int tmp = list[low]; // 数组的第一个作为中轴`

`while (low < high) {`

`while (low < high && list[high] >= tmp) { `// 从右往左扫描，探测比基准量小的元素

`high--;`

`}`

`list[low] = list[high]; // 比中轴小的记录移到低端`

`while (low < high && list[low] <= tmp) { `// 从左往右扫描，探测比基准量大的元素

`low++;`

`}`

`list[high] = list[low]; // 比中轴大的记录移到高端`

`}`

`list[low] = tmp; // 中轴记录到尾`

`return low; // 返回中轴的位置`

`}`

`public void quickSort(int[] list, int low, int high) {`

`if (low < high) {`

`int middle = getMiddle(list, low, high); // 将list数组进行一分为二`

`quickSort(list, low, middle - 1); // 对低字表进行递归排序`

`quickSort(list, middle + 1, high); // 对高字表进行递归排序`

`}`

`}`

http://blog.csdn.net/pzhtpf/article/details/7560294 程序员必知的8大排序(三)-------冒泡排序，快速排序（java实现, by pzhtpf）