快速排序
Love&Share 人气:0一---基本思想
先给定一个数组{-3,2,0,5,-4,1}，设定一个标杆，假设就是中间值0，然后一头一尾两个指针，去对数组进行重新排序，排序的结果为中间值0的左边的数全部小于0，而标杆0的右边的数全部大于0。此时数组为{-3,-4,0,5,2,1}。然后再用相同的思想对0左边的数进行递归得{-4,-3,0,5,2,1}，对0右边的数进行递归得{-4,-3,0,1,2,5}。
二---图解
三---代码
1 public class QuickSort {
2 public static void main(String[] args) {
3 int[] arr = {-3,2,0,5,-4,1};
4 quickSort(arr, 0, arr.length - 1);
5 System.out.println(Arrays.toString(arr));
6 }
7 public static void quickSort(int[] arr, int left, int right) {
8 int l = left;
9 int r = right;
10 int temp = 0;
11 int pivot = arr[(left + right) / 2];
12 while(l < r) { // 只要l < r,说明还没有排完
13 while(arr[l] < pivot) { // 找出左边大于等于pivot的数
14 l++;
15 }
16 while(arr[r] > pivot) { // 找出右边小于等于pivot的数
17 r--;
18 }
19 // 如果l == r，说明左边的数都是小于中轴值，右边的数都是大于中轴值，无需交换，退出。
20 if(l == r) {
21 break;
22 }
23 // 如果上面的语句没有执行，说明左边有比中轴值小的，右边有比中轴值大的，交换。
24 temp = arr[l];
25 arr[l] = arr[r];
26 arr[r] = temp;
27
28 }
29 // 上面循环完成，代表我们已经按照中轴值左边全是小于等于中轴值，右边全是大于等于中轴值的规则排序好了
30 // 首先判断上面排序完成后l和r是否相等，如果相等，要错开，否则会进行栈溢出
31 if(l == r) {
32 l++;
33 r--;
34 }
35 // 左边递归排序
36 if(left < r) { // 错开之后r是在左边的，所以这里就是r。
37 quickSort(arr, left, r);
38 }
39 // 左边部分排好了，接下来进行右边
40 if(right > l) { // 错开之后l是在左边的，所以这里就是l。
41 quickSort(arr, l, right);
42 }
43 }
四---出现问题
上面的代码其实是有瑕疵的，思考这样一个数组
{-4,2,0,0,7}
程序报错：
改进代码，红色部分即为优化。
1 public static void quickSort(int[] arr, int left, int right) {
2 int l = left;
3 int r = right;
4 int temp = 0;
5 int pivot = arr[(left + right) / 2];
6 while(l < r) { // 只要l < r,说明还没有排完
7 while(arr[l] < pivot) { // 找出左边大于等于pivot的数
8 l++;
9 }
10 while(arr[r] > pivot) { // 找出右边小于等于pivot的数
11 r--;
12 }
13 // 如果l == r，说明左边的数都是小于中轴值，右边的数都是大于中轴值，无需交换，退出。
14 if(l == r) {
15 break;
16 }
17 // 如果上面的语句没有执行，说明左边有比中轴值小的，右边有比中轴值大的，交换。
18 temp = arr[l];
19 arr[l] = arr[r];
20 arr[r] = temp;
21 // 交换完成，现在判断左边或右边的数是否和中轴值相同，如果相同，要进行前进或者后退，防止进入死循环。
22 if(arr[l] == pivot) {
23 r--;
24 }
25 if(arr[r] == pivot) {
26 l++;
27 }
28
29 }
30 // 上面循环完成，代表我们已经按照中轴值左边全是小于等于中轴值，右边全是大于等于中轴值的规则排序好了
31 // 首先判断上面排序完成后l和r是否相等，如果相等，要错开，否则会进行栈溢出
32 if(l == r) {
33 l++;
34 r--;
35 }
36 // 左边递归排序
37 if(left < r) { // 错开之后r是在左边的，所以这里就是r。
38 quickSort(arr, left, r);
39 }
40 // 左边部分排好了，接下来进行右边
41 if(right > l) { // 错开之后l是在左边的，所以这里就是l。
42 quickSort(arr, l, right);
43 }
44 }
加载全部内容