您的位置 首页 java

java堆排序

堆排序就是先建立一个大堆,大堆的每一个子树的根都是最大的,然后尾巴元素和根交换,之后重新建大堆,再次找到最大的数放到根位置,继续交换即可

//堆排序 从小到大排序 应该是建大堆(能知道最上面是最大的)

public static void heapSort(int []array){

createHeap(array);

int end=array.length-1;

// while(){//循环 建立大堆 每次都是头最大 交换 尾巴节点

while (end>0){

int tmp=array[0];

array[0]=array[end];

array[end]=tmp;

adjust(array,0,end);

end–;

}

}

public static void adjust(int []array,int parent,int len){

int child=2*parent+1;

while(child<len){

if(child+1<len&&array[child+1]>array[child]){

child++;

}

if(array[child]>array[parent]){

int tmp=array[parent];

array[parent]=array[child];

array[child]=tmp;

parent=child;

child=2*parent+1;

}else {

break;

}

}

}

public static void createHeap(int []array){

for(int p=(array.length-1-1)/2;p>=0;p–){

adjust(array,p,array.length);

}

}

堆排序的时间复杂度为O(nlogn)空间复杂度为O(1) 稳定性:不稳定

文章来源:智云一二三科技

文章标题:java堆排序

文章地址:https://www.zhihuclub.com/174283.shtml

关于作者: 智云科技

热门文章

网站地图