POJ2388 Who's in the Middle

题目链接：Who's in the Middle，题目与排序有关，使用快排实现

package com.test;

import java.util.Scanner;

public class Main {
    
    public static int partition(Integer []arr,int first,int last)
    {
        int low = first;
        int end = last;
        int key = arr[first];//取数组第一个数为轴值
        
        while(low < end)
        {
            //首先从右向左寻找第一个比轴值小的数，交换位置
            while(low < end && key <= arr[end])
            {
                end--;
            }
            
            if(low < end)
            {
                arr[low++] = arr[end];
            }
            
            //然后从左向右寻找第一个比轴值大的数，交换位置
            while(low < end && arr[low] <= key)
            {
                low++;
            }
            
            if(low <end)
            {
                arr[end--] = arr[low];
            }
        }
        
        arr[low] = key;

        return low;
    }
    
    public static void sort(Integer []arr,int first,int last)
    {
        if(first >= last)
        {
            return;
        }
        
        int index = partition(arr,first,last);
        sort(arr,first,index-1);
        sort(arr,index+1,last);
        
    }
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int arrLength = sc.nextInt();
        
        Integer[] arr = new Integer[arrLength];
        
        for(int i=0;i<arrLength;i++)
        {
            int temp = sc.nextInt();
            arr[i] = temp;
        }
        
        int first = 0;
        int last = arr.length-1;
        sort(arr,first,last);
        
        System.out.println(arr[arrLength/2]);
    }

}