快速排序
基本思想：
通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对两部分继续进行排序，直到整个序列有序。
实例：
1.一趟排序的过程：
2.排序的全过程：
把整个序列看做一个数组，把第零个位置看做中轴，和最后一个比，如果比他小，则交换，比它大不做任何处理；
交换了以后再和小的那端比，比它小不交换，比它大交换。这样循环往复，一趟排序完成，左边的就是比中轴小的，
右边的就是比中轴大的，然后再用分治法，分别对这两个独立的数组进行排序。
代码实现
public class QucikSortDemo {
public static void main(String arg[]) {
int[] numbers = {10, 89, 87, 76, 56, 46, 11, 75, 32, 35, 98};
System.out.println("排序前：");
printArr(numbers);
quickSort(numbers);
System.out.println("排序后：");
printArr(numbers);
}
/**
* 查找出中轴位置(默认是最低为low)的在number数组排序后所在位置
*
* @param numbers
* @param low
* @param high
* @return
*/
public static int getMiddle(int[] numbers, int low, int high) {
// 数组的第一位作为中轴
int temp = numbers[low];
while (low < high) {
while (low < high && numbers[high] > temp) {
high--;
}
// 比中轴晓得记录移动到低端
numbers[low] = numbers[high];
while (low < high && numbers[low] < temp) {
low++;
}
// 比中轴大的记录移到高端
numbers[high] = numbers[low];
}
// 中轴记录到尾
numbers[low] = temp;
// 返回中轴的位置
return low;
}
/**
* 分治排序
*
* @param numbers
* @param low
* @param high
*/
public static void quickSort(int[] numbers, int low, int high) {
if (low < high) {
// 将numbers数组进行一分为二
int middle = getMiddle(numbers, low, high);
// 将低字段表进行递归排序
quickSort(numbers, low, middle - 1);
// 将高字段表进行递归排序
quickSort(numbers, middle + 1, high);
}
}
public static void quickSort(int[] numbers) {
if (numbers.length > 0) {
quickSort(numbers, 0, numbers.length - 1);
}
}
public static void printArr(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
System.out.print(numbers[i] + ",");
}
System.out.println("");
}
}
