快速排序
介绍
在数组中找一个支点(任意),经过一趟排序后,支点左边的数都要比支点小,支点右边的数都要比支点大!
现在我们有一个数组:int arr[]={1,4,5,67,2,7,8,6,9,44};
经过一趟排序之后,如果我选择数组中间的数作为支点:7(任意的),那么第一趟排序后的结果是这样的:{1,4,5,6,2,7,8,67,9,44}
那么就实现了支点左边的数比支点小,支点右边的数比支点大
递归分析与代码实现
现在我们的数组是这样的:{1,4,5,6,2,7,8,67,9,44},既然我们比7小的在左边,比7大的在右边,那么我们只要将”左边“的排好顺序,又将”右边“的排好序,那整个数组是不是就有序了?
回顾一下递归:”左边“的排好顺序,”右边“的排好序,跟我们第一趟排序的做法是一样的。
只不过是参数不一样:第一趟排序是任选了一个支点,比支点小的在左边,比支点大的在右边。那么,我们想要”左边“的排好顺序,只要在”左边“部分找一个支点,比支点小的在左边,比支点大的在右边。
递归出口也很容易找到:如果数组只有一个元素时,那么就不用排序了
代码如下:
public static void main(String[] args) {
int[] arr = {1, 4, 5, 67, 2, 7, 8, 6, 9, 44};
quickSort(arr, 0, 9);
System.out.println(arr);
}
/**
* 快速排序
*
* @param arr
* @param L 指向数组第一个元素
* @param R 指向数组最后一个元素
*/
public static void quickSort(int[] arr, int L, int R) {
int i = L;
int j = R;
//支点
int pivot = arr[(L + R) / 2];
//左右两端进行扫描,只要两端还没有交替,就一直扫描
while (i <= j) {
//寻找直到比支点大的数
while (pivot > arr[i])
i++;
//寻找直到比支点小的数
while (pivot < arr[j])
j--;
//此时已经分别找到了比支点小的数(右边)、比支点大的数(左边),它们进行交换
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
//上面一个while保证了第一趟排序支点的左边比支点小,支点的右边比支点大了。
//“左边”再做排序,直到左边剩下一个数(递归出口)
if (L < j)
quickSort(arr, L, j);
//“右边”再做排序,直到右边剩下一个数(递归出口)
if (i < R)
quickSort(arr, i, R);
}