首页 > 代码库 > java 堆排序
java 堆排序
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 + " ");
}
}
}
java 堆排序