Java实现堆排序

电玩女神 2023-08-17 15:43 76阅读 0赞

> 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。

## 算法原理 ##

*  将数据看成是完全二叉树，根据完全二叉树的特性(堆序性)来进行排序的一种算法；
 *  完全二叉树：除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3OTIzNzYw_size_16_color_FFFFFF_t_70]
 *  堆序性(最大堆)：最大堆也叫大根堆即要求节点的元素都要不小于其孩子，且处于最大堆的根节点的元素一定是这个堆中的最大值；最小堆和其相反；
 *  堆排序是一种不稳定的排序算法；
 *  时间复杂度：O(n)+O(nlgn) ~ O(nlgn)；

## 分析 ##

1.  将数据的结构转为堆，然后构建大根堆，选出最大值取出；
2.  此时堆中没有根节点，继续构建新的大根堆，选出最大取出；
3.  重复以上步骤，得到排序后的数据；  
    ![这里写图片描述][70]

## 代码实现 ##

public class HeapSort { 
    	public static void heapSort(int[] arr) { 
    		// 构建第一个大根堆
    		// 实现堆序性，但其只能帮助我们得到最大值
    		// 在数组中可能不是正确的排序，因此需要继续调整堆
    
    		// 叶子结点：没有子节点
    		// 非叶子结点：有子节点
    		// int i = arr.length / 2 - 1, 我们从最后一层非叶子结点开始
    		for (int i = arr.length / 2 - 1; i >= 0; i--) { 
    			adjustHeap(arr, i, arr.length);
    		}
    		System.out.println("第一个大根堆：" + Arrays.toString(arr));
    
    		// 将大根堆最大值从堆中剔除放在数组最后，然后继续调整堆得到新的大根堆
    		// 再次剔除最大值放在数组后，然后继续调整堆得到新的大根堆
    		for (int j = arr.length - 1; j > 0; j--) { 
    			// 交换arr[0]和arr[j]的值，将最大值放入数组底部
    			swap(arr, 0, j);
    			// 调整没有根节点的堆，得到新的大根堆
    			adjustHeap(arr, 0, j);
    		}
    	}
    
    	private static void adjustHeap(int[] arr, int i, int length) { 
    		//取出arr[i]，防止其后续移动变化
    		int tmp = arr[i];
    		
    		for (int j = 2 * i + 1; j < length; j = 2 * j + 1) { 
    			// 让j先指向子节点中最大的节点
    			if (j + 1 < length && arr[j] < arr[j + 1]) { 
    				j++;
    			}
    
    			// 如果发现子节点更大，则进行值的交换
    			if (arr[j] > tmp) { 
    				swap(arr, i, j);
    				//i值变为其子节点的值，为下次循环比较子节点和根的大小做准备
    				i = j;
    			} else { 
    				break;
    			}
    		}
    	}
    
    	// 交换arr[i]和arr[j]的值
    	private static void swap(int[] arr, int i, int j) { 
    		int tmp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = tmp;
    	}
    
    	public static void main(String[] args) { 
    		int[] arr = {  96, 2, 1, 89, 21, 56, 19, 354, 0 };
    		System.out.println("初始数组：" + Arrays.toString(arr));
    		heapSort(arr);
    		System.out.println("排序后：" + Arrays.toString(arr));
    	}
    }
    //输出结果：
    	//初始数组：[96, 2, 1, 89, 21, 56, 19, 354, 0]
    	//第一个大根堆：[354, 96, 56, 89, 21, 1, 19, 2, 0]
    	//排序后：[0, 1, 2, 19, 21, 56, 89, 96, 354]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3OTIzNzYw_size_16_color_FFFFFF_t_70]: /images/20230810/d78ff5965975416a9260898e5a0b81c8.png
[70]: /images/20230810/a862bea61d13423bb3cf4ab52933745e.png