Java教程

快排算法

本文主要是介绍快排算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一、基本思想

从数组中选择一个基准数值,一轮排序之后,基准数值左边的每一个数值比右边的每一个数值小。然后对基准数值左边右边的数值列表再重新排序,直到左边和右边子列表中不需要排序(只有一个数值)。

 

二、流程示例

     

 1、选择基准值,并定义排序区间

选择一个排序基准值,基准值可为任意位置的任意值,但是一般就以最左或最右的数值为基准值进行排序。

      

         思考: 这里下标是谁先动,有什么区别?

 2、下标左移或者右移,进行值比较并赋值

        如果你是正序排序,需要将小于基准值的给 l, ,大于基准值的 给 r

如果你选择了最左或者最右为基准,就需要反方向先动

①、l 下标先动,判断 l 值为 2,值不动(因为其是小于3的,满足排序规则,处于 l 的扫描范围)。l 下标继续向右移动,直到遇到了 

 

②、发现 4 大于基准值 3,且是在 l 的范围内,不在 r 的范围内,需要将改值放到 r 里面去

思考:这里是是谁继续动,有什么区别

 ③、r 向左移动

发现其值为 4 且在 r 的扫描范围内,则 r 继续向左移动

 

 ④、r 向左移动

发现其值小于基准值,且其不在 l 的扫描范围内,则需要将值给 l

 ⑤、l 向右移动 

但是其发现 与 r 装脸了,意味着 l + r 已经扫描完整个 区间了,则这一轮排序结束。

3、l 区间 和 r 区间内部排序

现在已经保证 l 中的任意值 小于 r 中的任意值, 但是不能保证 l 和 r 区间内 各自数值的顺序,需要对 l 和 r 区间进行排序

         重复对各自区间进行步骤 2 操作即可。

三、区间内左移和右移比较算法

 1 private int partition(int[] arr, int left, int right) {
 2         int current = arr[right];
 3         // 以谁未基准就需要反方向先动
 4         while (left < right) {
 5             while (left < right && arr[left] <= current) {
 6                 left++;
 7             }
 8             arr[right]=arr[left];
 9 
10             while (left < right && arr[right]>= current ) {
11                 right--;
12             }
13             arr[left] = arr[right];
14         }
15 
16         arr[right]=current;
17 
18         return left;
19     }

 四、算法示例

 1  public int[] sort(int[] arr) {
 2         quickSort(arr, 0, arr.length - 1);
 3         return arr;
 4     }
 5 
 6     public void quickSort(int[] arr, int left, int right) {
 7         if(left < right){
 8             int middle = partition(arr,left,right);
 9             quickSort(arr,left,middle-1);
10             quickSort(arr,middle+1,right);
11         }
12     }
13 
14     private int partition(int[] arr, int left, int right) {
15         var current = arr[right];
16         //很重要:以谁为基准就需要反方向先动
17         while (left < right) {
18             while (left < right && arr[left] <= current) {
19                 left++;
20             }
21             arr[right]=arr[left];
22 
23             while (left < right && arr[right]>= current ) {
24                 right--;
25             }
26             arr[left] = arr[right];
27         }
28 
29         arr[right]=current;
30 
31         return left;
32     } 
这篇关于快排算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!