查看: 366|回复: 0

[Java学习] 堆排序实例(Java数组实现)

发表于 2018-1-5 08:00:00

堆排序:利用大根堆

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

  1. public class MaxHeap<T extends Comparable<? super T>> {
  2. private T[] data;
  3. private int size;
  4. private int capacity;
  5. public MaxHeap(int capacity) {
  6. this.data = (T[]) new Comparable[capacity + 1];
  7. size = 0;
  8. this.capacity = capacity;
  9. }
  10. public int size() {
  11. return this.size;
  12. }
  13. public boolean isEmpty() {
  14. return size == 0;
  15. }
  16. public int getCapacity() {
  17. return this.capacity;
  18. }
  19. /**
  20. * @return 查看最大根(只看不删, 与popMax对比)
  21. */
  22. public T seekMax() {
  23. return data[1];
  24. }
  25. public void swap(int i, int j) {
  26. if (i != j) {
  27. T temp = data[i];
  28. data[i] = data[j];
  29. data[j] = temp;
  30. }
  31. }
  32. public void insert(T item) {
  33. size++;
  34. data[size] = item;
  35. shiftUp(size);
  36. }
  37. /**
  38. * @return 弹出最大根(弹出意味着删除, 与seekMax对比)
  39. */
  40. public T popMax() {
  41. swap(1, size--);
  42. shiftDown(1);
  43. return data[size + 1];
  44. }
  45. /**
  46. * @param child 孩子节点下角标是child,父节点下角表是child/2
  47. */
  48. public void shiftUp(int child) {
  49. while (child > 1 && data[child].compareTo(data[child / 2]) > 0) {
  50. swap(child, child / 2);
  51. child = child / 2;
  52. }
  53. }
  54. /**
  55. * @param a data数组中某个元素的下角标
  56. * @param b data数组中某个元素的下角标
  57. * @return 哪个元素大就返回哪个的下角标
  58. */
  59. private int max(int a, int b) {
  60. if (data[a].compareTo(data[b]) < 0) {//如果data[b]大
  61. return b;//返回b
  62. } else {//如果data[a]大
  63. return a;//返回a
  64. }
  65. }
  66. /**
  67. * @param a data数组中某个元素的下角标
  68. * @param b data数组中某个元素的下角标
  69. * @param c data数组中某个元素的下角标
  70. * @return 哪个元素大就返回哪个的下角标
  71. */
  72. private int max(int a, int b, int c) {
  73. int biggest = max(a, b);
  74. biggest = max(biggest, c);
  75. return biggest;
  76. }
  77. /**
  78. * @param father 父节点下角标是father,左右两个孩子节点的下角表分别是:father*2 和 father*2+1
  79. */
  80. public void shiftDown(int father) {
  81. while (true) {
  82. int lchild = father * 2;//左孩子
  83. int rchild = father * 2 + 1;//右孩子
  84. int newFather = father;//newFather即将更新,父、左、右三个结点谁大,newFather就是谁的下角标
  85. if (lchild > size) {//如果该father结点既没有左孩子,也没有右孩子
  86. return;
  87. } else if (rchild > size) {//如果该father结点只有左孩子,没有右孩子
  88. newFather = max(father, lchild);
  89. } else {//如果该father结点既有左孩子,又有右孩子
  90. newFather = max(father, lchild, rchild);
  91. }
  92. if (newFather == father) {//说明father比两个子结点都要大,表名已经是大根堆,不用继续调整了
  93. return;
  94. } else {//否则,还需要继续调整堆,直到满足大根堆条件为止
  95. swap(father, newFather);//值进行交换
  96. father = newFather;//更新father的值,相当于继续调整shiftDown(newFather)
  97. }
  98. }
  99. }
  100. public static <T extends Comparable<? super T>> void sort(T[] arr) {
  101. int len = arr.length;
  102. //入堆
  103. MaxHeap<T> maxHeap = new MaxHeap<T>(len);
  104. for (int i = 0; i < len; i++) {
  105. maxHeap.insert(arr[i]);
  106. }
  107. //出堆
  108. for (int i = len - 1; i >= 0; i--) {
  109. arr[i] = maxHeap.popMax();
  110. }
  111. }
  112. public static void printArr(Object[] arr) {
  113. for (Object o : arr) {
  114. System.out.print(o);
  115. System.out.print("\t");
  116. }
  117. System.out.println();
  118. }
  119. public static void main(String args[]) {
  120. Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
  121. printArr(arr);//3 5 1 7 2 9 8 0 4 6
  122. sort(arr);
  123. printArr(arr);//0 1 2 3 4 5 6 7 8 9
  124. }
  125. }
