[编程题]排序
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] s = br.readLine().split(" ");
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(s[i]);
}
Arrays.sort(a);
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
}
}
发表于 2021-02-25 16:35:17
回复(0)
Java ，使用JavaAPI，冒泡排序，选择排序，插入排序，堆排序，归并排序，快速排序 七种解法
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static int[] array;
static int n;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
array = new int[n];
for (int i = 0; i < n; i++) array[i] = scanner.nextInt();
// apiSort();
// bubbleSort();
// selectSort();
// insertSort();
// heapSort();
// mergeSort(0, n - 1);
quickSort(0, n - 1);
for (int i : array) System.out.print(i + " ");
}
// 使用Java APi
static void apiSort() {
Arrays.sort(array);
}
// 交换两个数
static void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// 冒泡排序
static void bubbleSort() {
// 每趟往前归位一个最小值
for (int i = 1; i < n; i++)
for (int j = n - 1; j >= i; j--)
if (array[j] < array[j - 1]) swap(j, j - 1);
}
// 选择排序
static void selectSort() {
for (int i = 0; i < n - 1; i++) {
int k = i;
for (int j = i; j <= n - 1; j++)
if (array[j] < array[k]) k = j;
swap(k, i);
}
}
// 插入排序
static void insertSort() {
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
if (array[j] < array[j - 1]) swap(j, j - 1);
else break;
}
}
}
// 堆排序
static void heapSort() {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i : array) minHeap.add(i);
for (int i = 0; i < n; i++) array[i] = minHeap.poll();
}
// 归并排序
static void mergeSort(int i, int j) {
if (i >= j) return;
int mid = (i + j) >> 1;
mergeSort(i, mid);
mergeSort(mid + 1, j);
merge(i, mid, j);
}
static void merge(int i, int mid, int j) {
int[] temp = new int[n];
int l = i;
int r = mid + 1;
int t = i;
while (l <= mid && r <= j) temp[t++] = array[l] <= array[r] ? array[l++] : array[r++];
while (l <= mid) temp[t++] = array[l++];
while (r <= j) temp[t++] = array[r++];
System.arraycopy(temp, i, array, i, j - i + 1);
}
// 快速排序
static void quickSort(int i, int j) {
if (i >= j) return;
int pivot = partition(i, j);
quickSort(i, pivot - 1);
quickSort(pivot + 1, j);
}
static int partition(int i, int j) {
int v = array[i];
int l = i + 1;
int r = j;
while (true) {
while (l <= j && array[l] <= v) l++;
while (r >= i + 1 && array[r] >= v) r--;
if (l > r) break;
swap(l++, r--);
}
swap(i, r);
return r;
}
}
发表于 2020-03-17 20:51:44
回复(0)
import java.util.*;
public class Main {
private static void quickSort(int a[],int left,int right)
{
int i=left;
if(left>=right)
return;
int j=right;
int temp=a[left];
while(i!=j)
{
while(i<j&&a[j]>=temp)
j--;
if(j>i)
a[i]=a[j];
while(i<j&&a[i]<=temp)
i++;
if(i<j)
a[j]=a[i];
}
a[i]=temp;
quickSort(a,left,i-1);
quickSort(a,i+1,right);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());
String[] info = scanner.nextLine().split(" ");
scanner.close();
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = Integer.parseInt(info[i]);
}
quickSort(num, 0, n - 1);
for (int i = 0; i < n; i++) {
System.out.print(num[i] + " ");
}
}
}
public class Main {
private static void quickSort(int a[],int left,int right)
{
int i=left;
if(left>=right)
return;
int j=right;
int temp=a[left];
while(i!=j)
{
while(i<j&&a[j]>=temp)
j--;
if(j>i)
a[i]=a[j];
while(i<j&&a[i]<=temp)
i++;
if(i<j)
a[j]=a[i];
}
a[i]=temp;
quickSort(a,left,i-1);
quickSort(a,i+1,right);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());
String[] info = scanner.nextLine().split(" ");
scanner.close();
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = Integer.parseInt(info[i]);
}
quickSort(num, 0, n - 1);
for (int i = 0; i < n; i++) {
System.out.print(num[i] + " ");
}
}
}
发表于 2019-01-05 20:52:18
回复(0)
import java.util.Scanner;
import java.util.Arrays;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int[] nums = new int[n];
for(int i=0;i<n;i++){
nums[i] = sc.nextInt();
}
Arrays.sort(nums);
for(int i : nums){
System.out.print(i+" ");
}
}
}
}
发表于 2018-08-14 22:12:50
回复(0)
没借助第三方类库，手写了个希尔，准备写快排的但是发现大家都写烂了，希尔貌似看到的少。归并和堆以及其他基本排序也都会写了。加油！
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
int n = scan.nextInt();
int[] data = new int[n];
for (int i = 0; i < data.length; i++) {
data[i] = scan.nextInt();
}
shellSort(data);
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
}
}
private static void shellSort(int[] data) {
int len = data.length;
int i, j, temp;
for (int half = len / 2; half > 0; half /= 2) {
for (i = half; i < len; i++) {
temp = data[i];
j = i - half;
while (j >= 0 && temp < data[j]) {
data[j + half] = data[j];
j -= half;
}
data[j + half] = temp;
}
}
}
}
发表于 2018-05-29 09:52:32
回复(0)
import java.util.*;
public class Main{
public static int[] aux;
public static void bubbleSort(int[] arr){
int len = arr.length;
for(int i = len - 1; i >= 0; i--){
for(int j = 0; j < i; j++){
if(arr[j] > arr[j + 1]){
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}
public static void selectSort(int[] arr){
int len = arr.length;
for(int i = 0; i < len; i++){
int min = i;
for(int j = i + 1; j < len; j++){
if(arr[min] > arr[j]) min = j;
}
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
public static void insertSort(int[] arr){
int len = arr.length;
for(int i = 0; i < len - 1; i++){
for(int j = i + 1; j > 0; j--){
if(arr[j - 1] > arr[j]){
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
}
public static void quickSort(int[] arr, int low, int high){
if(low >= high){
return;
}
int i = low;
int j = high;
int pivot = arr[i];
while(i < j){
while(i < j && pivot <= arr[j])
j--;
arr[i] = arr[j];
while(i < j && pivot >= arr[i])
i++;
arr[j] = arr[i];
}
arr[i] = pivot;
quickSort(arr, low, i - 1);
quickSort(arr, i + 1, high);
}
public static void shellSort(int[] arr){
int len = arr.length;
int gap = 1;
while(gap < len / 3) gap = gap * 3 + 1;//塞奇书中提出的步长选取策略，平均复杂度能达到nlogn
for(; gap >= 1; gap /= 3){
for(int i = 0; i < len - gap; i += gap){
for(int j = i + gap; j > 0; j -= gap){
if(arr[j - gap] > arr[j]){
int temp = arr[j - gap];
arr[j - gap] = arr[j];
arr[j] = temp;
}
}
}
}
}
public static void mergeSort(int[] arr, int low, int high){
if(low >= high){
return;
}
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, high);
}
public static void merge(int[] arr, int low, int high){
int mid = (low + high) / 2;
int i = low;
int j = mid + 1;
for(int k = low; k <= high; k++){
aux[k] = arr[k];
}
for(int k = low; k <= high; k++){
if(i > mid){
arr[k] = aux[j++];
}else if(j > high){
arr[k] = aux[i++];
}else if(aux[i] < aux[j]){
arr[k] = aux[i++];
}else{
arr[k] = aux[j++];
}
}
}
public static void heapifySort(int[] arr){
int len = arr.length;
for(int i = len - 1; i > 0; i--){//此处不可写为i >= 0
maxHeapify(arr, i);
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
}
}
public static void maxHeapify(int[] arr, int n){
for(int i = (n - 1) / 2; i >= 0; i--){
int child = 2 * i + 1;
if(child != n && arr[child] < arr[child + 1]){
child++;
}
if(arr[i] < arr[child]){
int temp = arr[i];
arr[i] = arr[child];
arr[child] = temp;
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++){
arr[i] = sc.nextInt();
}
//bubbleSort(arr);
//selectSort(arr);
//insertSort(arr);
//quickSort(arr, 0, arr.length - 1);
//shellSort(arr);
//aux = new int[arr.length];
//mergeSort(arr, 0, arr.length - 1);
heapifySort(arr);
for(int i = 0; i < n; i++){
System.out.print(String.valueOf(arr[i]) + " ");
}
}
}
发表于 2018-03-20 22:07:22
回复(0)
import java.util.*;
public class Main {
public static void main(String [] args) {
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext()) {
int n= scanner.nextInt();
int [] a=new int[n];
for(int i=0;i<n;i++) {
a[i]=scanner.nextInt();
}
hSort(a,n);
//System.out.printf(Arrays.toString(a));
if(n==0)continue;
for(int i=0;i<n;i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}
scanner.close();
}
public static void hSort(int [] a,int n)
{
if(n<=1)return;
for(int i=n/2-1;i>=0;i--) {
sink(a, i, n-1);
}
int i=n-1;
while(i>0) {
int temp=a[i];
a[i]=a[0];
a[0]=temp;
sink(a, 0, i-1);
i--;
}
}
public static void sink(int[] a,int start,int end) {
int temp=a[start];
for(int j=2*start+1;j<=end;j=2*j+1) {
if(j<end&&a[j]<a[j+1])j++;
if(a[j]>temp) {
a[start]=a[j];
start=j;
}
}
a[start]=temp;
}
}
发表于 2017-09-06 11:47:55
回复(0)
//插入排序
import java.util.Scanner;
public class Main
{
public static void main(String []args)
{
Scanner in = new Scanner(System.in);
while(in.hasNext())
{
int count=in.nextInt();
int []a=new int[count];
for(int i=0;i<count;i++)
{
int insert=in.nextInt();
a[i]=insert;
for(int j=i;j>=0;j--)
{
if(insert<a[j])
{
a[j+1]=a[j];
a[j]=insert;
}
}
}
for(int i=0;i<count;i++)
{
System.out.print(a[i]+" ");
}
System.out.println();
}
}
}
发表于 2017-06-16 17:13:44
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()){
int n = sc.nextInt();
int[] sort = new int[n];
for (int i = 0; i < n; i++){
sort[i] = sc.nextInt();
}
for (int i = 0; i < n-1; i++){
for (int j = i+1; j < n; j++){
if (sort[i] > sort[j]){
int temp = sort[j];
sort[j] = sort[i];
sort[i] = temp;
}
}
}
for(int i = 0; i < n; i++){
System.out.print(sort[i] + " ");
}
System.out.println();
}
}
}
发表于 2017-06-12 00:42:45
回复(0)
import java.util.Scanner;
public class Main {
int data;
Main left;
Main right;
int zcc;
public static void main(String[] args) {
String[]arr ;
Scanner input=new Scanner(System.in);
Main ma=null;
while(input.hasNext()){
String n=input.nextLine();
//System.out.println("zzzz");
String str =input.nextLine();
arr= str.trim().split("\\s+");
ma =new Main(Integer.parseInt(arr[0]));
ma.xxx(ma,arr);
inOrder(ma);
System.out.println();
ma=new Main(Integer.parseInt(arr[0]));
}
}
public Main(int data) {
this.data=data;
left=null;
right=null;
this.zcc=0;
}
public void xxx(Main root,String[] arr){
for(int i=1;i<arr.length;i++){
insert(root, Integer.parseInt(arr[i]));
}
}
public void insert(Main root,int data){
if(data>root.data)
{
if(root.right==null){
root.right = new Main(data);
//System.out.println(root.data);
}else{
this.insert(root.right, data);
}
}else if(data<root.data){
if(root.left==null){
root.left = new Main(data);
//System.out.println(root.data);
}else{
this.insert(root.left, data);
}
}
else if(data==root.data){
//System.out.println(zcc);
root. zcc++;
}
}
public static void inOrder(Main root){ //中根遍历
if(root!=null){
inOrder(root.left);
System.out.print(root.data+" ");
for (int i = 0; i < root.zcc; i++) {
System.out.print(root.data+" ");
}
inOrder(root.right);
}
}
}
二叉树的中序遍历。效果很好
编辑于 2017-04-16 19:19:07
回复(0)
// insertSort import java.util.Scanner; /** * Created by Yuan on 2017/3/2. */ public class SortTest { public static void main(String[] args){ Scanner scanner=new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); int[] data = new int[n]; for (int i = 0; i < n; i++) { data[i] = scanner.nextInt(); } insertSort(data); for (int i=0;i<n-1;i++){ System.out.print(data[i]+" "); } System.out.println(data[n-1]); } } public static void insertSort(int[] data){ int len= data.length; for(int i=0;i<len-1;i++){ int j=i; int temp=data[i+1]; while (j>=0&&temp<data[j]){ data[j+1]=data[j]; j--; } data[j+1]=temp; } } }
发表于 2017-03-02 20:11:17
回复(0)
问题信息
难度：
11条回答
115收藏
19419浏览
通过挑战的用户
查看代码-
2023-03-14 15:41:40
-
2023-03-14 10:51:08
-
2023-03-13 23:03:17 -
2023-03-12 15:15:46
-
2023-03-12 12:50:40
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
