Acwing 818. 数组排序

本文主要是介绍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;}
}

这篇关于Acwing 818. 数组排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---