Java數(shù)組實現(xiàn)堆排序的示例分析
這篇文章主要為大家展示了“Java數(shù)組實現(xiàn)堆排序的示例分析”，內(nèi)容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“Java數(shù)組實現(xiàn)堆排序的示例分析”這篇文章吧。
創(chuàng)新互聯(lián)建站專業(yè)成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計，集網(wǎng)站策劃、網(wǎng)站設(shè)計、網(wǎng)站制作于一體，網(wǎng)站seo、網(wǎng)站優(yōu)化、網(wǎng)站營銷、軟文發(fā)稿等專業(yè)人才根據(jù)搜索規(guī)律編程設(shè)計，讓網(wǎng)站在運行后，在搜索中有好的表現(xiàn)，專業(yè)設(shè)計制作為您帶來效益的網(wǎng)站！讓網(wǎng)站建設(shè)為您創(chuàng)造效益。
數(shù)組全部入堆，再出堆從后向前插入回數(shù)組中，數(shù)組就從小到大有序了。
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 孩子節(jié)點下角標是child，父節(jié)點下角表是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數(shù)組中某個元素的下角標
* @param b data數(shù)組中某個元素的下角標
* @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數(shù)組中某個元素的下角標
* @param b data數(shù)組中某個元素的下角標
* @param c data數(shù)組中某個元素的下角標
* @return 哪個元素大就返回哪個的下角標
*/
private int max(int a, int b, int c) {
int biggest = max(a, b);
biggest = max(biggest, c);
return biggest;
}
/**
* @param father 父節(jié)點下角標是father,左右兩個孩子節(jié)點的下角表分別是：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即將更新，父、左、右三個結(jié)點誰大，newFather就是誰的下角標
if (lchild > size) {//如果該father結(jié)點既沒有左孩子，也沒有右孩子
return;
} else if (rchild > size) {//如果該father結(jié)點只有左孩子，沒有右孩子
newFather = max(father, lchild);
} else {//如果該father結(jié)點既有左孩子，又有右孩子
newFather = max(father, lchild, rchild);
}
if (newFather == father) {//說明father比兩個子結(jié)點都要大，表名已經(jīng)是大根堆，不用繼續(xù)調(diào)整了
return;
} else {//否則，還需要繼續(xù)調(diào)整堆，直到滿足大根堆條件為止
swap(father, newFather);//值進行交換
father = newFather;//更新father的值，相當(dāng)于繼續(xù)調(diào)整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
}
}堆排序：對數(shù)組進行構(gòu)造堆(最大堆)
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,數(shù)組建堆
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數(shù)組中某個元素的下角標
* @param b data數(shù)組中某個元素的下角標
* @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數(shù)組中某個元素的下角標
* @param b data數(shù)組中某個元素的下角標
* @param c data數(shù)組中某個元素的下角標
* @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) {//如果原父結(jié)點就是三者最大，則不用繼續(xù)整理堆了
return;
} else {//父節(jié)點不是最大，則把大的孩子交換上來，然后繼續(xù)往下堆調(diào)整，直到滿足大根堆為止
swap(newFather, father);
father = newFather;//相當(dāng)于繼續(xù)shiftDown(newFather)。假如newFather原來是father的左孩子，那就相當(dāng)于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數(shù)組實現(xiàn)堆排序的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！
當(dāng)前題目：Java數(shù)組實現(xiàn)堆排序的示例分析
轉(zhuǎn)載源于：http://bm7419.com/article32/gosipc.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、建站公司、網(wǎng)站設(shè)計公司、品牌網(wǎng)站制作、做網(wǎng)站、網(wǎng)站營銷
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)
- 微信公眾號的方案有幾種風(fēng)格？ 2014-05-24
- 微信公眾號開發(fā)需要多少錢？ 2020-12-15
- 微信公眾號的盈利模式有幾種？ 2014-05-25
- 微信公眾號文章標題制作有什么技巧 2022-11-07
- 運營公眾號與微信小程序的區(qū)別？ 2016-09-19
- 『微信公眾號運營技巧』運營工具有哪些？ 2022-06-23
- 微信公眾號運營的基本原則是什么？ 2014-05-29
- 微信公眾號文章閱讀量是怎么算? 2013-10-04
- 同樣是公眾號的編輯你到底差在哪里？ 2014-02-26
- 轉(zhuǎn)換思路，公眾號吸粉并沒那么難！ 2016-11-13
- 什么類型的微信公眾號比較賺錢？ 2014-01-14
- 微信公眾號代運營主要包含哪些內(nèi)容?需要注意什么? 2022-07-13