堆排序的JAVA实现及时间复杂度分析

谁践踏了优雅 2021-09-22 14:26 194阅读 0赞

堆排序是一个比较常用的排序方式，下面是其JAVA的实现：

## 1. 建堆 ##

// 对输入的数组进行建堆的操作
        private static void buildMaxHeap(int[] array, int length) { 
            // 遍历所有的内部节点，每一个都进行siftdown操作
            for (int i = (int)Math.floor(length / 2 - 1); i >= 0; i--) { 
                siftdown(array, length, i);
            }
        }
    	
    	private static void siftdown(int[] array, int length, int index) { 
            // 1. 判断是否为叶子节点
            if (isLeaf(array, length, index)) { 
                return;
            }
    
            // 2. 计算左右两个值的大小
            int max = Integer.MIN_VALUE;
            int maxIndex = index;
            // 判断该内部节点是否有两个子树
            if (2 * (index + 1) > length - 1) { 
                max = array[2 * index + 1];
                maxIndex = 2 * index + 1;
            } else { 
                // 对两个子树的值进行比较
                if (array[2 * index + 1] > array[2 * (index + 1)]) { 
                    max = array[2 * index + 1];
                    maxIndex = 2 * index + 1;
                } else { 
                    max = array[2 * (index + 1)];
                    maxIndex = 2 * (index + 1);
                }
            }
    
            // 3. 如需交换，交换后继续向下递归
            if (array[index] < array[maxIndex]) { 
                array[maxIndex] = array[index];
                array[index] = max;
                siftdown(array, length, maxIndex);
            }
        }
    
        // 判断是否为叶子节点
        private static boolean isLeaf(int[] array, int length, int index) { 
            return index > (int)Math.floor(length / 2 - 1);
        }

## 2. 堆排序 ##

private static void heapSort(int[] array) { 
            buildMaxHeap(array, array.length);
            // 将堆顶的最大值每次都交换到最后，对剩余的数字进行新的建堆操作
            for (int i = 0; i < array.length; i++) { 
                int temp = array[array.length - i - 1];
                array[array.length - i - 1] = array[0];
                array[0] = temp;
                buildMaxHeap(array, array.length - i - 1);
            }
        }

## 3. 时间复杂度 ##

堆排序的时间复杂度主要有两个部分：

*  初始化建堆
 *  每次取堆顶元素后，剩余部分的排序

因此，我们来分别看一下这两个部分的时间复杂度

