Java数组实现堆排序的示例分析

这篇文章主要为大家展示了“Java数组实现堆排序的示例分析”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“Java数组实现堆排序的示例分析”这篇文章吧。

数组全部入堆，再出堆从后向前插入回数组中，数组就从小到大有序了。

public class MaxHeap<T extends Comparable<? super T>> {  private T[] data;  private int size;  private int capacity;    public MaxHeap(int capacity) {   this.data = (T[]) new Comparable[capacity + 1];   size = 0;   this.capacity = capacity;  }    public int size() {   return this.size;  }    public boolean isEmpty() {   return size == 0;  }    public int getCapacity() {   return this.capacity;  }    /**   * @return 查看最大根(只看不删, 与popMax对比)   */  public T seekMax() {   return data[1];  }    public void swap(int i, int j) {   if (i != j) {    T temp = data[i];    data[i] = data[j];    data[j] = temp;   }  }    public void insert(T item) {   size++;   data[size] = item;   shiftUp(size);  }    /**   * @return 弹出最大根(弹出意味着删除, 与seekMax对比)   */  public T popMax() {   swap(1, size--);   shiftDown(1);   return data[size + 1];  }    /**   * @param child 孩子节点下角标是child，父节点下角表是child/2   */  public void shiftUp(int child) {   while (child > 1 && data[child].compareTo(data[child / 2]) > 0) {    swap(child, child / 2);    child = child / 2;   }  }    /**   * @param a data数组中某个元素的下角标   * @param b data数组中某个元素的下角标   * @return 哪个元素大就返回哪个的下角标   */  private int max(int a, int b) {   if (data[a].compareTo(data[b]) < 0) {//如果data[b]大    return b;//返回b   } else {//如果data[a]大    return a;//返回a   }  }    /**   * @param a data数组中某个元素的下角标   * @param b data数组中某个元素的下角标   * @param c data数组中某个元素的下角标   * @return 哪个元素大就返回哪个的下角标   */  private int max(int a, int b, int c) {   int biggest = max(a, b);   biggest = max(biggest, c);   return biggest;  }      /**   * @param father 父节点下角标是father,左右两个孩子节点的下角表分别是：father*2 和 father*2+1   */  public void shiftDown(int father) {   while (true) {    int lchild = father * 2;//左孩子    int rchild = father * 2 + 1;//右孩子    int newFather = father;//newFather即将更新，父、左、右三个结点谁大，newFather就是谁的下角标      if (lchild > size) {//如果该father结点既没有左孩子，也没有右孩子     return;    } else if (rchild > size) {//如果该father结点只有左孩子，没有右孩子     newFather = max(father, lchild);    } else {//如果该father结点既有左孩子，又有右孩子     newFather = max(father, lchild, rchild);    }      if (newFather == father) {//说明father比两个子结点都要大，表名已经是大根堆，不用继续调整了     return;    } else {//否则，还需要继续调整堆，直到满足大根堆条件为止     swap(father, newFather);//值进行交换     father = newFather;//更新father的值，相当于继续调整shiftDown(newFather)    }   }  }    public static <T extends Comparable<? super T>> void sort(T[] arr) {   int len = arr.length;   //入堆   MaxHeap<T> maxHeap = new MaxHeap<T>(len);   for (int i = 0; i < len; i++) {    maxHeap.insert(arr[i]);   }   //出堆   for (int i = len - 1; i >= 0; i--) {    arr[i] = maxHeap.popMax();   }  }    public static void printArr(Object[] arr) {   for (Object o : arr) {    System.out.print(o);    System.out.print("\t");   }   System.out.println();  }    public static void main(String args[]) {   Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};   printArr(arr);//3 5 1 7 2 9 8 0 4 6   sort(arr);   printArr(arr);//0 1 2 3 4 5 6 7 8 9  } }

堆排序：对数组进行构造堆(最大堆)

public class MaxHeap<T extends Comparable<? super T>> {  private T[] data;  private int size;  private int capacity;    public MaxHeap(int capacity) {   this.capacity = capacity;   this.size = 0;   this.data = (T[]) new Comparable[capacity + 1];  }    public MaxHeap(T[] arr) {//heapify,数组建堆   capacity = arr.length;   data = (T[]) new Comparable[capacity + 1];   System.arraycopy(arr, 0, data, 1, arr.length);   size = arr.length;   for (int i = size / 2; i >= 1; i--) {    shiftDown(i);   }  }    public int size() {   return this.size;  }    public int getCapacity() {   return this.capacity;  }    public boolean isEmpty() {   return size == 0;  }    public T seekMax() {   return data[1];  }    public void swap(int i, int j) {   if (i != j) {    T temp = data[i];    data[i] = data[j];    data[j] = temp;   }  }    public void insert(T item) {   size++;   data[size] = item;   shiftUp(size);  }    public T popMax() {   swap(1, size--);   shiftDown(1);   return data[size + 1];  }    public void shiftUp(int child) {   while (child > 1 && data[child].compareTo(data[child / 2]) > 0) {    swap(child, child / 2);    child /= 2;   }  }    /**   * @param a data数组中某个元素的下角标   * @param b data数组中某个元素的下角标   * @return 哪个元素大就返回哪个的下角标   */  private int max(int a, int b) {   if (data[a].compareTo(data[b]) < 0) {//如果data[b]大    return b;//返回b   } else {//如果data[a]大    return a;//返回a   }  }    /**   * @param a data数组中某个元素的下角标   * @param b data数组中某个元素的下角标   * @param c data数组中某个元素的下角标   * @return 哪个元素大就返回哪个的下角标   */  private int max(int a, int b, int c) {   int biggest = max(a, b);   biggest = max(biggest, c);   return biggest;  }    public void shiftDown(int father) {   while (true) {    int lchild = father * 2;    int rchild = father * 2 + 1;    int newFather = father;//这里赋不赋值无所谓，如果把下面这个return改成break,那就必须赋值了      if (lchild > size) {//如果没有左、右孩子     return;    } else if (rchild > size) {//如果没有右孩子     newFather = max(father, lchild);    } else {//如果有左、右孩子     newFather = max(father, lchild, rchild);    }      if (newFather == father) {//如果原父结点就是三者最大，则不用继续整理堆了     return;    } else {//父节点不是最大，则把大的孩子交换上来，然后继续往下堆调整，直到满足大根堆为止     swap(newFather, father);     father = newFather;//相当于继续shiftDown(newFather)。假如newFather原来是father的左孩子，那就相当于shiftDown(2*father)    }   }  }    public static <T extends Comparable<? super T>> void sort(T[] arr) {   int len = arr.length;   MaxHeap<T> maxHeap = new MaxHeap<>(arr);   for (int i = len - 1; i >= 0; i--) {    arr[i] = maxHeap.popMax();   }  }    public static void printArr(Object[] arr) {   for (Object o : arr) {    System.out.print(o);    System.out.print("\t");   }   System.out.println();  }    public static void main(String args[]) {   Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};   printArr(arr);//3 5 1 7 2 9 8 0 4 6   sort(arr);   printArr(arr);//0 1 2 3 4 5 6 7 8 9  } }

以上是“Java数组实现堆排序的示例分析”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！