欧美成人午夜免费全部完,亚洲午夜福利精品久久,а√最新版在线天堂,另类亚洲综合区图片小说区,亚洲欧美日韩精品色xxx

扣丁學(xué)堂Java培訓(xùn)之排序算法之堆排思想及代碼實(shí)現(xiàn)

2019-02-13 13:26:34 1305瀏覽

今天扣丁學(xué)堂Java培訓(xùn)老師給大家介紹一下關(guān)于Java排序算法之堆排思想及代碼實(shí)現(xiàn)，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧。

什么是頂堆？它是一顆完全二叉樹，頂堆有大頂堆和小頂堆兩種。所謂大頂堆就是在這顆完全二叉樹中，任何一顆子樹都滿足：父結(jié)點(diǎn)的值>孩子結(jié)點(diǎn)的值；小頂堆則相反。

如圖：

什么是堆排序(Heapsort)？利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素。

現(xiàn)在給我們一個(gè)無序數(shù)組，我們將其從小到大排序，使用堆排序的實(shí)現(xiàn)步驟和思想如下：

1.讓這個(gè)數(shù)組變成一個(gè)大根堆

2.將最后一個(gè)位置和堆頂位置作交換

3.將堆的大小進(jìn)行-1操作

4.將當(dāng)前的堆變成一個(gè)大頂堆

5.回到2

看起來似乎很抽象，那我們現(xiàn)在用一個(gè)例子進(jìn)行講解：假設(shè)一個(gè)整型數(shù)組arr={2,1,3,6,0,5}

1.將一個(gè)無序數(shù)組變成一個(gè)大頂堆存儲(chǔ)

如果使用完全二叉樹進(jìn)行存儲(chǔ)數(shù)組，任意下標(biāo)為index的結(jié)點(diǎn)的父結(jié)點(diǎn)的下標(biāo)應(yīng)該是(index-1)/2，其孩子結(jié)點(diǎn)的下標(biāo)應(yīng)分別為：(index*2+1)和(index*2+2)。我們使用該結(jié)論創(chuàng)建一個(gè)大頂堆：

首先我們假設(shè)0位置上的數(shù)已經(jīng)排好，將其放在這棵二叉樹的根位置，創(chuàng)建一個(gè)int類型變量i記錄當(dāng)前指向的數(shù)組的下標(biāo)，初始化值為1。

設(shè)置一個(gè)index初始化值=i，將index和(index-1)/2位置的數(shù)進(jìn)行比較，也就是和它的父結(jié)點(diǎn)進(jìn)行比較，如果比父結(jié)點(diǎn)小就不變，并進(jìn)行i++，index=i；如果比父結(jié)點(diǎn)大就和父結(jié)點(diǎn)交換并且給index賦值為(index-1)/2，即指向原來位置的父結(jié)點(diǎn)，再將該值與當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)進(jìn)行比較…直到該結(jié)點(diǎn)值是小于該結(jié)點(diǎn)父結(jié)點(diǎn)的值或到根結(jié)點(diǎn)時(shí)停止。

以arr數(shù)組進(jìn)行舉例：

0位置上的數(shù)是2，先認(rèn)為它是已經(jīng)排好的，i和index此時(shí)都為1，(index-1)/2為0，所以將1和2進(jìn)行比較，1<2所以1位置上的數(shù)不變，執(zhí)行i++,index=i；

此時(shí)i和index值都為2，(index-1)/2為0，所以講3和2進(jìn)行比較，3>2所以將3和2進(jìn)行交換，原數(shù)組就變?yōu)椋簕3,1,2,6,0,5}，index=(index-1)/2=0，當(dāng)前結(jié)點(diǎn)是根節(jié)點(diǎn)，不再進(jìn)行比較了，執(zhí)行i++,index=i；

此時(shí)i和index值都為3，(index-1)/2為1，所以將6和1進(jìn)行比較，6>1所以將6和2進(jìn)行交換，原數(shù)組就變?yōu)椋簕3,6,2,1,0,5}，index=(index-1)/2=1，不是根節(jié)點(diǎn)，于是再將6和3進(jìn)行比較，6>3，所以再交換6和3，原數(shù)組變?yōu)椋簕6,3,2,1,0,5}，index=(index-1)/2=0，當(dāng)前結(jié)點(diǎn)是根節(jié)點(diǎn)，不再進(jìn)行比較了，執(zhí)行i++,index=i；

…….

以此類推最后得到的數(shù)組：{6,3,5,1,0,2}

最后得到的大頂堆：

代碼實(shí)現(xiàn)：

// 插入數(shù)使其形成大頂堆
public static void heapInsert(int[] arr, int index) {
  while(arr[index] > arr[(index - 1)/2]) {
    swap(arr, index, (index - 1)/2);
    index = (index - 1)/2;
  }
}

2.將形成的大頂堆最后一個(gè)元素和根進(jìn)行交換

