堆排序的实现

不念不忘少年蓝@ 2022-04-11 02:51 366阅读 0赞

要想用堆来实现排序，首先得构建一个堆。

将字符串"SORTEXAMPLE"放入起始下标为1的数组中，构成一颗二叉树：![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70][]

构造堆时，从最后一个非叶子节点出发。如上图所示，最后一个非叶子节点下标为N/2=5，可以观察出任意一个大小为N的二叉堆的最后一个非叶子节点的标号都是N/2。从5开始一直到根节点1，一直进行sink操作，整个过程可以保证较大元素一直处于堆的上方，而较小元素则沉在堆的下方。如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70 1][]

此时，最大的元素X已在根节点，第二第三大的元素在堆的第二层……元素的大小按层次相对有序。此时，正式进入排序阶段：

将根节点与最后一个叶子节点交换（将堆中的最大元素拿出，并使堆的大小减一），然后将根节点sink到大小减一后的堆的合适位置，以此类推，直到堆的大小为1，排序便结束。为了形象地说明这一过程，请看下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70 2][]

给出代码：

public class HeapSort {
    	public static void sort(Comparable[] a) {
    		int N = a.length - 1;
    		/* 建堆 */
    		for (int k = N/2; k >= 1; k--) {
    			sink(a, k, N);
    		}
    		/* 排序 */
    		while (N > 1) {
    			exch(a, 1, N--);
    			sink(a, 1, N);
    		}
    	}
    	
    	public static void sink(Comparable[] a, int k, int h) {
    		while (k*2 <= h) {
    			int j = 2*k;
    			if (j < h && less(a[j], a[j+1]))
    				j++;
    			if (!less(a[k], a[j]))
    				break;
    			exch(a, k, j);
    			k = j;
    		}
    	}
    	
    	public static void exch(Comparable[] a, int p, int q) {
    		Comparable temp = a[p];
    		a[p] = a[q];
    		a[q] = temp;
    	}
    	
    	public static boolean less(Comparable v, Comparable w) {
    		return v.compareTo(w)<0;
    	}
    	
    	public static void showHeap(Comparable[] a) {
    		int N = a.length;
    		for (int i = 1; i < N; i++) {
    			System.out.print(a[i] + " ");
    		}
    		System.out.println("\n");
    	}
    }

测试结果：

public static void main(String[] args) {
    		Integer a[] = {null, 1, 3, 2, 4, 5, 95, 41, -34, -59};
    		sort(a);
    		showHeap(a);
    	}
    
    -59 -34 1 2 3 4 5 41 95

对于大小为N的堆，构造堆时的比较次数不大于2N，每次sink时最多可能需要2lgN次比较。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70]: /images/20220411/ffe16eaf324c4e39b539c3a827e72902.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70 1]: /images/20220411/9c88d5ab1c3741189909fc502296024f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70 2]: /images/20220411/2321bde3b3ef46c3b4db872c294a7ae8.png