堆排序(最大堆)
import java.util.Arrays;
public class HeapSort {
//数组arr下标为0的位置不使用，待排序数字放入下标为 1 ~arr.length-1 的位置，并对这些位置上的元素排序
public static void sort(int arr[]) {
HeapSorths = new HeapSort();
hs.buildMaxHeap(arr, 1, arr.length - 1);
System.out.println("buildMaxHeap result : " + Arrays.toString(arr));
hs.adjustHeap(arr, 1, arr.length - 1);
}
//建最大堆
public void buildMaxHeap(int[] arr, int start, int end) {
for (int i = end ; i >= start; i--) {
downWithCycle(arr, i, end);
}
}
//堆调整
public void adjustHeap(int[] arr, int start, int end) {
for (int i = end; i > start; i--) {
swap(arr, start, i);
System.out.println("swap result : " + Arrays.toString(arr));
downWithCycle(arr, start, i - 1);
}
}
//下滤
public void downWithCycle(int[] arr, int start, int end) {
if (start >= end) {
return;
}
int index = start;
int leftIndex = 2 * index;
int rightIndex = 2 * index + 1;
while (leftIndex <= end) {
int biggestIndex = index;
if(arr[leftIndex]>arr[biggestIndex]){
biggestIndex = leftIndex;
}
if ((rightIndex <= end) && (arr[rightIndex] > arr[biggestIndex])) {
biggestIndex = rightIndex;
}
if(biggestIndex != index){
swap(arr,index,biggestIndex);
index = biggestIndex;
leftIndex = 2 * index;
rightIndex = 2 * index + 1;
}else{
return ;
}
}
}
//交换下标为a和b的元素
privatevoid swap(int[]arr,inta,intb) {
inttemp =arr[a];
arr[a] =arr[b];
arr[b] =temp;
}
public static void main(String[] args) {
int[] arr = { 0, 11, 2, 31, 444, 52, 16, 71, 8, 93, 10 };
System.out.println("origin : " + Arrays.toString(arr));
HeapSort.sort(arr);
System.out.println("result : " + Arrays.toString(arr));
}
}
更多相关文章
- 字体图标的引入和通过媒体查询改变导航样式
- HTML样式和常用选择器
- 字体图标的引用和自定义样式/媒体查询的使用
- 数据库的CURD操作、PDO本质与原理的学习
- CSS之伪类选择器和简单盒子简单案例
- 伪类选择器与盒模型常用属性
- 伪类选择器-结构伪类、根据位置选择匹配
- 7.4——常用标签与应用场景之表格与单元格
- css伪类选择器和盒模型