堆排序
2021-07-02 11:05
标签：快速排序 else imp 重要 维数 int str 时间复杂度 一个 原创 堆排序和快速排序的时间复杂度是相同的，掌握堆排序也是非常重要的! 用一维数组存储堆，有以下规律： 首先讲述堆向下调整的过程： 假设从根结点开始向下调整堆（调整为最小堆），将结点i与两个子结点中较小的一个交换， 假如i与右儿子交换了，将右儿子的坐标赋值给i，然后再重复上面的比较过程和交换过程，直到根 结点比两个子节点都小，说明调整完毕！ 排序过程就是将需要排序的数输入数组后，从最后一个非叶子结点开始向下调整，接着将倒数第二个 非叶子结点向下调整！ 20:10:58 2018-09-11 堆排序 标签：快速排序 else imp 重要 维数 int str 时间复杂度 一个 原文地址：https://www.cnblogs.com/chiweiming/p/9629883.html
1 import java.util.*;
2
3 public class 堆排序 {
4
5 static int n; //需排序的个数
6 static int array[];
7
8 static void swap(int a,int b) {
9 int temp;
10 temp=array[a];
11 array[a]=array[b];
12 array[b]=temp;
13 }
14
15 //向下调整
16 static void siftdown(int i) {
17 int flag=0; //标识是否需要继续向下调整
18 int t=i; //存储3个结点中值最小的结点编号
19 //判断结点i是否有左儿子
20 while(i*2) {
21 if(array[i*2]array[t]) {
22 t=i*2;
23 }
24 if(i*2+1n) {
25 if(array[i*2+1]array[t]) {
26 t=i*2+1;
27 }
28 }
29 if(t!=i) {
30 swap(t,i);
31 i=t;
32 }
33 else {
34 flag=1;
35 }
36 }
37 }
38
39 //建立堆
40 static void create() {
41 //第一个非叶结点的编号为n/2
42 for(int i=n/2;i>=1;i--) {
43 siftdown(i);
44 }
45 }
46
47 static int deletemax() {
48 int t;
49 t=array[1];
50 array[1]=array[n];
51 n--;
52 siftdown(1);
53 return t;
54 }
55
56 public static void main(String[] args) {
57 Scanner reader=new Scanner(System.in);
58 n=reader.nextInt();
59 array=new int[n+1];
60 //输入要排序的数
61 for(int i=1;i) {
62 array[i]=reader.nextInt();
63 }
64 create();
65 int num=n;
66 for(int i=1;i) {
67 System.out.print(deletemax()+" ");
68 }
69 }
70
71 }
下一篇：Python基础之集合set