首页 / 算法 / 排序算法--选择排序--堆排序
排序算法--选择排序--堆排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法--选择排序--堆排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2440字,纯文字阅读大概需要4分钟。
内容图文
![排序算法--选择排序--堆排序](/upload/InfoBanner/zyjiaocheng/799/c1381b43b29041b19fd13acb1b7c5046.jpg)
https://blog.csdn.net/u010452388/article/details/81283998
基本思想:
1.首先将待排序的数组构造成一个大根堆,此时,整个数组的最大值就是堆结构的顶端
2.将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1
3.将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,如此反复执行,便能得到有序数组
import org.junit.Test;
import java.util.Random;
/**
* Author:zxh
* MIS:
* Date: 2019/2/21 19:53
* Email:
* Desc: 大顶堆 并不仅仅要求0位置的值最大,而且要求每个父节点都大于左孩子,右孩子
*/
public class SortHeap {
private final static int arrLength = 10;
@Test
public void test() {
//int[] a = {6, 0, 8, 19, 20, 31, 59, 71, 79, 95,};
/*初始化数组*/
int[] a = new int[arrLength];
Random random = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = random.nextInt(100);
}
System.out.print("原始数组:");
print(a);
/*构建大顶堆*/
generateMaxTopHeap(a);
System.out.print("初始化构建大顶堆完毕后:");
print(a);
/*堆顶与最后一位元素交换*/
swap(a, a.length - 1, 0);
/*重新构建大顶堆**/
rebulidMaxTopHeap(a);
print(a);
}
private void rebulidMaxTopHeap(int[] a) {
int parentIndex;
//父、左、右中的最大的index
int maxIndex;
//最后一个节点
int lastIndex = a.length - 2;
while (lastIndex >= 1) {
parentIndex = 0;
int leftIndex = 2 * parentIndex + 1;
int rightIndex = 2 * parentIndex + 2;
while (leftIndex <= lastIndex) {
/*rightIndex > lastIndex时,右孩子已经是排好序的,不能重新把它卷进来,只需比较左孩子和父节点*/
if (a[leftIndex] > a[rightIndex] || rightIndex > lastIndex) {
maxIndex = leftIndex;
} else {
maxIndex = rightIndex;
}
if (a[parentIndex] > a[maxIndex]) {
break;
}
swap(a, maxIndex, parentIndex);
parentIndex = maxIndex;
leftIndex = 2 * parentIndex + 1;
rightIndex = 2 * parentIndex + 2;
}
swap(a, 0, lastIndex);
lastIndex--;
System.out.print("中间选择排序过程:");
print(a);
}
}
private void generateMaxTopHeap(int[] a) {
int childIndex;
int parentIndex;
for (int index = 1; index < a.length; index++) {
//父节点 parent = (child-1)/2
childIndex = index;
parentIndex = (childIndex - 1) / 2;
while (childIndex > 0) {
if (a[childIndex] > a[parentIndex]) {
swap(a, parentIndex, childIndex);
}
childIndex = parentIndex;
parentIndex = (parentIndex - 1) / 2;
}
}
}
private void swap(int[] a, int aIndex, int bIndex) {
int temp = a[bIndex];
a[bIndex] = a[aIndex];
a[aIndex] = temp;
}
public void print(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + ",");
}
System.out.println();
}
public static void main(String[] args) {
System.out.println((0 - 1) / 2);// 输出0 ********
}
}
内容总结
以上是互联网集市为您收集整理的排序算法--选择排序--堆排序全部内容,希望文章能够帮你解决排序算法--选择排序--堆排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。