响应式装饰设计公司网站源码/seo课程总结怎么写

堆排序思想及代码实现

前言

对于一个数组，如果要实现数组中元素从小到大进行排序，此时这种需求就可以利用堆排序进行实现。本文讲解如果利用堆排序实现数组元素从小到大进行排序。

一、实现步骤

1.构造堆；
2.得到堆顶元素，这个值就是最大值；
3.交换堆顶元素和数组中的最后一个元素，此时所有元素中的最大元素已经放到合适的位置；
4.对堆进行调整，重新让除了最后一个元素的剩余元素中的最大值放到堆顶；
5.重复2~4这个步骤，直到堆中剩一个元素为止。

二、构造堆

1.由数组构造堆的思路一

堆的构造，最直观的想法就是另外再创建一个和新数组，然后从左往右遍历原数组，每得到一个元素后，添加到新数组中，并通过上浮，对堆进行调整，最后新的数组就是一个堆。

2.由数组构造堆的思路二

上述的方式虽然很直观，也很简单，但是我们可以用更聪明一点的办法完成它。创建一个新数组，把原数组的数据拷贝到新数组的1~length处，再从新数组长度的一半处开始往1索引处扫描（从右往左），然后对扫描到的每一个元素做下沉调整即可。
为什么是一半处？
因为堆的特性，前一半都是非叶子节点，后一半都是叶子节点，而叶子节点不能再下沉。

• 一次由数组构造堆的过程
  
  
  

3.思路二的具体代码实现

//根据原数组source，构造出堆heapprivate static void createHeap(Comparable[] source, Comparable[] heap){//1.拷贝source数组到heap数组中（heap[0]元素不用），此时heap一个无序的堆System.arraycopy(source,0,heap,1,source.length);//2.对前一半元素使用下沉算法，使得heap成为真正有序的堆for (int i = (heap.length-1)/2; i >0 ; i--) {sink(heap,i,heap.length-1);}}//在heap堆中，对target处的元素做下沉，范围是0~range。private static void sink(Comparable[] heap, int target, int range){//如果target位置结点的左子树存在，则循环遍历，将target位置结点与其左右子结点中较大的进行比较，若target位置处的结点小于较大的子结点，则交互while (2*target<=range){int maxIndex;//左右结点中较大结点的索引//如果右结点存在，则比较左右子结点中较大的结点if (2*target+1<=range){if (less(heap,2*target,2*target+1)){maxIndex=2*target+1;}elsemaxIndex=2*target;}//如果右结点不存在，则较大子结点就是左节点else{maxIndex=2*target;}//比较当前节点与较大子结点的大小，如果当前结点较小，则交换,否则，结束循环if(!less(heap,target,maxIndex)){break;}exch(heap,target,maxIndex);target=maxIndex;//继续下一次循环}}//判断heap堆中索引i处的元素是否小于索引j处的元素private static boolean less(Comparable[] heap, int i, int j){return heap[i].compareTo(heap[j])<0;}//交换heap堆中i索引和j索引处的值private static void exch(Comparable[] heap, int i, int j){Comparable temp=heap[i];heap[i]=heap[j];heap[j]=temp;}

三、堆排序

1.堆排序思路

对构造好的堆，我们只需要做类似于堆的删除操作，就可以完成排序。
1.将堆顶元素和堆中最后一个元素交换位置；
2.通过对堆顶元素下沉调整堆，把最大的元素放到堆顶(此时最后一个元素不参与堆的调整，因为最大的数据已经到了数组的最右边)
3.重复1~2步骤，直到堆中剩最后一个元素。

2.堆排序思路代码实现

 //对source数组中的数据从小到大排序public static void sort(Comparable[] source){Comparable[] heap = new Comparable[source.length + 1];//创建堆createHeap(source,heap);int maxIndex = heap.length-1;//通过循环不断交互索引1和最大索引处的元素，并下沉元素1，排除最大索引处的结点while (maxIndex!=1){exch(heap,1,maxIndex);maxIndex--;sink(heap,1,maxIndex);}//将堆数组拷贝到source数组System.arraycopy(heap,1,source,0,source.length);}

四、堆排序测试

//堆排序测试
public class HeapSortTest {public static void main(String[] args) {String[] arr = {"S","O","R","T","E","X","A","M","P","L","E"};HeapSort.sort(arr);System.out.println(Arrays.toString(arr));}
}