排序--08---堆排序

文章目录堆排序需求:实现步骤API设计堆构造过程树--07---堆的实现因为堆数组中的一半 是叶子节点,一半是非叶子节点.堆数组中最大索引处的父节点,就是最后一个非叶子节点图解流程:代码实现堆排序过程排序流程:图解流程:代码实现:堆排序总的代码测试:堆排序需求:给定一个数组String[] arr {“S”,“O”,“R”,“T”,“E”,“X”,“A”,“M”,“P”,“L”,“E”}请对数组中的字符按从小到大排序。实现步骤构造堆得到堆顶元素这个值就是最大值交换堆顶元素和数组中的最后一个元素此时所有元素中的最大元素已经放到合适的位置对堆进行调整重新让除了最后一个元素的剩余元素中的最大值放到堆顶重复2~4这个步骤直到堆中剩一个元素为止。API设计堆构造过程树–07—堆的实现堆的构造最直观的想法就是另外再创建一个和新数组数组然后从左往右遍历原数组每得到一个元素后添加到新数组中并通过上浮对堆进行调整最后新的数组就是一个堆。上述的方式虽然很直观也很简单但是我们可以用更聪明一点的办法完成它。创建一个新数组把原数组0 ~ length-1的数据拷贝到新数组的1~length处再从新数组长度的一半处开始往1索引处扫描从右往左然后对扫描到的每一个元素做下沉调整即可。因为堆数组中的一半 是叶子节点,一半是非叶子节点.堆数组中最大索引处的父节点,就是最后一个非叶子节点图解流程:代码实现publicclassHeapSort{//判断heap堆中索引i处的元素是否小于索引j处的元素privatestaticbooleanless(Comparable[]heap,inti,intj){returnheap[i].compareTo(heap[j])0;}//交换heap堆中i索引和j索引处的值privatestaticvoidexch(Comparable[]heap,inti,intj){Comparabletmpheap[i];heap[i]heap[j];heap[j]tmp;}//根据原数组source构造出堆heapprivatestaticvoidcreateHeap(Comparable[]source,Comparable[]heap){//把source中的元素拷贝到heap中heap中的元素就形成一个无序的堆System.arraycopy(source,0,heap,1,source.length);//对堆中的元素做下沉调整(从长度的一半处开始往索引1处扫描)for(inti(heap.length)/2;i0;i--){sink(heap,i,heap.length-1);}}//在heap堆中对target处的元素做下沉范围是0~rangeprivatestaticvoidsink(Comparable[]heap,inttarget,intrange){while(2*targetrange){//1.找出当前结点的较大的子结点intmax;if(2*target1range){if(less(heap,2*target,2*target1)){max2*target1;}else{max2*target;}}else{max2*target;}//2.比较当前结点的值和较大子结点的值if(!less(heap,target,max)){break;}exch(heap,target,max);targetmax;}}}堆排序过程排序流程:对构造好的堆我们只需要做类似于堆的删除操作就可以完成排序。将堆顶元素和堆中最后一个元素交换位置通过对堆顶元素下沉调整堆把最大的元素放到堆顶(此时最后一个元素不参与堆的调整因为最大的数据已经到了数组的最右边)重复1~2步骤直到堆中剩最后一个元素。图解流程:代码实现://对source数组中的数据从小到大排序publicstaticvoidsort(Comparable[]source){//构建堆Comparable[]heapnewComparable[source.length1];createHeap(source,heap);//定义一个变量记录未排序的元素中最大的索引intNheap.length-1;//通过循环交换1索引处的元素和排序的元素中最大的索引处的元素while(N!1){//交换元素exch(heap,1,N);//排序交换后最大元素所在的索引让它不要参与堆的下沉调整N--;//需要对索引1处的元素进行对的下沉调整sink(heap,1,N);}//把heap中的数据复制到原数组source中System.arraycopy(heap,1,source,0,source.length);}堆排序总的代码packagemain.java.Algorithms.heap;publicclassHeapSort{//判断heap堆中索引i处的元素是否小于索引j处的元素privatestaticbooleanless(Comparable[]heap,inti,intj){returnheap[i].compareTo(heap[j])0;}//交换heap堆中i索引和j索引处的值privatestaticvoidexch(Comparable[]heap,inti,intj){Comparabletmpheap[i];heap[i]heap[j];heap[j]tmp;}//根据原数组source构造出堆heapprivatestaticvoidcreateHeap(Comparable[]source,Comparable[]heap){//把source中的元素拷贝到heap中heap中的元素就形成一个无序的堆System.arraycopy(source,0,heap,1,source.length);//对堆中的元素做下沉调整(从长度的一半处开始往索引1处扫描)for(inti(heap.length)/2;i0;i--){sink(heap,i,heap.length-1);}}//对source数组中的数据从小到大排序publicstaticvoidsort(Comparable[]source){//构建堆Comparable[]heapnewComparable[source.length1];createHeap(source,heap);//定义一个变量记录未排序的元素中最大的索引intNheap.length-1;//通过循环交换1索引处的元素和排序的元素中最大的索引处的元素while(N!1){//交换元素exch(heap,1,N);//排序交换后最大元素所在的索引让它不要参与堆的下沉调整N--;//需要对索引1处的元素进行对的下沉调整sink(heap,1,N);}//把heap中的数据复制到原数组source中System.arraycopy(heap,1,source,0,source.length);}//在heap堆中对target处的元素做下沉范围是0~rangeprivatestaticvoidsink(Comparable[]heap,inttarget,intrange){while(2*targetrange){//1.找出当前结点的较大的子结点intmax;if(2*target1range){if(less(heap,2*target,2*target1)){max2*target1;}else{max2*target;}}else{max2*target;}//2.比较当前结点的值和较大子结点的值if(!less(heap,target,max)){break;}exch(heap,target,max);targetmax;}}}测试:publicclassHeapSortTest{publicstaticvoidmain(String[]args){// //待排序数组String[]arr{S,O,R,T,E,X,A,M,P,L,E};Integer[]arr1{2,55,6,-8,36,24,111,88,30};//通过HeapSort对数组中的元素进行排序HeapSort.sort(arr);HeapSort.sort(arr1);//打印排序后数组中的元素System.out.println(Arrays.toString(arr));System.out.println(Arrays.toString(arr1));}}