架构师面试系列-堆排序

痛定思痛。 2023-02-23 10:59 87阅读 0赞

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；  
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；  
堆排序的平均时间复杂度为 Ο(nlogn)。

首先理解一下什么是完全二叉树  
一棵深度为K，有n个节点的二叉树，对树中节点按照从上至下，从左至右的顺序进行编号，如果编号为i（1<=i<=n）与满二叉树的编号为i的位置一致，则称此树为完全二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bnl1aHVhX2tleWJvYXJk_size_16_color_FFFFFF_t_70]

# 完全二叉树的性质 #

如果对具有n个节点二叉树的根节点从0开始编号，则序号为i的节点的双亲结点为(i-1)/2,左孩子的编号为2i+1，右孩子为2i+2。如果从1开始编号，则双亲结点编号为i/2，左孩子结点序号为2i，右孩子结点序号为2i+1.

# 堆排序实现 #

import java.util.Arrays;
    
    /** * 堆排序 * * 1、构建最大堆。 * 2、选择顶，并与第0位置元素交换 * 3、由于步骤2的的交换可能破环了最大堆的性质，第0不再是最大元素，需要调用maxHeap调整堆(沉降法)，如果需要重复步骤2 * * 动画演示地址： * * https://www.cs.usfca.edu/~galles/visualization/HeapSort.html * */
    public class HeapSort { 
    
        public int[] sort(int[] sourceArray){ 
            int[] arr= Arrays.copyOf(sourceArray,sourceArray.length);
            int len=arr.length;
            //构建大站堆
            buildMaxHeap(arr,len);
            //
            for(int i=len-1;i>=0;i--){ 
                swap(arr,0,i);
                len--;
                heapify(arr,0,len);
            }
            return arr;
        }
    
        //构建大站堆
        private void buildMaxHeap(int[] arr,int len){ 
            for(int i=(int)Math.floor(len/2);i>=0;i--){ 
                heapify(arr,i,len);
            }
        }
        //堆的比较方法
        private void heapify(int[] arr,int i,int len){ 
            int left=2*i+1;
            int right=2*i+2;
            int largest=i;
    
            //左子树大于根节点，将左子树和根节点进行交换
            if(left<len && arr[left] >arr[largest]){ 
                largest=left;
            }
            //右子树大于根节点，将右子树和根节点进行交换
            if(right<len && arr[right]>arr[largest]){ 
                largest=right;
            }
            //如果根节点发生变化，就进行转化，并继续比较，直到不发生变化为止
            if(largest!=i){ 
                swap(arr,i,largest);
                heapify(arr,largest,len);
            }
        }
    
        //交换函数
        private void swap(int[] arr,int i,int j){ 
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
    
        public static void main(String[] args) { 
            int[] resourceArray={ 12,23,234,33334,34,34,2234,56,34,34,567,443};
            HeapSort heapSort=new HeapSort();
            Arrays.stream(heapSort.sort(resourceArray)).forEach(System.out::println);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bnl1aHVhX2tleWJvYXJk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020070712035175.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bnl1aHVhX2tleWJvYXJk,size_16,color_FFFFFF,t_70