数据结构之堆排序

以你之姓@ 2022-08-11 17:30 125阅读 0赞

package com.zhiru;
    
    /*
     * 堆排序
     * 时间复杂度：O(n*log2n)
     * 空间复杂度：O(1)
     * 不稳定的排序算法
     */
    public class HeapSort {
    	private int[] heap;
    	private int maxSize;// 堆的最大容量
    	private int currentSize;// 堆目前容量
    	private static int defaultSize = 10;
    
    	HeapSort(int sz) {
    		maxSize = (defaultSize < sz ? sz : defaultSize);
    		heap = new int[maxSize];
    		currentSize = 0;//
    	}
    
    	HeapSort(int[] a) {
    		int len = a.length;
    		maxSize = (defaultSize < len ? len : defaultSize);
    		heap = new int[maxSize];
    		for (int i = 0; i < len; i++)
    			heap[i] = a[i];
    		currentSize = len;
    		int currentPos = (currentSize - 2) / 2;// 自下向上调整为最大堆
    		while (currentPos >= 0) {
    			siftDown(currentPos, currentSize - 1);
    			currentPos--;
    		}
    	}
    
    	// 最大堆的局部调整算法.
    	private void siftDown(int start, int m) {
    		int i, j;
    		i = start;// 开始节点
    		j = 2 * i + 1;// 开始节点的左子树
    		int temp = heap[i];
    		while (j <= m) {
    			if (j < m && heap[j] < heap[j + 1])
    				j++;// 左右子树那个大，走那边
    			if (temp >= heap[j])
    				break;// 父节点较子女结点大，跳出循环。
    			else {
    				heap[i] = heap[j];
    				i = j;
    				j = 2 * i + 1;
    			}
    		}
    		heap[i] = temp;// 回放
    	}
    
    	public void sort() {
    		// for(int i=(currentSize-2)/2;i>=0;i--)
    		// siftDown(i,currentSize-1);
    		// heap[0]有最大的排序码，每次循环将最大heap[0]与 heap[n-2]交换
    		// 然后将剩余元素调整为最大堆，堆顶就是次最大排序码，直到排好序为止。
    		for (int j = currentSize - 1; j >= 0; j--) {
    			printHeap();
    			System.out.print("\n");
    			heap[0] ^= heap[j];
    			heap[j] = heap[0] ^ heap[j];
    			heap[0] ^= heap[j];
    			siftDown(0, j - 1);
    		}
    	}
    
    	public void printHeap() {
    		if (heap != null && currentSize > 0) {
    			for (int i = 0; i < currentSize; i++) {
    				System.out.print(heap[i] + " ");
    			}
    		}
    	}
    
    }

49 25 21 25 16 8   
25 25 21 8 16 49   
25 16 21 8 25 49   
21 16 8 25 25 49   
16 8 21 25 25 49   
8 16 21 25 25 49