【Java】数据结构-堆排序（完整代码）

孤樱懶契 发表于 2021-6-30 15:12

本帖最后由孤樱懶契于 2021-10-23 22:40 编辑

# 堆排序和其他排序算法时间复杂度比较截图

!(https://gitee.com/gylq/cloudimages/raw/master/img/image-20210630150821902.png)

# 堆排序执行（完整代码）

## MaxHeap.java（最大堆数据结构）

```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 intparent(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 是左右孩子中最大值

         if(data.get(k).compareTo(data.get(j)) >= 0)
            break;
         data.swap(k,j);
         k = j;
   }
}
}

```

## Array.java(堆使用的自定义动态数组)

```java
public class Array<E> {

private E[] data;
private int size;//大小

// 构造函数转入数组的容量capacity构造Array
public Array(int capacity){
   data =(E[])new Object;
   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 = 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=data;
   }
   data = e;
   size ++;
}

// 获取index索引位置的元素
public E get(int index){
   if(index < 0 || index >= size)
         throw new IllegalArgumentException("Get failed. Index is illegal.");
   return data;
}

// 修改index索引位置的元素为e
public void set(int index, E e){
   if(index < 0 || index >= size)
         throw new IllegalArgumentException("set failed. Index is illegal.");
   data = e;

}

// 查找数组中是否有元素e
public boolean contains(E e){
   for(int i = 0 ; i < size ; i++)
   {
         if(data.equals(e))
            return true;
   }
   return false;
}

// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find(E e){
   for(int i = 0 ; i < size ; i++)
   {
         if(data.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;
   for(int i = index + 1 ; i < size ; i ++)
   {
         data = data;
   }
   size --;
   data = 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;
   data = data;
   data = 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);
         if(i != size - 1)
            res.append(", ");
   }
   res.append(']');
   return res.toString();
}

private void resize(int newCapacity){
   E[] newData = (E[])new Object;
   for(int i = 0 ; i < size ; i ++)
         newData = data;
   data = newData;
}
}

```

## SortingHelper.java（辅助进行算法时间输出的）

```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.compareTo(arr) > 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（生成随机的一组数组或有序的一组数组）

```java
import java.util.Random;

public class ArrayGenerator {

private ArrayGenerator(){}

public static Integer[] generateOrderedArray(int n){

   Integer[] arr = new Integer;
   for(int i = 0; i < n ; i++)
      arr = i;
   return arr;
}

// 生成一个长度为 n 的随机数组，每个数字的范围是[ 0 , bound)
public static Integer[] generateRandomArray(int n, int bound){

   Integer[] arr = new Integer;
   Random rnd = new Random();
   for(int i = 0 ; i < n; i++)
         arr = rnd.nextInt(bound); //从0到bound前闭后开
   return arr;
}
}

```

## HeapSort.java(简单的堆排序)

> 因为是最大堆，所以进行了逆置输出

```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 = 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);
   }

   SortingHelper.sortTest("MergeSort", arr);
   SortingHelper.sortTest("QuickSort2", arr2);
   SortingHelper.sortTest("QuickSort3", arr3);
   SortingHelper.sortTest("HeapSort", arr4);
}
}

```

xfmiao 发表于 2021-6-30 16:27

楼主的编辑器用的哪个的，不像pycharm

lvbuqing 发表于 2021-6-30 17:55

xfmiao 发表于 2021-6-30 16:27
楼主的编辑器用的哪个的，不像pycharm

IntelliJ IDEA

与影立黄昏 发表于 2021-6-30 20:12

idea哪个版本啊我安装一次太卡了

页: [1]

吾爱破解 - 52pojie.cn's Archiver

【Java】数据结构-堆排序（完整代码）