堆排序和其他排序算法时间复杂度比较截图
堆排序执行（完整代码）
MaxHeap.java（最大堆数据结构）
public class MaxHeap<E extends Comparable<E>> {
private Array<E> data;
public MaxHeap(int capacity){
data = new Array<>(capacity);
}
public MaxHeap(){
data = new Array<>();
}
// 返回堆中的元素个数
public int size(){
return data.getSize();
}
// 返回一个布尔值，表示堆中是否为空
public boolean isEmpty(){
return data.isEmpty();
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
private int parent(int index){
if(index == 0)
throw new IllegalArgumentException("index-0 doesn't have parent.");
return (index - 1) / 2;
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
private int leftChild(int index){
return index * 2 + 1;
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素右孩子节点的索引
private int rightchild(int index){
return index * 2 + 2;
}
// 向堆中添加元素
public void add(E e){
data.addLast(e);
siftUp(data.getSize()- 1);
}
private void siftUp(int k){
while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
data.swap(k , parent(k));
k = parent(k);
}
}
// 看堆中的最大元素
public E findMax(){
if(data.getSize()==0)
throw new IllegalArgumentException("can not findMax when heap is empty!");
return data.get(0);
}
// 取出堆中最大元素
public E extractMax(){
E ret = findMax();
data.swap(0, data.getSize()-1);
data.removeLast();
siftDown(0);
return ret;
}
private void siftDown(int k ){
while(leftChild(k) < data.getSize() ){
int j = leftChild(k);
if(j + 1 < data.getSize() && data.get(j+1).compareTo(data.get(j))>0){
j = rightchild(k);
}
//data[j] 是左右孩子中最大值
if(data.get(k).compareTo(data.get(j)) >= 0)
break;
data.swap(k,j);
k = j;
}
}
}
Array.java(堆使用的自定义动态数组)
public class Array<E> {
private E[] data;
private int size; //大小
// 构造函数 转入数组的容量capacity构造Array
public Array(int capacity){
data =(E[])new Object[capacity];
size = 0 ;
}
// 无参的构造函数，默认数组的容量capacity = 10
public Array(){
this(10); //调用有参构造函数传入10设定初始大小
}
// 获取数组中元素个数
public int getSize(){
return size;
}
// 获取数组的容量
public int getCapacity(){
return data.length;
}
//返回数组是否为空
public boolean isEmpty(){
return size == 0;
}
// 向所有元素后添加一个新元素
public void addLast(E e){
// if(size == data.length) {
// throw new IllegalArgumentException("AddLast failed. Array is full.");
// }
// data[size] = e;
// size ++;
add(size, e);
}
// 在所有元素前添加一个新元素
public void addFirst(E e){
add(0, e);
}
// 在第index个位置插入一个新元素e
public void add(int index, E e){
if(index < 0 || index > size ){
throw new IllegalArgumentException("Add failed. Require index >=0 and index <= size.");
}
if(size == data.length) {
resize(2 * data.length);
}
for(int i = size - 1 ; i >= index ; i --){
data[i + 1]=data[i];
}
data[index] = e;
size ++;
}
// 获取index索引位置的元素
public E get(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Index is illegal.");
return data[index];
}
// 修改index索引位置的元素为e
public void set(int index, E e){
if(index < 0 || index >= size)
throw new IllegalArgumentException("set failed. Index is illegal.");
data[index] = e;
}
// 查找数组中是否有元素e
public boolean contains(E e){
for(int i = 0 ; i < size ; i++)
{
if(data[i].equals(e))
return true;
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find(E e){
for(int i = 0 ; i < size ; i++)
{
if(data[i].equals(e))
return i;
}
return -1;
}
// 从数组中删除index位置的元素，返回删除的元素
public E remove(int index){
if(index < 0 || index >= size)
{
throw new IllegalArgumentException("Remove failed. Index is illegal.");
}
E ret = data[index];
for(int i = index + 1 ; i < size ; i ++)
{
data[i-1] = data[i];
}
size --;
data[size] = null; //让他自动回收 非必须写 loitering objects ！= memory leak
if(size == data.length / 4 && data.length / 2 != 0)
resize(data.length / 2);
return ret;
}
// 从数组中删除第一个元素，返回删除的元素
public E removeFirst(){
return remove(0);
}
// 从数组中删除最后一个元素，返回删除的元素
public E removeLast(){
return remove(size-1);
}
// 从数组中删除元素e
public void removeElement(E e){
int index = find(e);
if(index != -1)
remove(index);
}
public void swap(int i , int j){
if(i < 0 || i >= size || j < 0 || j >= size)
throw new IllegalArgumentException("Index is illegal.");
E t = data[i];
data[i] = data[j];
data[j] = t;
}
//system.out.print()所输出的类型toString覆盖
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d, capacity = %d \n", size, data.length));
res.append('[');
for(int i = 0 ; i < size ; i ++){
res.append(data[i]);
if(i != size - 1)
res.append(", ");
}
res.append(']');
return res.toString();
}
private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[i];
data = newData;
}
}
SortingHelper.java（辅助进行算法时间输出的）
public class SortingHelper {
private SortingHelper(){} //私有类
public static <E extends Comparable<E>> boolean isSorted(E[] arr){
for(int i = 1; i< arr.length; i++)
if (arr[i - 1].compareTo(arr[i]) > 0)
return false;
return true;
}
public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
long startTime = System.nanoTime();
if(sortname.equals("SelectionSort")) {
SelectionSort.sort(arr);
} else if(sortname.equals("InsertionSort"))
InsertionSort.sort(arr);
else if(sortname.equals("InsertionSort2"))
InsertionSort.sort2(arr);
else if(sortname.equals("MergeSort"))
MergeSort.sort(arr);
else if(sortname.equals("MergeSort2"))
MergeSort.sort2(arr);
else if(sortname.equals("MergeSort3"))
MergeSort.sort3(arr);
else if(sortname.equals("MergeSort4"))
MergeSort.sort4(arr);
else if(sortname.equals("MergeSortBU"))
MergeSort.sortBU(arr);
else if(sortname.equals("QuickSort"))
QuickSort.sort(arr);
else if(sortname.equals("QuickSort2"))
QuickSort.sort2ways(arr);
else if(sortname.equals("QuickSort3"))
QuickSort.sort3ways(arr);
else if(sortname.equals("HeapSort"))
HeapSort.sort(arr);
long endTime = System.nanoTime();
double time = (endTime - startTime) / 1000000000.0; //纳米要/9个零
if(!SortingHelper.isSorted(arr))
throw new RuntimeException(sortname + "failed");
System.out.println(String.format("%s , n = %d : %f s ", sortname, arr.length, time));
}
}
ArrayGenerator.java（生成随机的一组数组或有序的一组数组）
import java.util.Random;
public class ArrayGenerator {
private ArrayGenerator(){}
public static Integer[] generateOrderedArray(int n){
Integer[] arr = new Integer[n];
for(int i = 0; i < n ; i++)
arr[i] = i;
return arr;
}
// 生成一个长度为 n 的随机数组， 每个数字的范围是[ 0 , bound)
public static Integer[] generateRandomArray(int n, int bound){
Integer[] arr = new Integer[n];
Random rnd = new Random();
for(int i = 0 ; i < n; i++)
arr[i] = rnd.nextInt(bound); //从0到bound前闭后开
return arr;
}
}
HeapSort.java(简单的堆排序)
因为是最大堆，所以进行了逆置输出
import java.util.Arrays;
public class HeapSort {
private HeapSort(){}
public static <E extends Comparable<E>> void sort(E[] data){
MaxHeap<E> maxHeap = new MaxHeap<>();
for(E e: data)
maxHeap.add(e);
for(int i = data.length - 1 ; i >= 0 ; i --)
data[i] = maxHeap.extractMax();
}
public static void main(String[] args) {
int n = 1000000;
Integer[] arr = ArrayGenerator.generateRandomArray(n , n);
Integer[] arr2 = Arrays.copyOf(arr, arr.length);
Integer[] arr3 = Arrays.copyOf(arr, arr.length);
Integer[] arr4 = Arrays.copyOf(arr, arr.length);
Integer[] arr5 = Arrays.copyOf(arr, arr.length);
sort(arr5);
for(int i = 0 ; i < n ; i ++){
System.out.println(arr5[i]);
}
SortingHelper.sortTest("MergeSort", arr);
SortingHelper.sortTest("QuickSort2", arr2);
SortingHelper.sortTest("QuickSort3", arr3);
SortingHelper.sortTest("HeapSort", arr4);
}
}
发表于 2021-6-30 15:12