在該例子中應(yīng)該是將2和6進(jìn)行交換，得到：

得到的數(shù)組：{2,3,5,1,0,6}

那我們?yōu)槭裁匆M(jìn)行交換呢？

這時(shí)候的數(shù)組最后一個(gè)值就是最大的了，也就是最后一個(gè)位置上的數(shù)已經(jīng)排好了，接下來我們就要將除了最后位置的結(jié)點(diǎn)之外剩下的完全二叉樹進(jìn)行排序了，即：

要進(jìn)行排序的部分：{2,3,5,1,0}

3.將除了最后一個(gè)結(jié)點(diǎn)剩下的完全二叉樹轉(zhuǎn)化成一個(gè)新的大頂堆

傳入當(dāng)前數(shù)組，并標(biāo)記當(dāng)前位置index，初始化值為0，先判斷當(dāng)前的index位置的結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)，如果是葉子結(jié)點(diǎn)就不需要再比較了，直接返回；如果不是葉子結(jié)點(diǎn)，則將index位置的值和它孩子結(jié)點(diǎn)的值進(jìn)行比較，如果index位置上的值最大則不交換并且直接返回，否則選取最大的值與index位置上的值進(jìn)行交換；交換后index為當(dāng)前位置，再與當(dāng)前位置的孩子結(jié)點(diǎn)進(jìn)行比較。。。以此類推直到當(dāng)前結(jié)點(diǎn)是一個(gè)葉子結(jié)點(diǎn)或不需要再交換時(shí)停止。

該例子中：index位置上的值是2，該位置的孩子結(jié)點(diǎn)分別為3和5，將2和5進(jìn)行交換之后，index=index*2+2=2，此時(shí)index位置結(jié)點(diǎn)是一個(gè)葉子結(jié)點(diǎn)，不再進(jìn)行交換，此時(shí)構(gòu)成了一個(gè)新的大頂堆。如圖：

得到的數(shù)組：{5,3,2,1,0,6}

然后就回到了步驟2，直到數(shù)組中未排序的部分只有一個(gè)數(shù)時(shí)不再進(jìn)行排序。

完整代碼實(shí)現(xiàn)：

/**
 * @author LZD   2018/03/01
 */
public class HeapSort {
  public static void heapSort(int[] arr) {
    if(arr == null || arr.length < 2)
      return;
    // 構(gòu)建大頂堆
    for(int i = 0;i < arr.length;i++) {
      heapInsert(arr, i);
    }
    int heapSize = arr.length;
    swap(arr, 0, --heapSize);
    while(heapSize > 0) {
      heapify(arr, 0, heapSize);
      swap(arr, 0, --heapSize);
    }
  }
  // 插入數(shù)使其形成大頂堆
  public static void heapInsert(int[] arr, int index) {
    while(arr[index] > arr[(index - 1)/2]) {
      swap(arr, index, (index - 1)/2);
      index = (index - 1)/2;
    }
  }
  // 將堆化為大頂堆
  public static void heapify(int[] arr, int index, int heapSize) {
    // 先判斷當(dāng)前的index位置的結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)
    int left = index * 2 + 1;
    while(left < heapSize) {
      // 不是葉子結(jié)點(diǎn)則選出index位置結(jié)點(diǎn)的孩子結(jié)點(diǎn)中較大的賦給largest
      int largest = left+1 < heapSize && arr[left + 1] > arr[left]
          ? left + 1: left;
      largest = arr[largest] > arr[index] ? largest : index;
      if(largest == index) {
        break;
      }
      swap(arr, largest, index);
      index = largest;
      left = index * 2 + 1;
    }
  }
  public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
  // for test 打印數(shù)組
  public static void printArray(int[] arr) {
    for(int i = 0;i < arr.length;i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
  // for test
  public static void main(String[] args) {
    int[] arr = {2, 1, 3, 6, 0, 5};
    heapSort(arr);
    printArray(arr);
  }
}

以上就是關(guān)于扣丁學(xué)堂Java培訓(xùn)之排序算法之堆排思想及代碼實(shí)現(xiàn)的全部內(nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，最后想要了解更多請(qǐng)關(guān)注扣丁學(xué)堂Java培訓(xùn)官網(wǎng)、微信等平臺(tái)，扣丁學(xué)堂IT職業(yè)在線學(xué)習(xí)教育平臺(tái)不僅為您提供權(quán)威的Java視頻教程供大家學(xué)習(xí)，還精心的準(zhǔn)備了Java從入門到精通開發(fā)實(shí)戰(zhàn)技能，定能讓你學(xué)有所成。扣丁學(xué)堂Java技術(shù)交流群：670348138。

【關(guān)注微信公眾號(hào)獲取更多學(xué)習(xí)資料】

查看更多關(guān)于“Java開發(fā)資訊”的相關(guān)文章>>