Menu

堆排序–思路代码

2018年4月27日 - 算法,数据结构

堆排序的步骤:

1.首先先将数组转换成二叉树

2.然后找出二叉树的最小堆(最大堆)

小顶堆:父元素比左右子元素都小

 

3.最小堆的概念:每个父节点比左右的子节点都小

调整为小顶堆之后,让堆顶元素与末尾元素进行交换,然后继续调整,直到序列有序

堆排序的代码实现:

public class HeapSort{

public static void main(string []args)

{

int []arr={9,8,7,6,5,4,3,2,1};

sort(arr);

System.out.println(Arrays.toString(arr));

}

public static void sort(int []arr)

{

//构建最大堆

for(int i=arr.length/2-1;i>=0;i–)

{

1 //从第一个非叶子结点从下至上,从右至左调整结构

adjustHeap(arr,i,arr.length);

}

2//调整堆结构+交换堆顶元素与末尾元素

for(int j=arr.length-1;j>0;j–)

swap(arr,0,j);//将堆顶元素与末尾元素交换

adjustHeap(arr,0,j);//重新对堆进行调整

}

///调整大顶堆

public static void adjustHeap(int []arr,int i,int length)

{

int temp=arr[i];//先取出当前元素i

for(int k=i*2+1;k<length;k=k*2+1)

{

if(k+1<length&&arr[k]<arr[l+1])

{

k++;

}

//从i结点的左子节点开始,也就是2i+1处开始

if(arr[k]>temp)

//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换

{

arr[i]=arr[k];

i=k;

}

else

{

break;

}

}

arr[i]=temp;

}

public static void swap(int []arr,int a,int b)

{

int temp=arr[a];

arr[a]=arr[b];

arr[b]=temp;

}

}

堆排序的时间复杂度都为O(nlogn)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: