本文主要介绍java数据结构堆排序的详细讲解和实例的相关资料，有需要的朋友可以参考一下。

1 堆排序

堆是一种重要的数据结构，分为大根堆和小根堆。这是一棵完整的二叉树。如果在底层使用数组存储数据，则假设一个元素编号为i(Java array从0开始，I为0到n-1)。如果它有左子树，那么左子树的位置是2i 1；如果有右子树，则右子树的位置为2i 2；如果有父节点，父节点的位置是(最大堆的任意子树的根节点不小于任意子节点，最小堆的根节点不大于任意子节点。

所谓堆排序就是利用堆这种数据结构的性质对数组进行排序。在数组的非降序排序中，需要大根堆，因为根据大根堆的性质，最大值必须在堆的顶部。堆排序是一种不稳定的排序算法，其时间复杂度为O(nlogn)。

2 算法思想

(1)建立最大堆；

(2)选择顶部，与零位元素交换；

(3)由于步骤(2)中的交换可能会打破最大堆的性质，即第0个位置的元素不再是最大元素，所以需要调用maxHeap来调整堆(结算方式)，并根据实际情况重复步骤(2)。

堆排序中最重要的算法是maxHeap。这个函数假设一个元素的两个子节点满足最大堆的性质(即左右子树都是最大堆)，只有根元素可能违反最大堆的性质。然后找出元素的最大元素和左右子节点。如果元素是最大的，那么整棵树就是最大堆，程序退出。否则交换根元素和最大元素的位置，继续调用maxHeap进行构建。

3 Java代码

公共类堆排序{

公共静态void main(String[] args) {

int[] arr={3，2，1，0，-1，-2，-3 }；

system . out . println(' Before heap:')；

打印数组(arr)；

堆排序(arr)；

System.out.println('堆排序后：')；

打印数组(arr)；

}

public static void heap sort(int[]arr){

if (arr==null || arr.length=1) {

返回；

}

buildMaxHeap(arr)；//建立最大堆

for(int I=arr . length-1；I=1；我- ) {

exchangeElements(arr，0，I)；//交换堆的顶部和0位置的元素。

maxHeap(arr，I，0)；//因为交换元素后，有可能违背堆的性质，所以把元素定下来

}

}

private Void BuildMaxEAP(int[]arr){//构建最大堆

if (arr==null || arr.length=1) {

返回；

}

int half=arr . length/2；

for(int I=half；I=0；我- ) {

maxHeap(arr，arr.length，I)；

}

}

私有静态void maxHeap(int[] arr，int heapSize，int index) {

int left=index * 2 ^ 1；//左侧子树中的元素

int right=index * 2 ^ 2；//右侧子树中的元素

int largest=index//初始化最大值元素

if(left heap size arr[left]arr[index]){

最大=左侧；

}

if(right heap size arr[right]arr[large]){

最大=右；

}

如果(索引！=large){//确定根元素是否为最大元素。

exchangeElements(arr，index，maximum)；

maxHeap(arr，heapSize，maximum)；

}

}

public static void print array(int[]arr){//打印数组

system . out . print(' { ')；

for(int I=0；长度；i ) {

system . out . print(arr[I])；

if (i arr.length - 1) {

System.out.print('，')；

}

}

system . out . println(' } ')；

}

公共静态void交换元素(int [] arr，int index 1，int index 2){//交换元素

int temp=arr[index 1]；

arr[index 1]=arr[index 2]；

arr[index 2]=temp；

}

}

感谢您的阅读，希望能帮到您，也感谢您对本站的支持！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。