《排序算法》——堆排序(大顶堆,小顶堆,Java)
2024-08-30 12:18:51
十大算法之堆排序:
堆的定义例如以下:
堆的定义例如以下:
n个元素的序列{k0,k1,...,ki,…,k(n-1)}当且仅当满足下关系时,称之为堆。
" ki<=k2i,ki<=k2i+1;或ki>=k2i,ki>=k2i+1.(i=1,2,…,[n/2])"
若将和此次序列相应的一维数组(即以一维数组作此序列的存储结构)看成是一个全然二叉树,
则全然二叉树中每个节点的值的都大于或等于随意一个字节的值(假设有的话)。称之为大顶堆。
则全然二叉树中每个节点的值的都小于或等于随意一个字节的值(假设有的话),称之为小顶堆。
由此,若序列{k0,k1,…,k(n-1)}是堆。则堆顶元素(或全然二叉树的根)必为序列中n个元素的最小值(或最大值)。
倘若给堆中每个节点都赋予一个整数值标签,根节点被标记为0。对于每个标记为i的节点,其左子节点(若存在的话)被标记为2*i+1,其右子节点(若存在的话)被标记为2*i+2,对于一个标记为i的非根节点,其父节点被标记为(i-1)/2。使用这个标记,我们可以将堆存储在数组中。节点存储在数据中的位置就使其标签。
package sort; import java.util.Arrays; /*
* 堆排序
* 堆的定义:满足 Ki <= K2i+1 Ki<=K2i+2 为小顶堆,满足 Ki >= K2i+1 Ki>=K2i+2 为大顶堆
* 此为大顶堆的代码实例,小顶堆相似
*/
public class duiSort { static int[] arr = {
16,7,3,20,17,8 //定义待排序数组
};
public static void main(String[] args) { buildHeap();//建立大顶堆并排序
System.out.println("排序好的为:" + Arrays.toString(arr));
} private static void buildHeap() {
// TODO Auto-generated method stub
int len = arr.length;
for(int i =len/2 -1 ;i>=0;i--) //建立大顶堆
{
sortHeap(i,len);
}
System.out.println("建立好的大顶堆例如以下:" + Arrays.toString(arr));
for(int j = len-1; j >0; j --) //对大顶堆进行排序
{
swap(0,j);
sortHeap(0,j);
}
} private static void sortHeap(int i, int len) {
// TODO Auto-generated method stub
int left = 2*i+1; //定义左节点
int right = 2*i +2; //定义右节点
int large = 0; //存放三个节点中最大节点的下标
if(len >left && arr[left] > arr[i]) //假设左孩子大于根节点 将左孩子下标赋值给large
large = left;
else //否之。将根节点下标赋值给large
large = i; if(len > right && arr[right] > arr[large])
large = right; //若右孩子节点大于根节点,把右孩子节点下标赋值给large if(large != i) //若最大节点的下标不等于根节点的下标时,交换其值
{
swap(large,i);
sortHeap(large,len);
}
}
//交换相应下标值
private static void swap(int m, int n) {
// TODO Auto-generated method stub
int temp ;
temp = arr[m];
arr[m] = arr[n];
arr[n] = temp;
}
}
最新文章
- AIX 环境下整理文件系统碎块
- Ubuntu 16.04 LTS 安装配置 Nginx 1.10.0 Php7.0-FPM
- 【iCore3 双核心板】例程二十七:DMA LAN实验——高速数据传输测速
- sql按天分组
- convert转化成特定日期格式
- 安装微软ASP.NET MVC 4,运行以下的包管理器控制台命令
- SQL SERVER 中的行列转换小结
- alfresco 5.0 document
- poj3071 Football
- java图片处理工具类
- XAMPP的MYSQL无法启动
- javascript什么是函数
- distributor之Interrupt Set/Clear-Active Registers, GICD_IS/CACTIVERn
- 原生AJAX基础讲解及兼容处理
- Unity加载外部图片
- 对Tomcat部署web应用的方式总结
- 【转】Vim速查表-帮你提高N倍效率
- iOS.Operation-on-ZipFile
- Linux之常用命令
- Django基础学习四_数据库的增删改查