以中间数为基准的快速排序的分析实现

77 阅读 0 评论 51 点赞

我是靠谱客的博主慈祥向日葵，最近开发中收集的这篇文章主要介绍以中间数为基准的快速排序的分析实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思路分析

在这里插入图片描述

代码如下：

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);
        }

    }

}