排序之堆排序

我会带着你远行 2022-08-21 01:27 15阅读 0赞

今天看了算法导论堆排序这一章，将自己的代码实现和理解与大家分享一下。

这里分析的是大堆：

最大堆的性质是除了根结点以外的所有结点i都要满足：A\[PARENT(i)\]>=A\[i\].也就是说某结点的值最多与其父结点一样大。

我们还可以知道，堆结构上的一些基本操作的运行时间至多与树的高度成正比：时间复杂度为O(lgn)。

基本代码有求堆的左孩子，右孩子，父结点的代码如下：

public static int LEFT(int i) {
    		return (i << 1) + 1; // 括号必须要，否则先做加法运算
    	}
    
    	public static int RIGHT(int i) {
    		return (i << 1) + 2;
    	}
    
    	public static int PARENT(int i) {
    		return (i - 1) >> 1;
    	}

元素A与元素B交换的代码：

public static void SWAP(int[] A, int i, int j) {
    		int temp = A[i];
    		A[i] = A[j];
    		A[j] = temp;
    		return;
    	}

我代码中有三个关键的函数：

MAX\_HEAPIFY：时间复杂度为O(lgn)（稍后我会证明），它是维护最大堆性质的关键。

BUILD\_MAX\_HEAP：具有线性时间复杂度，功能是从无序的输入数据数组中构造一个最大堆。

HEAP\_SORT：时间复杂度为O(nlgn)，功能是对一个数组进行原址排序（在排序过程中仅有常数个元素需要存储在数组外）。

下面我来说说我对其中一些知识的理解：

好多同学对当MAX－HEAPIFY作用在一棵以结点i为根的、大小为n的子树上时……………i结点的子树大小至多为2n/3(最坏情况发生在最低层恰好半满的时候)，这句话不理解。为什么子树大小至多为2n/3？解释如下图：

![20160309212156687][]

因此可以得到MAX\_HEAPIFY的运行时间函数：

T(n) =T(2n/3)+O(1)

用主方法解出来，时间复杂度就是O(lgn)。

BUILD\_MAX\_HEAP的时间复杂度是O(n)，算法导论上面有证明所以我就不写了（其实是画图没工具……）。

HEAP\_SORT的时间复杂度是O(nlgn)。因为每次调用BUILD\_MAX\_HEAP的时间复杂度是O(n)，而n-1次调用MAX\_HEAPIFY，每次时间为O(lgn)。

故时间复杂度为O((n-1)\*lgn)，即O(nlgn)。

这三个函数的实现如下：

public static void MAX_HEAPIFY(int[] A, int i, int Heap_Size) {
    		int Largest = i;
    		int L = LEFT(i), R = RIGHT(i);
    		if (L < Heap_Size && A[L] > A[i]) {
    			Largest = L;
    		}
    		if (R < Heap_Size && A[R] > A[Largest]) {
    			Largest = R;
    		}
    
    		if (Largest != i) {
    			SWAP(A, i, Largest);
    			MAX_HEAPIFY(A, Largest, Heap_Size);
    		}
    	}
    
    	public static void BUILD_MAX_HEAP(int[] A) {
    		for (int i = (A.length - 1) / 2; i >= 0; i--) {
    			MAX_HEAPIFY(A, i, A.length);
    		}
    	}
    
    	public static void HEAP_SORT(int[] A) {
    		int Heap_Size = A.length;
    		for (int i = A.length - 1; i >= 1; i--) {
    			SWAP(A, 0, i);
    			Heap_Size--;
    			MAX_HEAPIFY(A, 0, Heap_Size);
    		}
    	}

public static void main(String[] args) {
    		int[] Heap = new int[] { 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };
    		BUILD_MAX_HEAP(Heap);
    		HEAP_SORT(Heap);
    		for (int i = 0; i < Heap.length; i++) {
    			System.out.print(Heap[i] + ",");
    		}
    	}

最后的main是测试函数。

大家可以试试，如果有问题了，请留言。

[20160309212156687]: /images/20220731/bd4d6878e0de4e4da015db41a4fca854.png