package sunfa.sort;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
public class HeapSort {
public static void main(String[] args) {
int n = 20;
Random ran = new Random();
int[] arr = new int[n];
Heap<Integer> heap = new Heap<Integer>(n, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int i = 0; i < n; i++) {
int o = ran.nextInt(100);
arr[i] = o;
heap.add(o);
}
System.out.println(Arrays.toString(arr));
// System.out.println(Arrays.toString(heap.getHeap()));
// System.out.println(heap.getHeap()[heap.count()]);
// heap.swap(heap.getHeap(), 1, heap.count());
// System.out.println("swap:" + Arrays.toString(heap.getHeap()));
// heap.heapify(1, heap.count());
System.out.println(Arrays.toString(heap.getHeap()));
System.out.println("堆排序:");
/**
* 堆排序的思想是:<br>
* 以最大堆为例<br>
* ①把堆头和堆尾2个数交换<br>
* ②将堆头到堆尾-1这个范围内的数进行堆化<br>
* 重复上面2个步骤直到②步中要被堆化的数据长度为1<br>
*
* 算法分析<br>
* 堆[排序的时间,主要由建立初始]堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。<br>
堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。<br>
由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。<br>
堆排序是就地排序,辅助空间为O(1),<br>
它是不稳定的排序方法。<br>
*/
int last = heap.count();
while (last - 1 > 1) {
heap.swap(heap.getHeap(), 1, last--);
if (last - 1 > 1) {
heap.heapify(1, last);
}
System.out.println("堆化后:" + ",last:" + last
+ Arrays.toString(heap.getHeap()));
}
}
}
class Heap<E> {
private Object[] heap;
private int size;
Comparator<E> comp;
public Object[] getHeap() {
return heap;
}
public int count() {
return size;
}
public Heap(int n, Comparator<E> c) {
if (n < 0)
throw new IllegalArgumentException("n:" + n);
comp = c;
heap = new Object[n];
}
public void add(E e) {
if (size + 1 == heap.length)
heap = Arrays.copyOf(heap, heap.length << 1);
heap[++size] = e;
fixUp(size);
}
private void fixUp(int k) {
while (k > 1) {
int p = k >>> 1;
if (compare((E) heap[k], (E) heap[p]) > 0)
break;
swap((E[]) heap, k, p);
k = p;
}
}
public void swap(Object[] e, int a, int b) {
Object t = e[a];
e[a] = e[b];
e[b] = t;
}
private int compare(E t1, E t2) {
return comp == null ? (((Comparable<E>) t1).compareTo(t2)) : (comp
.compare(t1, t2));
}
private void fixDown(int k) {
int j;
while ((j = k << 1) <= size) {
if (j < size && compare((E) heap[j], (E) heap[j + 1]) > 0)
j++;
if (compare((E) heap[k], (E) heap[j + 1]) < 0)
break;
swap((E[]) heap, k, j);
k = j;
}
}
/**
* 对指定范围内的数据进行堆化
* @param a 开始索引
* @param b 结束索引
*/
public void heapify(int a, int b) {
for (int i = b; i >= a; i--) {
fixUp(i);
}
}
}
分享到:
相关推荐
本程序实现各种排序算法并分析与比较 直接插入排序, SHELL排序,冒泡排序,快速排序,简单选择排序,堆排序,归并排序
简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
1、常见排序算法实现(1-6选择几个算法练习) 1)问题描述:输入一组... (5)实现堆排序算法。 (6)合并排序算法。 2) 实现提示: 数据输入后,每选择一种算法,把数据拷贝后再排序,保证原始数据不破坏.
解决算法中求若干个数的前N位,堆排序是最佳选择。
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
排序算法: 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序
用C++语言实现的几个常见算法,里面有注解,方便大家理解,简单易学,都可以正常编译运行。
堆排序的一个简单算法里面涉及到初始建堆,从最后一个非终端结点至根结点,重复执行移走堆顶及重建堆的操作
算发在VC环境下试运行过了,可以运行,直接考进去就行了,为了简单,里面用的数组类型,修改一下就可以了
简单实现快速排序和堆排序,是标准的算法,时间达到nlog2n
使用简单数组实现下面各种排序算法的功能,并进行比较, 排序算法如下: a) 插入排序; b) 希尔排序; c) 冒泡排序; d) 快速排序; e) 简单选择排序; f) 堆排序; g) 归并排序; h) 基数排序(选作); i) 其他; ...
第一部分是简单排序算法,后面你将看到他们的共同点是算法复杂度为O(N*N)(因为没有 使用word,所以无法打出上标和下标)。 第二部分是高级排序算法,复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种 ...
1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组不同的输入数据作比较;比较...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
随机产生10000个浮点数,保存到a.txt文件中,再读取到内存中并分别用简单选择排序、冒泡排序、快速排序、希尔排序、归并排序、堆排序算法进行排序,显示排序过的数列的第1、10、100、1000、10000的具体数字和每个...
排序算法总结常见排序算法如下:直接插入排序希尔排序简单选择排序堆排序冒泡排序快速排序归并排序技术排序它们都属于内部排序,也就是只考虑数据量较小仅需要使用内部的排
(1) 对6种常用内部排序算法进行比较:冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序 (2) 待排序的表长不小于100,其中数据要用伪随机数产生,至少用5组不同的输入数据做比较 (3) 比较...