*  对于初始化建堆：我们需要对除了叶子节点这一层的其他节点都进行遍历，每一个点假设都递归到了叶子节点，需要 k - i 次siftdown操作，而每一层有 2^(i - 1) 个节点，（i代表层数，设根节点为第一层）即，我们需要计算 2^(i - 1) \* (k - i) ，当 i 取值为 1 到 n - 1时的值的和。  
    即求：  ∑ i = 1 n − 1 ( n − i ) 2 i − 1 \\sum\_\{i=1\}^\{n-1\} (n-i)2^\{i-1\} i=1∑n−1(n−i)2i−1  
    计算过程如下：  
     ∑ i = 1 n − 1 ( n − i ) 2 i − 1 = ∑ i = 1 n − 1 n ∗ 2 i − 1 − ∑ i = 1 n − 1 i ∗ 2 i − 1 \\sum\_\{i=1\}^\{n-1\} (n-i)2^\{i-1\} = \\sum\_\{i=1\}^\{n-1\} n\*2^\{i-1\} - \\sum\_\{i=1\}^\{n-1\} i\*2^\{i-1\} i=1∑n−1(n−i)2i−1=i=1∑n−1n∗2i−1−i=1∑n−1i∗2i−1  
    对于前半部分：  
     ∑ i = 1 n − 1 n ∗ 2 i − 1 = n ∗ ∑ i = 1 n − 1 2 i − 1 = n ∗ 1 ∗ ( 1 − 2 n − 1 ) 1 − 2 = n ∗ 2 n − 1 − n \\sum\_\{i=1\}^\{n-1\} n\*2^\{i-1\} = n\*\\sum\_\{i=1\}^\{n-1\} 2^\{i-1\} = n \* \\frac\{1\*(1-2^\{n-1\})\}\{1-2\}=n\*2^\{n-1\} - n i=1∑n−1n∗2i−1=n∗i=1∑n−12i−1=n∗1−21∗(1−2n−1)=n∗2n−1−n  
    对于后半部分：  
     S n = ∑ i = 1 n − 1 i ∗ 2 i − 1 = 2 0 + 2 ∗ 2 1 + 3 ∗ 2 2 + . . . + ( n − 1 ) ∗ 2 n − 2 S\_n = \\sum\_\{i=1\}^\{n-1\} i\*2^\{i-1\}=2^0+2\*2^1+3\*2^2+...+(n-1)\*2^\{n-2\} Sn=i=1∑n−1i∗2i−1=20\+2∗21\+3∗22\+...\+(n−1)∗2n−2  
     2 ∗ S n = 2 ∗ ∑ i = 1 n − 1 i ∗ 2 i − 1 = 2 1 + 2 ∗ 2 2 + 3 ∗ 2 3 + . . . + ( n − 1 ) ∗ 2 n − 1 2\* S\_n = 2\*\\sum\_\{i=1\}^\{n-1\} i\*2^\{i-1\}=2^1+2\*2^2+3\*2^3+...+(n-1)\*2^\{n-1\} 2∗Sn=2∗i=1∑n−1i∗2i−1=21\+2∗22\+3∗23\+...\+(n−1)∗2n−1  
     S n − 2 ∗ S n = − S n = 2 0 + 2 1 + 2 2 + . . . + 2 n − 2 − ( n − 1 ) ∗ 2 n − 1 = 2 n − 1 − n ∗ 2 n − 1 S\_n - 2\* S\_n =-S\_n=2^0+2^1+2^2+...+2^\{n-2\}-(n-1)\*2^\{n-1\}=2^n-1-n\*2^\{n-1\} Sn−2∗Sn=−Sn=20\+21\+22\+...\+2n−2−(n−1)∗2n−1=2n−1−n∗2n−1  
    即，两部分相加，有：  
     n ∗ 2 n − 1 − n + 2 n − 1 − n ∗ 2 n − 1 = 2 n − 1 − n n\*2^\{n-1\} - n+2^n-1-n\*2^\{n-1\}=2^n-1-n n∗2n−1−n\+2n−1−n∗2n−1=2n−1−n  
    由于，n代表的是层数，它可以由 n = log N 求得，代入，有：N - 1 - log N，故时间复杂度 **O(N) = N**
 *  第二部分，是关于排序的，我们交换堆顶元素不断放置到堆的末尾。即堆的元素是越来越少，我们比较的次数也减少，即求：  
     l o g ( n − 1 ) + l o g ( n − 2 ) … + l o g 3 + l o g 2 ≈ l o g ( n ! ) log(n-1)+log(n-2)…+log3+log2≈log(n!) log(n−1)\+log(n−2)…\+log3\+log2≈log(n!)  
    可以证明log(n!)和nlog(n)是同阶函数：  
    　　 ∵ ( n / 2 ) n / 2 ≤ n ! ≤ n n ∴ n / 2 log ⁡ ( n / 2 ) ≤ log ⁡ ( n ! ) ≤ n log ⁡ ( n ) ∵(n/2)^\{n/2\}≤n!≤n^\{n\} ∴n/2\\log(n/2) \\leq \\log(n!) \\leq n\\log(n) ∵(n/2)n/2≤n!≤nn∴n/2log(n/2)≤log(n!)≤nlog(n)  
    　  
    即可以知道第二部分的时间复杂度为O(nlogn)

将两部分结合起来，我们可以获得时间复杂度为O(n) = O(n + nlogn) = O(nlogn)