数据结构之排序算法——堆排序（Java实现）

一时失言乱红尘 2023-02-09 14:19 32阅读 0赞

➢ **基本介绍**

1.  堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为0(n log n),它也是不稳定排序。
2.  堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆，注意:没有要求结点的左孩子的值和右孩子的值的大小关系。
3.  每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
4.  大顶堆举例说明  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70_pic_center]  
    大顶堆特点: `arr[i]>=arr[2*i+1] && arr[i] >=arr[2*i+2]` //i对应第几个节点，i从开始编号  
    反之小顶锥就是小于。

➢ **基本思想**

1.  将待排序序列构造成一个大顶堆。
2.  此时，整个序列的最大值就是堆项的根节点。
3.  将其与末尾元素进行交换，此时末尾就为最大值。
4.  然后将剩余n-1个元素重新构造成一个堆， 这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]

➢**代码实现**

1.  构建大顶锥

// 构建大顶锥 i:索引 length：多少元素需要调整，length--
    	public static void BigHeap(int[] arr, int i, int length) { 
    		int temp = arr[i];
    		// 调整位置
    		// k = i * 2 + 1 k是i的左子节点
    		for (int k = i * 2 + 1; k < length; k = k * 2 + 1) { 
    			if (k + 1 < length && arr[k] < arr[k + 1]) {  // 左子节点的值小于右子节点的值
    				k++;
    			}
    			if (arr[k] > temp) {  // 子节点大于父节点进行交换
    				arr[i] = arr[k];
    				i = k;
    			} else { 
    				break;
    			}
    		}
    		arr[i] = temp;
    	}

详情见下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]  
添加交换方法

public static void heap(int[] arr) { 
    		int temp = 0;
    		for (int i = arr.length / 2 - 1; i >= 0; i--) { 
    			BigHeap(arr, i, arr.length);
    		}
    		for (int j = arr.length - 1; j > 0; j--) { 
    			temp = arr[j];
    			arr[j] = arr[0];
    			arr[0] = temp;
    			BigHeap(arr, 0, j);
    		}
    	}

在main函数当中进行测试：

int arr[] = {  4, 8, 9, 6, 2, 18, 51, 0, -4, 95, -78 };
    		heap(arr);
    		System.out.println(Arrays.toString(arr));

很显然：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]  
在先前发的博文当中对堆排序的时间效率进行测试：测试10000000个数据基本上在几秒之间，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200519135545189.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200521155025642.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200521162531286.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200521163911403.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200521164140207.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70