Acwing 818. 数组排序

给定一个长度为$n$的数组$a$以及两个整数$l$和$r$，请你编写一个函数，void sort(int a[], int l, int r)，将 $a[l]\sim a[r]$从小到大排序。
输出排好序的数组 a。
输入格式
第一行包含三个整数$n，l，r$。
第二行包含$n$个整数，表示数组$a$。

输出格式
共一行，包含$n$个整数，表示排序完成后的数组$a$。

数据范围

0≤l≤r<n≤1000

输入样例：

5 2 4
4 5 1 3 2

输出样例：

4 5 1 2 3

代码 sort函数

import java.util.Scanner;
import static java.util.Arrays.sort;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), l = sc.nextInt(), r = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        sort(a, l, r + 1);//Java中左闭右开
        for(int i = 0; i < n; i++){
            System.out.printf("%d ", a[i]);
        }
    }

}

y总冒泡

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), l = sc.nextInt(), r = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        sort(a, l, r);
        for(int i = 0; i < n; i++){
            System.out.printf("%d ", a[i]);
        }
    }
    private static void sort(int a[], int l, int r){
        for(int i = r; i > l; i--){
            for(int j = l; j < i; j++){
                if(a[j] > a[j + 1]){
                    int tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;
                }
            }
        }
    }
}

y总快排
y总的快排好像和一般的那种写法不一样诶。回去翻了翻，快排在算法基础课里面，21年写的了，当时学的迷迷糊糊的。

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), l = sc.nextInt(), r = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        sort(a, l, r);
        for(int i = 0; i < n; i++){
            System.out.printf("%d ", a[i]);
        }
    }
    private static void sort(int a[], int l, int r){
        if(l >= r) return;
        int x = a[l + r >> 1];//y总基准元素取中间
        int i = l - 1, j = r + 1;
        while(i < j){
            while(a[++i] < x);
            while(a[--j] > x);
            if(i < j) swap(a, i, j);
        }
        sort(a, l, j);
        sort(a, j + 1, r);
    }
    private static void swap(int[] a, int i, int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

一般快排写法

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), l = sc.nextInt(), r = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        sort(a, l, r);
        for(int i = 0; i < n; i++){
            System.out.printf("%d ", a[i]);
        }
    }
    private static void sort(int a[], int l, int r){
        if(l >= r) return ;
        int i = l, j = r;
        int x = a[l];
        while(i < j){
            while(a[j] >= x && i < j) j--;
            while(a[i] <= x && i < j) i++;
            if(i < j) swap(a, i, j);
        }
        swap(a, l, j);
        sort(a, l, j - 1);
        sort(a, j + 1, r);
    }
    private static void swap(int a[], int i, int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}