public class HeapSort
{
public static void main(String[] args)
{
int[] arr = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
heapSort(arr);
printHeap(arr);
}
//堆排序函数
public static void heapSort(int[] arr)
{
int len = arr.length;
buildHeap(arr, len); //首次建堆，建成一个完整的大顶堆（根节点为最大值）
for (int i = 0; i < len; i++)
{
swap(arr, 0, len - 1 - i); //将堆顶元素（通过调整堆获得的最大值）和最后一个交换（剩余未排好序部分的最后一个）
adjustHeap(arr, len - 1 - i, 0); //之后每次从堆顶开始调整，最大的值将上升到根节点
}
}
//第一次建堆的过程
public static void buildHeap(int[] arr, int maxlen)
{
int len = maxlen / 2 - 1; //完全二叉树的最后一个非叶子结点
for (int i = len; i >= 0; i--)
{
adjustHeap(arr, maxlen, i);
}
}
/**
* maxlen 此次调整堆的最大元素个数(因为堆排序过程中，后面已经调整好的就不需要调整了)
* i 表示此次调整堆的父节点
* */
public static void adjustHeap(int[] arr, int maxlen, int i)
{
int left = 2 * i + 1; //获得该父节点的左孩子
int right = 2 * i + 2; //获得该父节点的右孩子
int maxpos = i;
while (left < maxlen)
{
if (right < maxlen && arr[maxpos] < arr[right])
{
maxpos = right;
}
if (arr[maxpos] < arr[left])
{
maxpos = left;
}
if (maxpos != i)
{
swap(arr, i, maxpos);
i = maxpos; //继续向下调整，因为此次调整可能会破坏原来下面的堆
left = 2 * i + 1;
right = 2 * i + 2;
}
else
{
break;
}
}
}
//交换堆中任意两个数
public static void swap(int[] arr, int from, int to)
{
int temp = arr[from];
arr[from] = arr[to];
arr[to] = temp;
}
//打印堆中的数据
public static void printHeap(int[] arr)
{
int len = arr.length;
for (int i = 0; i < len; i++)
{
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
编辑于 2015-01-22 14:13:36
回复(0)
package Sort; import java.util.Arrays; /** * Created by ZihanCong on 16/9/9. */ public class HeapSort { public static void main(String[] args) { HeapSort hs = new HeapSort(); hs.heapSort(new int[]{1,3,5,4,7,2,9}); } public void heapSort(int[] data) { int arrayLength = data.length; for (int i = 0; i < arrayLength - 1; i++) { //构建最大堆 buildMaxHeap(data, arrayLength - i - 1); swap(data, 0, arrayLength - i - 1); System.out.println(Arrays.toString(data)); } } public void buildMaxHeap(int[] data, int lastIndex) { //从lastIndexc处的父节点开始 for (int i = (lastIndex - 1) / 2; i >=0 ; i--) { int k = i; while (k * 2 + 1 <= lastIndex) { int bigger = k * 2 + 1; //如果右节点较大,bigger引用总是指向较大的对象 if (bigger < lastIndex && data[bigger] < data[bigger + 1]) bigger++; if(data[k] < data[bigger]){ swap(data,k,bigger); //开始遍历下层的k k = bigger; } else break; } } } public void swap(int[] data, int begin, int end) { int temp = data[begin]; data[begin] = data[end]; data[end] = temp; } }
编辑于 2016-09-09 20:55:22
回复(0)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
堆排序原理
堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：
//最大堆排序 public class MaxHeapProblem { public static void buildHeap(int a[]) { int heapSize = a.length; int filter = (int) Math.floor(heapSize / 2); // i从第一个非叶子结点开始 for (int i = filter - 1; i >= 0; i--) { heapAdjust(a, i, heapSize); } } // 已知H.r[i...heapSize]中记录的关键字除H.r[i]外，均满足最大堆结构 public static void heapAdjust(int arr[], int i, int heapSize) { // 当前待调整的元素 int tmp = arr[i]; // 该元素的左孩子 int index = 2 * i + 1; while (index < heapSize) { // 如果右孩子大于左孩子,则index+1，即交换右孩子和双亲节点 if (index + 1 < heapSize && arr[index] < arr[index + 1]) { index = index + 1; } if (arr[i] < arr[index]) { // 交换孩子和双亲节点 arr[i] = arr[index]; // 重新赋初值 i = index; index = 2 * i + 1; } // 已经是最大堆 else { break; } // 把双亲值赋给孩子节点 arr[i] = tmp; } } private void heapAdjust2(int[] arr, int i, int heapSize) { int maxIndex = i; if (2 * i + 1 <= heapSize - 1 && arr[2 * i + 1] > arr[i]) maxIndex = 2 * i + 1; if (2 * i + 2 <= heapSize - 1 && arr[i * 2 + 2] > arr[maxIndex]) maxIndex = 2 * i + 2; if (maxIndex != i) { int temp = arr[maxIndex]; arr[maxIndex] = arr[i]; arr[i] = temp; heapAdjust2(arr, maxIndex, heapSize); } } public static void heapSort(int a[]) { int heapSize = a.length; for (int i = heapSize - 1; i > 0; i--) { // 交换堆顶和最后一个元素 int tmp = a[0]; a[0] = a[i]; a[i] = tmp; // 在heapSize范围内根结点的左右子树都已经是最大堆,所以只需看新交换的堆顶元素是否满足最大堆结构即可。 // 将H.r[0...i]重新调整为最大堆 heapAdjust(a, 0, i); } } public static void main(String[] args) { int arr[] = new int[] { 6, 5, 3, 1, 8, 7, 2, 4 }; buildHeap(arr); System.out.println("初始建立的最大堆是:"); for (int data : arr) System.out.print(data + " "); System.out.println(); System.out.println("堆经过筛选调整后，排序结果为:"); heapSort(arr); for (int data : arr) System.out.print(data + " "); } }