堆排序-排序算法(七)

清疚 2023-03-01 13:33 28阅读 0赞

## 堆排序 ##

### 实现思路 ###

1.  将数组按照堆（最大堆、最小堆都可以）的结构进行整理

源数据：73,6,72,88,85,83,48,60,57,42
    整理后：88,85,83,60,73,72,48,6,57,42

1.  此时已经是一个最大堆，第一个元素，肯定是最大的，循环删除堆最大值，删除最大值把堆重新建立，把删除的值保存在另一个数组中

建立堆，logN，共建立N次  
额外开辟一个数组存放结果

此时，时间复杂度为O(NlogN)，空间复杂度为O(2N)，不划算呐

优化版：  
下面a为数组，size为数组长度

1.  将数组按照堆（最大堆、最小堆都可以）的结构进行整理
2.  将数组最大值（第0个元素）与堆末尾（size-1），重新把0～size-1长度的数组重组为堆，循环

第01次：85 73 83 60 42 72 48 6 57 |88 
    第02次：83 73 72 60 42 57 48 6 |85 88 
    第03次：73 60 72 6 42 57 48 |83 85 88 
    第04次：72 60 57 6 42 48 |73 83 85 88 
    第05次：60 48 57 6 42 |72 73 83 85 88 
    第06次：57 48 42 6 |60 72 73 83 85 88 
    第07次：48 6 42 |57 60 72 73 83 85 88 
    第08次：42 6 |48 57 60 72 73 83 85 88 
    第09次：6 |42 48 57 60 72 73 83 85 88 
    第10次：|6 42 48 57 60 72 73 83 85 88

### 代码实现 ###

public class 堆排序 { 
        public static void main(String[] args) { 
            int[] arr = new int[]{  73, 6, 72,88, 85, 83, 48, 60, 57, 42};
            MakeMaxHeap(arr, arr.length);
            for (int i : arr) System.out.print(i+",");
            
            System.out.println();
            
            MinHeap_Sort(arr, arr.length);
            for (int i : arr) System.out.print(i+",");
        }
    
        public static void MinHeap_Sort(int a[], int n) { 
            int temp;
            MakeMaxHeap(a, n);
            int index=1;
            for (int i = n - 1; i >= 0; i--) { 
                temp = a[0];
                a[0] = a[i];
                a[i] = temp;
                MaxHeapFixdown(a, 0, --n);
    
    //此处为打印排序过程，方便理解，可删除
                System.out.print("第" + index++ + "次：" );
                for (int j = 0; j < a.length; j++) { 
                    if (j==n) System.out.print("|");
                    System.out.print( a[j] + " ");
                }
                System.out.println();
    
            }
        }
    
        //构建最大堆
        public static void MakeMaxHeap(int a[], int n) { 
            for (int i = (n - 1) / 2; i >= 0; i--) { 
                MaxHeapFixdown(a, i, n);
            }
        }
    
        //从i节点开始调整,n为节点总数 从0开始计算 child节点的子节点为 2*parent+1, 2*parent+2
        public static void MaxHeapFixdown(int a[], int parent, int n) { 
            int temp, child;
            while (parent * 2 + 1 <= n - 1) { 
                child = parent * 2 + 1;
                if (child != n - 1 && a[child] < a[child + 1]) { 
                    child++;
                }
                if (a[parent] >= a[child]) { 
                    break;
                } else { 
                    temp = a[parent];
                    a[parent] = a[child];
                    a[child] = temp;
                }
                parent = child;
            }
        }
    
    }