java 堆排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java 堆排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2539字,纯文字阅读大概需要4分钟。
内容图文
package wangChaoPA实习工作练习.com.进阶篇.排序;
import java.util.ArrayList;
/**
*
* <p>
* 描述该类情况 {@link 代表跟谁有关系}
* </p>
*
* @author 王超
* @since 1.0
* @date 2017年5月10日 下午5:44:42
* @see 新建|修改|放弃
* @see wangChaoPA实习工作练习.com.进阶篇.排序.Heap
*/
public class Heap<E extends Comparable>
{
private ArrayList<E> list = new ArrayList<E>();// 使用ArrayList实现堆排序
public Heap()
{
}
public Heap(E[] objects)
{
for (int i = 0; i < objects.length; i++)
{
add(objects[i]);
}
}
// 添加
public void add(E newObject)
{
// 添加到list
this.list.add(newObject);
// 获取到添加到list中newObject的索引值
int currentIndex = this.list.size() - 1;
while (currentIndex > 0)
{
// 获取到父节点的索引
int parentIndex = (currentIndex) / 2;
// 如果新增元素的值大于父节点的值则进行swap
if (list.get(currentIndex).compareTo(list.get(parentIndex)) > 0)
{
E temp = this.list.get(currentIndex);
this.list.set(currentIndex, this.list.get(parentIndex));
this.list.set(parentIndex, temp);
}
else
{
break;
}
currentIndex = parentIndex;
}
}
// 堆的大小
public int getSize()
{
return this.list.size();
}
// 删除
public E remove()
{
if (this.list.size() == 0)
{
return null;
}
// 首元素 即最大的元素
E removeObject = this.list.get(0);
// 把最后的一个元素置于第一个
this.list.set(0, this.list.get(this.list.size() - 1));
// 删除最后一个元素
this.list.remove(this.list.size() - 1);
int currentIndex = 0;
while (currentIndex < this.list.size())
{
// 获取到新首元素的子节点索引
int leftChildIndex = currentIndex * 2 + 1;
int rightChildIndex = currentIndex * 2 + 2;
if (leftChildIndex >= this.list.size())
{
break;
}
// 获取子节点中大的索引值
int maxIndex = leftChildIndex;
if (rightChildIndex < this.list.size())
{
if (this.list.get(maxIndex)
.compareTo(this.list.get(rightChildIndex)) < 0)
{
maxIndex = rightChildIndex;
}
}
// 比较父节点与子节点 并交换
if (this.list.get(currentIndex)
.compareTo(this.list.get(maxIndex)) < 0)
{
E temp = this.list.get(maxIndex);
this.list.set(maxIndex, this.list.get(currentIndex));
this.list.set(currentIndex, temp);
currentIndex = maxIndex;
}
else
{
break;
}
}
return removeObject;
}
}
//测试类
package wangChaoPA实习工作练习.com.进阶篇.排序;
public class HeapSort
{
public static <E extends Comparable> void heapSort(E[] list)
{
Heap<E> heap = new Heap<E>();
for (int i = 0; i < list.length; i++)
{
heap.add(list[i]);
}
for (int i = list.length - 1; i >= 0; i--)
{
list[i] = heap.remove();
}
}
public static void main(String[] args)
{
Integer[] list =
{ 2, 3, 2, 5, 6, 1, -2, 3, 14, 12 };
heapSort(list);
for (Integer temp : list)
{
System.out.print(temp + " ");
}
}
}
原文:http://www.cnblogs.com/qingtianBKY/p/6837503.html
内容总结
以上是互联网集市为您收集整理的java 堆排序全部内容,希望文章能够帮你解决java 堆排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。