当前位置：首页 > article >正文

【蓝桥】宝藏排序Ⅱ----Array.sort和PriorityQueue

article 2024/11/22 10:55:00

在一个神秘的岛屿上，有一支探险队发现了一批宝藏，这批宝藏是以整数数组的形式存在的。每个宝藏上都标有一个数字，代表了其珍贵程度。然而，由于某种神奇的力量，这批宝藏的顺序被打乱了，探险队需要将宝藏按照珍贵程度进行排序，以便更好地研究和保护它们。作为探险队的一员，肖恩需要设计合适的排序算法来将宝藏按照珍贵程度进行从小到大排序。请你帮帮肖恩。

宝藏排序Ⅱ数据比较大，因此冒泡排序这里不行，Array.sort和
PriorityQueue在Java中排序性能更有且，这两种方法都能通过检测。

PriorityQueue

package yunkePra;

import java.util.PriorityQueue;
import java.util.Scanner;

public class p5test {
	public static void main(String[] args) {
	   Scanner scan = new Scanner(System.in);
	   int n=scan.nextInt();
	   PriorityQueue<Integer> queue = new PriorityQueue<>();
	   for(int i=0;i<n;i++) {
		   int num=scan.nextInt();
		   queue.add(num);
	   }
	   for(int i=0;i<n;i++) {
		   System.out.print(queue.remove()+" ");
	   }
       scan.close();
	}
}

Arrays.sort

package yunkePra;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class p5testSort {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		   int n=scan.nextInt();
		   int[] arr = new int[n];
		   for(int i=0;i<n;i++) {
			   arr[i]=scan.nextInt();
		   }
		   Arrays.sort(arr);
		   for(int i=0;i<n;i++) {
			   System.out.print(arr[i]+" ");
		   }
	       scan.close();
	}
}

让我们比较一下Java的PriorityQueue和Arrays.sort()方法在排序上的区别：

`PriorityQueue`

排序方式：
- PriorityQueue实现了一个优先级队列，它不是一个排序方法，但可以通过不断取出最小（或最大）元素来模拟排序。
- 它使用堆（Heap）数据结构，默认是最小堆（Min Heap），每次remove()操作返回并移除堆中最小的元素。
性能：
- 插入元素（add）的复杂度是 (O(\log n))。
- 移除最小元素（remove）的复杂度也是 (O(\log n))。
- 总体排序时间复杂度为 (O(n \log n))。
空间复杂度：
- 需要额外的 (O(n)) 空间来存储队列。
稳定性：
- PriorityQueue不是稳定的，因为堆的性质会导致相同优先级的元素顺序可能改变。
适用性：
- 适用于需要频繁插入和删除最小（或最大）元素的场景，而不是一次性排序。

`Arrays.sort()`

排序方式：
- Arrays.sort()方法在Java 7及之前使用的是快速排序（QuickSort），在Java 8及之后改为使用双轴快速排序（Dual-Pivot Quicksort），这是一种改进的快速排序算法。
- 它是原地排序，不需要额外的空间来存储数据。
性能：
- 平均时间复杂度为 (O(n \log n))，最坏情况也为 (O(n \log n))。
- 实际性能通常优于PriorityQueue模拟排序，因为它是专门为排序设计的算法。
空间复杂度：
- 对于原始类型数组，空间复杂度为 (O(\log n))（用于递归调用栈）。
- 对于对象数组，空间复杂度为 (O(n))（因为对象引用需要被复制）。
稳定性：
- Arrays.sort()是稳定的（在Java 8及之后）。
适用性：
- 适用于一次性排序整个数组或列表。