Java基础大总结（进阶版1）

Charles776

247人浏览 · 2026-04-10 16:08:54

Charles776 · 2026-04-10 16:08:54 发布

排序大家庭

练习

题目1：冒泡排序

import java.util.Scanner;
import java.util.*;


public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int[] nums = {12,3,45,67,87,57,34,23,12,98,76,54,32,11};

		for(int i = 0 ; i < nums.length -1 ; i++){
			for(int j = 0 ; j < nums.length - i - 1 ; j++){
				if (nums[j] > nums[j+1]) {
					int temp = nums[j];
					nums[j] = nums[j+1];
					nums[j+1] = temp;
				}
			}
		}
		
		for(int num :nums){
			System.out.print(num + " ");
		}

		scanner.close();
	}
}

题目2：快速排序

题目描述

将读入的 N 个数从小到大排序后输出。

输入格式

第一行为一个正整数 N。

第二行包含 N 个空格隔开的正整数 ai，为你需要进行排序的数。

输出格式

将给定的 N 个数从小到大输出，数之间空格隔开。

输入输出样例

输入

5
4 2 4 5 1

输出

1 2 4 4 5

import java.util.*;


public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		int[] nums = new int[n];
		for(int i =0 ;i<n;i++){
			nums[i] = scanner.nextInt();
		}

		quickSort(nums, 0,nums.length-1);

		System.out.println(Arrays.toString(nums));

		scanner.close();
	}

	public static void quickSort(int[] nums , int left , int right){

		 if (left >= right) {
            return;
         }
		
		int pivot = nums[left];
		int i = left;
		int j =right;
	
		while(i < j){
			while(i < j && nums[j] >= pivot){
				j--;
			}

			if (i < j) {
				nums[i] = nums[j];
				i++;
			}

			while(i < j && nums[i] <= pivot){
				i++;
			}

			if(i < j){
				nums[j] = nums[i];
				j--;
			}
		}

		nums[i] = pivot;

		quickSort(nums, left , i - 1);
		quickSort(nums, i + 1, right);
	}
}

题目3：合并排序

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		int n = scanner.nextInt();
		int[] nums = new int[n];
		for (int i = 0; i < n; i++) {
			nums[i] = scanner.nextInt();
		}

		int[] newNums = new int [n];

		divide(nums, 0, n-1, newNums);

		System.out.println(Arrays.toString(newNums));

        scanner.close();
	}

	public static void divide(int[] nums, int left , int right , int[] newNums){
		if(left < right){
			int mid = (left + right) / 2;

			divide(nums, left, mid, newNums);

			divide(nums, mid+1, right, newNums);

			if(nums[mid] > nums[mid+1]){
				Combine(nums , left , mid , right , newNums);
			}
		}
	}

	public static void Combine(int[] nums, int left, int mid, int right, int[] newNums){
		int i = left;
		int j = mid + 1;
		int k = left;

		while (i <= mid && j <= right) {
			if (nums[i] <= nums[j]) {
			newNums[k++] = nums[i++];
			}else{
				newNums[k++] = nums[j++];
				}
			}
		
		while (i <= mid) {
			newNums[k++] = nums[i++];
			}
		
		while (j <= right) {
			newNums[k++] = nums[j++];
		}

		for (int t = left; t <= right; t++) {
    		nums[t] = newNums[t];
		}
	}

}

注意：

1.最后一定要拷贝回到nums，虽然输出是newNums，但是递归需要用到nums，所以必须拷贝

2.搞清楚指针动向，和快速排序区分

题目4：插入排序

import java.util.*;

public class Main{
	public static void main(String[] args){

		int[] nums = {12,1,65,26,39,53,97,84,43};

		for(int i=1; i<nums.length; i++){
			int temp = nums[i];
			int j = i-1;

			while(j>=0 && nums[j]>temp){
				nums[j+1] = nums[j];
				j--;
			}
			nums[j+1] = temp;
		}
		
		System.out.println(Arrays.toString(nums));
	}
}

注意：1.while的判断条件不可颠倒，否则容易出现短路

2.不可以使用两个for，因为，如果temp是最小值，那我们就实现在第二个for里替换（也就是执行不到else语句，只进行一直往后移位），导致第一个数不得排序

题目5：选择排序

import java.util.*;

public class Main{
	public static void main(String[] args){

		int[] nums = {12,1,65,26,39,53,97,84,43};

		for(int i = 0 ; i < nums.length ; i++){
			int minIndex = i;
			for(int j = i+1 ; j < nums.length ; j++){
				if (nums[j] < nums[minIndex]) {
					minIndex = j;
				}
			}
			if (minIndex != i) {
				int temp = nums[i];
				nums[i] = nums[minIndex];
				nums[minIndex] = temp;
			}
		}
		System.out.println(Arrays.toString(nums));
	}
}