快速排序

软件发布|下载排行|最新软件

当前位置:首页IT学院IT技术

快速排序

Love&Share   2021-03-03 我要评论

一---基本思想

先给定一个数组{-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     }

 

Copyright 2022 版权所有 软件发布 访问手机版

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 联系我们