堆排序 -- 算法小结

xiaoxiao2021-02-28  9

对于一个int数组,请编写一个堆排序算法,对数组元素排序。

给定一个int数组A及数组的大小n,请返回排序后的数组。

测试样例: [1,2,3,5,2,3],6 [1,2,2,3,3,5] 思路:首先以整个数组建一个大根堆,然后将根与最后一个结点交换,最后一个即有序,接着大根堆的大小-1,重新建立大根堆,重复上述过程 直至堆大小为1…..

import java.util.*; public class HeapSort { public int[] heapSort(int[] A, int n) { // write code here if(A==null||n<2){ return A; } buildHeap(A); //建堆 sort(A); //排序 return A; } public void buildHeap(int[] A){ for(int i=A.length/2-1;i>=0;i--){ buildMaxHeap(A,i,A.length-1); } } public void sort(int[] A){ for(int i=A.length-1;i>=0;i--){ change(A,0,i); buildMaxHeap(A,0,i-1); } } public void buildMaxHeap(int[] A,int i,int end){ int left = 2*i+1; int right = 2*i+2; int tem; if(left<=end&&A[left]>A[i]){ tem = left; }else tem = i; if(right<=end&&A[right]>A[tem]){ tem = right; } if(tem != i){ change(A,i,tem); buildMaxHeap(A,tem,end); } } public void change(int[] A,int a,int b){ if(a!=b){ int tem1= A[a]; A[a] = A[b]; A[b] = tem1; } } }

转载请注明原文地址: https://www.6miu.com/read-450237.html

最新回复(0)