算法排序----堆排序法

蔚落 2022-05-22 21:12 182阅读 0赞

以上三种排序实际上有很多相似之处，实际上都类似于插入排序，将元素和相邻元素或者一定距离元素进行比较，最终找到其合适位置。因此时间复杂度都为O(n²)或者O(n1.3).

那么接下来我将叙述一种算法，它是利用堆的思想进行排序的。

首先,堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

那么我们的堆排序用的就是大顶堆的思想进行排序的。

如果i从0开始计数，那么a\[i\] > =a\[2\*i+1\] &&a\[i\] >= a\[2\*i+2\]。

下面我来具体解释一下堆排序的思想。首先我们将一个数组按照顺序排列成一个完全二叉树，那么这个时候从最后一个非叶子结点和其左孩子及右孩子进行比较然后找出最大值，和父亲节点的值进行交换。那么最后一个非叶子结点的下标就是

数组的长度/2-1。大家可以进行验证。然后依次从最后一个非叶子结点一直循环到根节点重复之前的操作。这个时候我们就会发现根节点的值就是整个二叉树最大值，这个时候我们将原数组的第一个值和最后一个值进行替换。并重新构建大顶堆，这个时候的二叉树叶子数目就要减一了。

下面我来用一个图来演示一下我的思路

![70][]

数组长度是11，11/2-1 = 4.          array\[4\] = 23 它的左孩子和右孩子的值是  8 和 15。比根节点小.

同样的思路依次类推直到找到 父亲节点38 ，它的左孩子时97比它的值大，此时进行交换。整个大顶堆构造完毕后，97会处于最上方的根节点。将它和最后一个元素15的值进行交换。这个时候数组的最大值就放在了最后一个位置。我们在将剩余的元素进行重复的大顶堆构造即可。

下面这些是我的代码，是根据思路进行逐步的转换的。

/**
 * <h1>堆排序</h1>
 * <hr>
 * 时间复杂度nlogn
 * <hr>
 * 堆排序就是利用堆（假设利用大顶堆）进行排序的方法。 
 * 它的基本思想是，将待排序的序列构造成一个大顶堆。 
 * 此时，整个序列的最大值就是堆顶的父亲结点。 
 * 将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值）， 
 * 然后将剩余的 n-1 个序列重新构造成一个堆，这样就会得到 n 个元素中次大的值。 
 * 如此反复执行，便能得到一个有序序列了。 
 * <hr>
 * 堆排序的实现需要解决的两个关键问题： 
 （1）将一个无序序列构成一个堆。 
 （2）输出堆顶元素后，调整剩余元素成为一个新堆。 
 
 * @param array
 * @return
 */
 public int[] heapSort(int[] array){
 	int i;
 	/**
 	 * 构建一个大顶堆，将这个数组的最大值移动到数组的第一个位置
 	 * 实际上是从最后一个非叶子结点开始进行构建
 	 */
 		buildMaxHeap(array,array.length);
 	for(i = array.length-1;i>=0;i--){
 		//将堆顶记录和当前未经排序子序列的最后一个记录交换
 		int temp = array[0];
 		array[0] =array[i];
 		array[i] =temp;
 		buildMaxHeap(array, i);//将array中前i个记录重新调整为大顶堆
 	}
 	return array;
 }
 /**
 * 构建大顶堆
 * @param array 目标数组
 * @param length 数组长度减一为了防止越界
 */
 private void buildMaxHeap(int[] array,int length) {
 	int temp, j;
 	int i = length/2-1;
 	for(j = 2*i;i>=0;i--,j=2*i){//第一项是规定了j的初值，注意for循环第三项要对j进行重新的赋值操作，否则j的值是不变的
 		if((j+2)<length){
 			//说明最底层的最后一个非叶子结点有左孩子和右孩子
 			//那么就要找出父亲结点和左孩子还有右孩子中最大的一个结点，令父亲结点的值是内个值即可
 			//找出左孩子和右孩子中较大的值和父亲结点进行比较
 			int max,index;
 			if(array[j+1]<array[j+2]){
 				 max = array[j+2];//左孩子和右孩子中的较大值
 				 index = j+2;//较大值对应的坐标
 			}else{
 				 max = array[j+1];
 				 index = j+1;
 			}
 			//如果左孩子和右孩子中较大的值比父亲结点大，则和父亲结点进行交换
 			if(max>array[i]){
 				temp =array[i];
 				array[i] = max;
 				array[index] = temp;
 			}
 			//如果父亲结点比左孩子和右孩子的值都大那么不需要做任何改动
 		}
 		else{
 			//说明最后一个底层只有一个左孩子
 			//那么只需要比较左孩子和父亲结点的值就可以了
 			if(array[j+1]>array[i]){
 				int max = array[j+1];
 				array[j+1] = array[i];
 				array[i] = max;
 			}
 		}
 	}
 }

[70]: /images/20220523/99739f887bd247938dd0553be16c292a.png