十大排序算法之堆排序

本文采用Java书写选择排序，其他语言类似可以借鉴着写

• 思想：所谓堆排序就是通过构造最大堆（升序）或者最小堆（降序）来进行排列的方法。可能有些童鞋不知道何为最大堆，何为最小堆。这里来给大家简单说明一下，最大堆：也就是构造完成一个完全二叉树，父节点均大于子节点；同理最小堆为均小于子节点。堆排序的重点就是构造最大堆或者最小堆，然后依次提取出根节点元素，放在最后。再对之前的重新构造最大堆或者最小堆，重复执行，直到堆中仅剩一个元素。最大堆和最小堆因为都是完全二叉树, 因此满足完全二叉树的性质，可以利用数组进行存储。点击了解详情
• 效果图：
  
  效果图可能不太明显，这里我又找了两个图片便于大家理解
  
  
  

算法复杂度和稳定性

• 稳定性：
  不稳定，相同两个元素可能发生值得交换
• 复杂度：
  时间复杂度：O(NlogN)
  空间复杂度：O(1)

代码实现

package Sort;/*** @Description:* @ProjectNmae: gitTest* @PackageName: Sort* @ClassName: HeapSort* @Author: Y-peak* @Date: 2021.09.13 00:08   星期一*/public class HeapSort {public static void heapSort(int [] arr){if(arr == null || arr.length<2)return;for(int i = 0; i < arr.length; i++){ //生成最大堆，也就是大根堆heapInsert(arr,i);}int heapSize = arr.length; //堆的大小swap(arr,0, --heapSize); //根节点与最后一个结点互换，将最后一个结点从堆中删除。也就是将最大值排在了最后while (heapSize>0){heapify(arr, 0 , heapSize);swap(arr,0,--heapSize);}}//在将处于index处位置的数，持续上移public static void heapInsert(int[] arr, int index){while (arr[index] > arr[(index - 1) / 2]){swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}public static void swap(int[] arr, int i, int j){int temp;temp = arr[i];arr[i] = arr[j];arr[j] = temp;}//在将处于index处位置的数，持续下移public static void heapify(int[] arr, int index, int heapSize){int left = index*2+1; //左孩子下标while (left < heapSize){int largest = left+1 < heapSize && arr[left+1] > arr[left]?left + 1:left; //选出子孩子中较大的进行交换largest = arr[largest] > arr[index] ? largest:index; //选出父节点与子节点中较大的if(largest == index)break; //停止swap(arr, largest, index);index = largest;left = index* 2+1;}}public static void main(String[] args) {int[] arr = new int[]{24,29,45,73,24,89,90};heapSort(arr);for (int i :arr){System.out.println(i);}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！