算法-排序算法：堆排序（HeapSort ）【O(nlogn)】

阳光穿透心脏的1/2处 2023-10-04 12:30 23阅读 0赞

MyArray.java

/**
     * 数组
     *
     * @author
     * @version 2018/8/4
     */
    public class MyArray<E> {
        
    
    	private E[] arr;
    	private int size;
    
    	public MyArray(int capacity){
        
    		arr = (E[])new Object[capacity];
    		size = 0;
    	}
    
    	public MyArray() {
        
    		this(10);
    	}
    
    	public int getSize(){
        
    		return size;
    	}
    
    	public int getCapacity(){
        
    		return arr.length;
    	}
    
    	public boolean isEmpty(){
        
    		return size == 0;
    	}
    
    	/**
    	 * 向数组头部插入一个元素
    	 *
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/4
    	 */
    	public void addFirst(E e){
        
    		add(0,e);
    	}
    
    	/**
    	 * 向数组尾部插入一个元素
    	 *
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/4
    	 */
    	public void addLast(E e){
        
    		add(size,e);
    	}
    
    	/**
    	 * 向数组指定位置插入一个元素
    	 *
    	 * @param index
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/4
    	 */
    	public void add(int index, E e){
        
    
    		if(index < 0 || index > size){
        
    			throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");
    		}
    
    		if(size == arr.length){
        
    //			throw new IllegalArgumentException("Add failed. Array is full.");
    			//数组动态扩容两倍
    			resize(2*arr.length);
    		}
    
    		for (int i= size-1; i >= index; i--){
        
    			arr[i+1] = arr[i];
    		}
    		arr[index] = e;
    		size++;
    	}
    
    	private void resize(int newCapacity) {
        
    		E[] newData = (E[]) new Object[newCapacity];
    		for (int i = 0; i < size; i++) {
        
    			newData[i] = arr[i];
    		}
    		arr = newData;
    	}
    
    	/**
    	 * 获取指定位置的元素
    	 *
    	 * @param index
    	 * @return E
    	 * @author ronglexie
    	 * @version 2018/8/4
    	 */
    	public E get(int index){
        
    		if(index < 0 || index >= size){
        
    			throw new IllegalArgumentException("Get failed. index is Illegal.");
    		}
    		return arr[index];
    	}
    
    	/**
    	 * 获取第一个元素
    	 *
    	 * @param
    	 * @return E
    	 * @author ronglexie
    	 * @version 2018/8/4
    	 */
    	public E getFirst() {
        
    		return arr[0];
    	}
    
    	/**
    	 * 获取最后一个元素
    	 *
    	 * @param
    	 * @return E
    	 * @author ronglexie
    	 * @version 2018/8/4
    	 */
    	public E getLast() {
        
    		return get(size - 1);
    	}
    
    	/**
    	 * 修改指定位置的元素
    	 *
    	 * @param index
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/4
    	 */
    	public void set(int index, E e){
        
    		if (index < 0 || index >= size){
        
    			throw new IllegalArgumentException("Set failed. index is Illegal.");
    		}
    		arr[index] = e;
    	}
    
    	/**
    	 * 查看数组中是否包含某个元素
    	 *
    	 * @param e
    	 * @return boolean
    	 * @author ronglexie
    	 * @version 2018/8/4
    	 */
    	public boolean contains(E e){
        
    		for (int i = 0; i < size; i++) {
        
    			if(arr[i].equals(e)){
        
    				return true;
    			}
    		}
    		return false;
    	}
    
    	/**
    	 * 查找元素在数组中的位置
    	 *
    	 * @param e
    	 * @return int
    	 * @author ronglexie
    	 * @version 2018/8/4
    	 */
    	public int indexOf(E e){
        
    		for (int i = 0; i < size; i++) {
        
    			if(arr[i].equals(e)){
        
    				return i;
    			}
    		}
    		return -1;
    	}
    
    	/**
    	 * 移除数组中的一个元素
    	 *
    	 * @param index
    	 * @return int
    	 * @author ronglexie
    	 * @version 2018/8/4
    	 */
    	public E remove(int index){
        
    		if (index < 0 || index >= size){
        
    			throw new IllegalArgumentException("Remove failed. index is Illegal.");
    		}
    
    		E result = arr[index];
    		for (int i = index + 1; i < size; i++) {
        
    			arr[i-1] = arr[i];
    		}
    		size--;
    		//修改对象引用，垃圾回收机制回收
    		arr[size] = null;
    
    		//动态缩小数组一半容量
    		if(size == arr.length/4 && arr.length/2 != 0){
        
    			resize(arr.length/2);
    		}
    		return result;
    	}
    
    	/**
    	 * 移除数组中的第一个元素
    	 *
    	 * @param
    	 * @return E
    	 * @author ronglexie
    	 * @version 2018/8/4
    	 */
    	public E removeFirst(){
        
    		return remove(0);
    	}
    
    	/**
    	 * 移除数组中的最后一个元素
    	 *
    	 * @param
    	 * @return int
    	 * @author ronglexie
    	 * @version 2018/8/4
    	 */
    	public E removeLast(){
        
    		return remove(size - 1);
    	}
    
    	/**
    	 * 移除数组中的某个元素
    	 *
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/4
    	 */
    	public void removeElement(E e){
        
    		int index = indexOf(e);
    		if(index != -1){
        
    			remove(index);
    		}
    	}
    
    	/**
    	 * 将索引为i和j的两个元素互相交换
    	 *
    	 * @param i
    	 * @param j
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/19
    	 */
    	public void swap(int i, int j){
        
    		if (i < 0 || i >= size || j < 0 || j >= size){
        
    			throw new IllegalArgumentException("Swap failed. index is Illegal.");
    		}
    		E temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    
    	/**
    	 * 自定义toString方法
    	 *
    	 * @param
    	 * @return java.lang.String
    	 * @author ronglexie
    	 * @version 2018/8/4
    	 */
    	@Override
    	public String toString(){
        
    		StringBuilder result = new StringBuilder();
    		result.append(String.format("Array: size = %d , capacity = %d\n",size,arr.length));
    		result.append("[");
    		for (int i = 0; i < size; i++){
        
    			result.append(arr[i]);
    			if(i != size - 1){
        
    				result.append(", ");
    			}
    		}
    		result.append("]");
    		return result.toString();
    	}
    
    }

MaxHeap.java

/**
     * 最大堆
     * 完全二叉树实现、树中的根结点都表示树中的最大元素结点
     *
     * @author ronglexie
     * @version 2018/8/19
     */
    public class MaxHeap<E extends Comparable<E>> {
        
    
    	private MyArray<E> arr;
    
    	public MaxHeap(int capacity){
        
    		arr = new MyArray<>(capacity);
    	}
    
    	public MaxHeap() {
        
    		arr = new MyArray<>();
    	}
    
    	// 返回堆中的元素个数
    	public int size(){
        
    		return arr.getSize();
    	}
    
    	public boolean isEmpty(){
        
    		return arr.isEmpty();
    	}
    
    	/**
    	 * 查找用数组实现的完全二叉树中该索引下节点的父亲节点的索引
    	 *
    	 * @param index
    	 * @return int
    	 * @author ronglexie
    	 * @version 2018/8/19
    	 */
    	public int parent(int index){
        
    		if(index == 0){
        
    			throw new IllegalArgumentException("root doesn't have parent.");
    		}
    		return (index - 1) / 2;
    	}
    
    	/**
    	 * 查找用数组实现的完全二叉树中该索引下节点的左孩子节点的索引
    	 *
    	 * @param index
    	 * @return int
    	 * @author ronglexie
    	 * @version 2018/8/19
    	 */
    	public int leftChild(int index){
        
    		return (index * 2) + 1;
    	}
    
    	/**
    	 * 查找用数组实现的完全二叉树中该索引下节点的右孩子节点的索引
    	 *
    	 * @param index
    	 * @return int
    	 * @author ronglexie
    	 * @version 2018/8/19
    	 */
    	public int rightChild(int index){
        
    		return (index * 2) + 2;
    	}
    
    	/**
    	 * 向最大堆中添加元素
    	 *
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/19
    	 */
    	public void add(E e){
        
    		arr.addLast(e);
    		shifUp(arr.getSize() - 1);
    	}
    
    	/**
    	 * 上浮节点
    	 *
    	 * @param k
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/19
    	 */
    	private void shifUp(int k) {
        
    		while (k > 0 && arr.get(parent(k)).compareTo(arr.get(k)) < 0){
        
    			arr.swap(k,parent(k));
    			k = parent(k);
    		}
    	}
    
    	/**
    	 * 查找堆中最大值
    	 *
    	 * @param
    	 * @return E
    	 * @author ronglexie
    	 * @version 2018/8/19
    	 */
    	public E findMax(){
        
    		if(arr .getSize() == 0){
        
    			throw new IllegalArgumentException("FindMax failed. heap is empty.");
    		}
    		return arr.get(0);
    	}
    
    	/**
    	 * 取出最大值
    	 *
    	 * @param
    	 * @return E
    	 * @author ronglexie
    	 * @version 2018/8/20
    	 */
    	public E extractMax(){
        
    		E result = findMax();
    
    		arr.swap(0,arr.getSize() - 1);
    		arr.removeLast();
    		siftDown(0);
    
    		return result;
    	}
    
    	/**
    	 * 下沉节点
    	 *
    	 * @param k
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/25
    	 */
    	private void siftDown(int k) {
        
    		while (k >= 0 && leftChild(k) < arr.getSize()){
        
    			int j = leftChild(k);
    			//找到k节点的左右子节点的最大值j
    			if (j + 1 < arr.getSize() && arr.get(j + 1).compareTo(arr.get(j)) > 0) {
        
    				j = rightChild(k);
    			}
    			// 运行到此，arr[j] 是 leftChild 和 rightChild 中的最大值
    			//比较大小判断是否还需要下沉操作
    			if(arr.get(k).compareTo(arr.get(j)) > 0){
        
    				break;
    			}
    			arr.swap(k,j);
    			k = j;
    		}
    	}
    
    }

## 一、非原地堆排序 ##

HeapSort.java

import java.util.Arrays;
    import java.util.Random;
    
    /**
     * Description: 堆排序.
     */
    public class HeapSort01 {
        
        final static int MAX=20; //待排序数组大小
        private HeapSort01(){
        }
    
        /**
         * 堆排序 
         * @param arr 待排序数组
         */
        public static void heapSort(int arr[]){
        
    
            MaxHeap<Integer> maxHeap = new MaxHeap<>();
            for(int elem : arr){
        
                maxHeap.add(elem);
            }
            for(int i = arr.length - 1; i>=0; i--){
        
                arr[i] = maxHeap.extractMax();
            }
    
        }
    
        public static void main(String[] args) {
        
            Random random=new Random();
            int []arr=new int[MAX];
            //生成随机数测试
            for(int i=0;i<MAX;i++){
        
                arr[i]= random.nextInt(20);
            }
            System.out.print("待排序数组：" + Arrays.toString(arr));
            long start=System.currentTimeMillis();
            heapSort(arr);
            long end=System.currentTimeMillis();
            System.out.println("\nheapSorting time cost:"+(end-start)+"ms");
            for (int anArray : arr) {
        
                System.out.print(anArray + " ");
            }
            System.out.println();
        }
    }

输出结果：

待排序数组：[12, 16, 5, 3, 0, 6, 8, 13, 7, 13, 9, 0, 1, 1, 15, 7, 4, 13, 15, 1]
    heapSorting time cost:4ms
    0 0 1 1 1 3 4 5 6 7 7 8 9 12 13 13 13 15 15 16

## 二、原地堆排序 ##

import java.util.Arrays;
    import java.util.Random;
    
    /**
     * Description: 堆排序. 原地排序
     */
    public class HeapSort02 {
        
        final static int MAX = 20; //待排序数组大小
    
         /**
         * 堆排序
         * @param arr 待排序数组
         */
        public static void heapSort(int[] arr) {
        
            if (arr.length <= 1) {
        
                return;
            }
            int length = arr.length;
            // heapify：将任意数组整理成堆的形状
            int parent_index = (length - 2) / 2;    // 最后一个叶子节点的父节点
            for (int i = parent_index; i >= 0; i--) {
        
                siftDown(arr, i, arr.length);
            }
            System.out.print("\nheapify后的数组：" + Arrays.toString(arr));
            for (int i = arr.length - 1; i >= 0; i--) {
        
                swap(arr, 0, i);    // 将最大值交换到i位置
                siftDown(arr, 0, i);
            }
            System.out.print("\n整理后的数组：" + Arrays.toString(arr));
        }
    
        /**
         * 下沉节点：对arr[0,n) 所形成的最大堆中，索引 k 的元素，执行siftDown
         */
        private static void siftDown(int[] arr, int k, int n) {
        
            while (leftChild(k) < n) {
        
                int j = leftChild(k);  //在此轮循环中，arr[k]与arr[j]交换位置
                //找到k节点的左右子节点的最大值j
                if (j + 1 < n && arr[j + 1] > arr[j]) {
        
                    j = rightChild(k);
                }
                // 运行到此，arr[j] 是 leftChild 和 rightChild 中的最大值
                //比较大小判断是否还需要下沉操作
                if (arr[k] >= arr[j]) {
        
                    break;
                }
                swap(arr, k, j);
                k = j;
            }
        }
    
        public static void swap(int[] arr, int i, int j) {
        
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        public static int leftChild(int index) {
        
            return (index * 2) + 1;
        }
    
        public static int rightChild(int index) {
        
            return (index * 2) + 2;
        }
    
        public static void main(String[] args) {
        
            Random random = new Random();
            int[] arr = new int[MAX];
            //生成随机数测试
            for (int i = 0; i < MAX; i++) {
        
                arr[i] = random.nextInt(20);
            }
            System.out.print("待排序数组：" + Arrays.toString(arr));
            long start = System.currentTimeMillis();
            heapSort(arr);
            long end = System.currentTimeMillis();
            System.out.println("\nheapSorting time cost:" + (end - start) + "ms");
            for (int anArray : arr) {
        
                System.out.print(anArray + " ");
            }
            System.out.println();
        }
    }

输出结果：

待排序数组：[15, 9, 10, 12, 7, 1, 12, 18, 12, 7, 0, 8, 17, 5, 15, 3, 2, 16, 8, 14]
    heapify后的数组：[18, 16, 17, 15, 14, 10, 15, 12, 12, 7, 0, 8, 1, 5, 12, 3, 2, 9, 8, 7]
    整理后的数组：[0, 1, 2, 3, 5, 7, 7, 8, 8, 9, 10, 12, 12, 12, 14, 15, 15, 16, 17, 18]
    heapSorting time cost:0ms
    0 1 2 3 5 7 7 8 8 9 10 12 12 12 14 15 15 16 17 18 
    
    Process finished with exit code 0