22.1.8 堆排序、桶排序
1. 堆排序：时间复杂度：O(nlogn), 空间复杂度：O(1)
（1）完全二叉树：
- 第i个节点的左孩子：2*i+1；
- 第i个节点的右孩子：2*i+2；
- 第i个节点的父节点：(i-1)/2;
（2）大根堆：以节点i为根节点的子树中，节点i上的值是这棵子树中最大的。
（3）小根堆：以节点i为根节点的子树中，节点i上的值是这棵子树中最小的。
（4）code：
public static void main(String[] args) { int[] arr = {2,5,3,6,2,1,9,7,8}; heapSoft(arr); for(int cur:arr) System.out.print(cur+" "); } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void heapSoft(int[] arr) { if(arr == null || arr.length<2) return; int heapsize = arr.length;
（2）堆注意事项：
- 用系统提供的小根堆（例如，PriorityQueue
(3)比较器
- 相当于c++中的比较运算符重载，可以实现两个类实例化的变量之间的比较。可以配合java中Array.sort(待排序的数组，排序方式)一起使用。
- 返回值标准： 返回值为负数，第一个参数排在前面； 返回值为正数，第二个参数排在前面； 返回值为0；谁在前面无所谓。
- code:
import java.lang.*;import java.util.Arrays;import java.util.Comparator ;
- 运行结果：
Name : C, Id : 1, Age : 22 Name : A, Id : 2, Age : 23 Name : B, Id : 3, Age : 21
（4）桶排序
- 1)桶排序思想下的排序都是不基于比较的排序
- 2)时间复杂度为O(N)，额外空间负载度O(M)
- 3)应用范围有限，需要样本的数据状况满足桶的划分
- code:
undefined
Original: https://www.cnblogs.com/txzmy/p/15779618.html
Author: 张满月。
Title: 22.1.8 堆排序、桶排序
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/607597/
转载文章受原作者版权保护。转载请注明原作者出处！