堆排序实例(Java数组实现)
程序员文章站
2024-02-25 08:54:16
堆排序:利用大根堆
数组全部入堆,再出堆从后向前插入回数组中,数组就从小到大有序了。
public class maxheap
堆排序:利用大根堆
数组全部入堆,再出堆从后向前插入回数组中,数组就从小到大有序了。
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数组实现)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持。