以中间数为基准的快速排序的分析实现_快速排序选择中位数作为基准值java

思路分析

代码如下：

package com.shujujiegou;


import sun.awt.im.SimpleInputMethodWindow;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Hello {
    public static void main(String[] args) {
        int arr[]=new int[]{-9,78,0,23,-567,70,-1,900,456,1};
        System.out.println("排序前的数组是："+Arrays.toString(arr));
        System.out.println("***************");
        xuanze(arr,0,arr.length-1);
        System.out.println("***************");
        System.out.println("排序后的数组是："+Arrays.toString(arr));

    }
    public static void xuanze(int []arr,int zuo,int you){
        int l=zuo; //左索引
        int r=you; //右索引
        int pivot=arr[(zuo+you)/2];
        int temp=0; //临时变量
        //while循环的目的是比pivot小的放他左边，比pivot大的放他右边
        while (l<r){
            while (arr[l]<pivot){
                l+=1;
            }
            while ((arr[r]>pivot)){
                r-=1;
            }
            //如果是这样，说明pivot的左右两的值，已经按照左边全是小等于pivot、右边全是大等于pivot值
            if(l>=r){
                break;
            }

            //交换
            temp=arr[l];
            arr[l]=arr[r];
            arr[r]=temp;

            //如果交换完后，发现这个arr【l】==pivot值相等 r-- 前移一下
            if(arr[l]==pivot){
                r-=1;
            }

            //如果交换完后，发现这个arr【r】==pivot值相等 l++ 后移一下
            if(arr[r]==pivot){
                l+=1;
            }
        }
        //如果l==r，必须l++ r-- 否则为出现栈溢出
        if(l==r){
            l+=1;
            r-=1;
        }
        //向左递归
        if (zuo<r) {
            xuanze(arr,zuo,r);
        }

        //向右递归
        if(you>l){
            xuanze(arr,l,you);
        }

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

代码运行效果如下：