最新字节跳动面试题之堆排序

• 堆排序是一个令人容易忘记的排序，你可能会对快排的partition记忆深刻，但是要你写出堆排序的代码还是得记忆一下关键点。
• 1.初始化堆（将数组结构调整为堆大的要求），2.堆顶和数组末尾进行对调。3.继续初始化堆。4.重复直到数组有序。
• 时间复杂度为：nlog(n)，空间复杂度为o(1).
• 思路总结：初始化的时候，需要从最末尾的一个非叶子节点从上进行堆化，堆化的核心是要求以该节点为根节点的子树满足堆的要求，首尾交换之后-需要从根节点开始向下进行堆化。

• 代码：

import java.lang.reflect.InvocationTargetException;
import java.util.Arrays;

class Main{
    public static void main(String[] args) throws ClassNotFoundException, NoSuchMethodException, InvocationTargetException, InstantiationException, IllegalAccessException {

        int []nums=new int[]{3,43,23,23,40,23,234,-234,0,0,0,213,231,8,9,0,6,5,3,2,2,4,5,6};
        HeapSort(nums);
        System.out.println(Arrays.toString(nums));
    }
    public static void HeapSort(int nums[]){
        int len = nums.length;
        //1.先进行初始化堆
        initHeapSort(nums,len);
        // 每次进行将堆顶和末尾进行交换
        for(int i = len-1;i>=0;i--){
            //首末进行交换
            swap(nums,0,i);
            len--;
            //从根位置进行堆调整
            heapfing(nums,0,len);
        }
    }
    public static void initHeapSort(int nums[],int len){
        //初始化应该从非叶子节点向上进行初始化
        for(int i = len/2-1;i>=0;i--){
            heapfing(nums,i,len);
        }
    }
    // 对i节点为根的子树进行判断是否满足堆的性质，从根往下进行调整
    public static void heapfing(int nums[],int i,int len){
        // 进行堆调整
        int left = i*2;
        int right = i*2 +1;
        int MaxIndex = i;
        if(leftnums[MaxIndex]){
            MaxIndex = left;
        }
        if(rightnums[MaxIndex]){
            MaxIndex = right;
        }
        //判断是否要进行交换
        if(i!=MaxIndex){
            swap(nums,i,MaxIndex);
            //对交换之后的子树进行判断是否满足堆的性质
            heapfing(nums,MaxIndex,len);
        }
    }
    public static void swap(int []nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

• 个人感觉和update操作一样。

• 回答的不是很好。

• 这个作为后端开发工程师应该不陌生。

• 面试需要尽可能体现你会的东西，要有项目可以讲，要是面试官没有项目点可以问，他就会问语言、计算机基础，不要慌。