复制代码

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

  1. public class MaxHeap<T extends Comparable<? super T>> {
  2. private T[] data;
  3. private int size;
  4. private int capacity;
  5. public MaxHeap(int capacity) {
  6. this.capacity = capacity;
  7. this.size = 0;
  8. this.data = (T[]) new Comparable[capacity + 1];
  9. }
  10. public MaxHeap(T[] arr) {//heapify,数组建堆
  11. capacity = arr.length;
  12. data = (T[]) new Comparable[capacity + 1];
  13. System.arraycopy(arr, 0, data, 1, arr.length);
  14. size = arr.length;
  15. for (int i = size / 2; i >= 1; i--) {
  16. shiftDown(i);
  17. }
  18. }
  19. public int size() {
  20. return this.size;
  21. }
  22. public int getCapacity() {
  23. return this.capacity;
  24. }
  25. public boolean isEmpty() {
  26. return size == 0;
  27. }
  28. public T seekMax() {
  29. return data[1];
  30. }
  31. public void swap(int i, int j) {
  32. if (i != j) {
  33. T temp = data[i];
  34. data[i] = data[j];
  35. data[j] = temp;
  36. }
  37. }
  38. public void insert(T item) {
  39. size++;
  40. data[size] = item;
  41. shiftUp(size);
  42. }
  43. public T popMax() {
  44. swap(1, size--);
  45. shiftDown(1);
  46. return data[size + 1];
  47. }
  48. public void shiftUp(int child) {
  49. while (child > 1 && data[child].compareTo(data[child / 2]) > 0) {
  50. swap(child, child / 2);
  51. child /= 2;
  52. }
  53. }
  54. /**
  55. * @param a data数组中某个元素的下角标
  56. * @param b data数组中某个元素的下角标
  57. * @return 哪个元素大就返回哪个的下角标
  58. */
  59. private int max(int a, int b) {
  60. if (data[a].compareTo(data[b]) < 0) {//如果data[b]大
  61. return b;//返回b
  62. } else {//如果data[a]大
  63. return a;//返回a
  64. }
  65. }
  66. /**
  67. * @param a data数组中某个元素的下角标
  68. * @param b data数组中某个元素的下角标
  69. * @param c data数组中某个元素的下角标
  70. * @return 哪个元素大就返回哪个的下角标
  71. */
  72. private int max(int a, int b, int c) {
  73. int biggest = max(a, b);
  74. biggest = max(biggest, c);
  75. return biggest;
  76. }
  77. public void shiftDown(int father) {
  78. while (true) {
  79. int lchild = father * 2;
  80. int rchild = father * 2 + 1;
  81. int newFather = father;//这里赋不赋值无所谓,如果把下面这个return改成break,那就必须赋值了
  82. if (lchild > size) {//如果没有左、右孩子
  83. return;
  84. } else if (rchild > size) {//如果没有右孩子
  85. newFather = max(father, lchild);
  86. } else {//如果有左、右孩子
  87. newFather = max(father, lchild, rchild);
  88. }
  89. if (newFather == father) {//如果原父结点就是三者最大,则不用继续整理堆了
  90. return;
  91. } else {//父节点不是最大,则把大的孩子交换上来,然后继续往下堆调整,直到满足大根堆为止
  92. swap(newFather, father);
  93. father = newFather;//相当于继续shiftDown(newFather)。假如newFather原来是father的左孩子,那就相当于shiftDown(2*father)
  94. }
  95. }
  96. }
  97. public static <T extends Comparable<? super T>> void sort(T[] arr) {
  98. int len = arr.length;
  99. MaxHeap<T> maxHeap = new MaxHeap<>(arr);
  100. for (int i = len - 1; i >= 0; i--) {
  101. arr[i] = maxHeap.popMax();
  102. }
  103. }
  104. public static void printArr(Object[] arr) {
  105. for (Object o : arr) {
  106. System.out.print(o);
  107. System.out.print("\t");
  108. }
  109. System.out.println();
  110. }
  111. public static void main(String args[]) {
  112. Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
  113. printArr(arr);//3 5 1 7 2 9 8 0 4 6
  114. sort(arr);
  115. printArr(arr);//0 1 2 3 4 5 6 7 8 9
  116. }
  117. }
复制代码

以上这篇堆排序实例(Java数组实现)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持程序员之家。



回复

使用道具 举报