5.13. Optimized heap sorting

发布时间 ： 2025-10-25 13:35:41 UTC      

Page Views: 9 views

In the heap sorting in the previous section, we opened up additional space to construct and sort the heap. In this section, we optimize using in-situ heap sorting.

For a maximum heap, first exchange the starting position data with the value at the end of the array, then the end of the array is the largest element, then shift down the W element to regenerate the maximum heap, and then swap the newly generated maximum number with the penultimate position of the entire array, which is the penultimate big data everywhere, and so on.

The whole process can be shown in the following figure:

image0

5.13.1. Java instance code

源码包下载： Download

Src/runoob/heap/HeapSort.java file code: 

package runoob.heap; import runoob.sort.SortTestHelper; /*\* \* 原地堆排序 */ public class HeapSort { public static void sort(Comparable[] arr) { int n = arr.length; // 注意，此时我们的堆是从0开始索引的 // 从(最后一个元素的索引-1)/2开始 // 最后一个元素的索引 = n-1 for (int i = (n - 1 - 1) / 2; i >= 0; i--) shiftDown(arr, n, i); for (int i = n - 1; i > 0; i--) { swap(arr, 0, i); shiftDown(arr, i, 0); } } // 交换堆中索引为i和j的两个元素 private static void swap(Object[] arr, int i, int j) { Object t = arr[i]; arr[i] = arr[j]; arr[j] = t; } // 原始的shiftDown过程 private static void shiftDown(Comparable[] arr, int n, int k) { while (2 \* k + 1 < n) { //左孩子节点 int j = 2 \* k + 1; //右孩子节点比左孩子节点大 if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0) j += 1; //比两孩子节点都大 if (arr[k].compareTo(arr[j]) >= 0) break; //交换原节点和孩子节点的值 swap(arr, k, j); k = j; } } // 测试 HeapSort public static void main(String[] args) { int N = 100; Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000); sort(arr); // 将heapify中的数据逐渐使用extractMax取出来 // 取出来的顺序应该是按照从大到小的顺序取出来的 for (int i = 0; i < N; i++) { System.out.print(arr[i] + " "); } // 确保arr数组是从大到小排列的 for (int i = 1; i < N; i++) assert arr[i - 1] >= arr[i]; } }       
                
                

                    

                        

                            
                                文章链接
                            
                            ：
                            5.13. Optimized heap sorting 
                        

                    

                

            
        
        

            

    
        
        

            

                

                    
                        
                            
                                Web框架 
                            
                            
                        
                             946
                        
                    
                    
                    
                        

                            
 
 
 

                        

                    
                

                
                

            

        
    
    
        
        

            

                

                    
                        
                            
                                《地理信息系统原理、技术与方法》 
                            
                            
                        
                             97
                        
                    
                    
                    
                        

                            
 
 
 最近几年来，地理信息系统无论是在理论上还是应用上都处在一个飞速发展的阶段。 GIS被应用于多个领域的建模和决策支持，如城市管理、区划、环境整治等等，地理信息成为信息时代重要的组成部分之一； “数字地球”概念的提出，更进一步推动了作为其技术支撑的GIS的发展。 与此同时，一些学者致力于相关的理论研究，如空间感知、空间数据误差、空间关系的形式化等等。 这恰好说明了地理信息系统作为应用技术和学科的两个方面，并且这两个方面构成了相互促进的发展过程。 
 
 

                        

                    
                

                
                

            

        
    
    
        
        

            

                

                    
                        
                            
                                WEB基础 
                            
                            
                        
                             289