java 对1 错23 tle 45 请求大佬帮帮忙这个快速排序

P1923 【深基9.例4】求第 k 小的数

StarryZiXuWang @ 2023-03-20 19:11:18

import java.io.*;

import java.util.*;

public class Main {

    public static void main(String[] args) {
      Scanner sc = new Scanner (System.in);
      int n =sc.nextInt();
      int k = sc.nextInt();
      int[] s = new int[n];
      for(int i = 0;i<s.length;i++)
      {
          s[i] = sc.nextInt();
      }
      quickSort(s , 0 , s.length-1);
     System.out.println(s[k]);

}

    public static  void quickSort(int[] arr,int low ,int high) {
        int i ,j,temp,t;
        if(low>high) {
            return;
        }
        i = low;
        j = high;
        temp = arr[low];

        while(i <j) {
            while(temp <= arr[j] && i<j) {
                j--;
            }
            while(temp>=arr[i] && i<j)
            {
                i++;
            }
            if(i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }

        }
        arr[low] = arr[i];
        arr[i] = temp;
       quickSort(arr,low,j-1);
       quickSort(arr,j+1,high);
    }
    }

by Bytejwz @ 2023-03-24 00:42:06

关于TLE的优化
和第n小没关系的区间就不用排了,比如本次排序1-10,求第2小,第一次排序中点选择了4,那么就排1-3就行了,后面的没必要排序,浪费时间


|