欧美大屁股bbbbxxxx,狼人大香伊蕉国产www亚洲,男ji大巴进入女人的视频小说,男人把ji大巴放进女人免费视频,免费情侣作爱视频

歡迎來到入門教程網(wǎng)!

C語言

當前位置:主頁 > 軟件編程 > C語言 >

C語言實現(xiàn)基于最大堆和最小堆的堆排序算法示例

來源:本站原創(chuàng)|時間:2020-01-10|欄目:C語言|點擊: 次

堆定義
堆實際上是一棵完全二叉樹,其任何一非葉節(jié)點滿足性質(zhì):
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2](小頂堆)或者:Key[i]>=Key[2i+1]&&key>=key[2i+2](大頂堆)
即任何一非葉節(jié)點的關(guān)鍵字不大于或者不小于其左右孩子節(jié)點的關(guān)鍵字。

堆排序的思想
利用大頂堆(小頂堆)堆頂記錄的是最大關(guān)鍵字(最小關(guān)鍵字)這一特性,使得每次從無序中選擇最大記錄(最小記錄)變得簡單。

  • 最大堆:所有節(jié)點的子節(jié)點比其自身小的堆。
  • 最小堆:所有節(jié)點的子節(jié)點比其自身大的堆。

這里以最大堆為基礎(chǔ),其基本思想為:

1.將初始待排序關(guān)鍵字序列(R1,R2....Rn)構(gòu)建成大頂堆,此堆為初始的無序區(qū);
2.將堆頂元素R[1]與最后一個元素R[n]交換,此時得到新的無序區(qū)(R1,R2,......Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2...n-1]<=R[n];
3.由于交換后新的堆頂R[1]可能違反堆的性質(zhì),因此需要對當前無序區(qū)(R1,R2,......Rn-1)調(diào)整為新堆,然后再次將R[1]與無序區(qū)最后一個元素交換,得到新的無序區(qū)(R1,R2....Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復此過程直到有序區(qū)的元素個數(shù)為n-1,則整個排序過程完成。

C語言實現(xiàn)
1.基于最大堆實現(xiàn)升序排序

// 初始化堆
void initHeap(int a[], int len) {
 // 從完全二叉樹最后一個非子節(jié)點開始
 // 在數(shù)組中第一個元素的索引是0
 // 第n個元素的左孩子為2n+1,右孩子為2n+2,
 // 最后一個非子節(jié)點位置在(n - 1) / 2
 for (int i = (len - 1) / 2; i >= 0; --i) {
  adjustMaxHeap(a, len, i);
 }
}
 
void adjustMaxHeap(int a[], int len, int parentNodeIndex) {
 // 若只有一個元素,那么只能是堆頂元素,也沒有必要再排序了
 if (len <= 1) {
  return;
 }
 
 // 記錄比父節(jié)點大的左孩子或者右孩子的索引
 int targetIndex = -1;
 
 // 獲取左、右孩子的索引
 int leftChildIndex = 2 * parentNodeIndex + 1;
 int rightChildIndex = 2 * parentNodeIndex + 2;
 
 // 沒有左孩子
 if (leftChildIndex >= len) {
  return;
 }
 
 // 有左孩子,但是沒有右孩子
 if (rightChildIndex >= len) {
  targetIndex = leftChildIndex;
 }
 // 有左孩子和右孩子
 else {
  // 取左、右孩子兩者中最大的一個
  targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex;
 }
 
 // 只有孩子比父節(jié)點的值還要大,才需要交換
 if (a[targetIndex] > a[parentNodeIndex]) {
  int temp = a[targetIndex];
  
  a[targetIndex] = a[parentNodeIndex];
  a[parentNodeIndex] = temp;
  
  
  // 交換完成后,有可能會導致a[targetIndex]結(jié)點所形成的子樹不滿足堆的條件,
  // 若不滿足堆的條件,則調(diào)整之使之也成為堆
  adjustMaxHeap(a, len, targetIndex);
 }
}
 
void heapSort(int a[], int len) {
 if (len <= 1) {
  return;
 }
 
 // 初始堆成無序最大堆
 initHeap(a, len);
 
 for (int i = len - 1; i > 0; --i) {
  // 將當前堆頂元素與最后一個元素交換,保證這一趟所查找到的堆頂元素與最后一個元素交換
  // 注意:這里所說的最后不是a[len - 1],而是每一趟的范圍中最后一個元素
  // 為什么要加上>0判斷?每次不是說堆頂一定是最大值嗎?沒錯,每一趟調(diào)整后,堆頂是最大值的
  // 但是,由于len的范圍不斷地縮小,導致某些特殊的序列出現(xiàn)異常
  // 比如說,5, 3, 8, 6, 4序列,當調(diào)整i=1時,已經(jīng)調(diào)整為3,4,5,6,8序列,已經(jīng)有序了
  // 但是導致了a[i]與a[0]交換,由于變成了4,3,5,6,8反而變成無序了!
  if (a[0] > a[i]) {
   int temp = a[0];
   a[0] = a[i];
   a[i] = temp;
  }
  
  // 范圍變成為:
  // 0...len-1
  // 0...len-1-1
  // 0...1 // 結(jié)束
  // 其中,0是堆頂,每次都是找出在指定的范圍內(nèi)比堆頂還大的元素,然后與堆頂元素交換
  adjustMaxHeap(a, i - 1, 0);
 }
}

2.基于最小堆實現(xiàn)降序排序

// 初始化堆
void initHeap(int a[], int len) {
 // 從完全二叉樹最后一個非子節(jié)點開始
 // 在數(shù)組中第一個元素的索引是0
 // 第n個元素的左孩子為2n+1,右孩子為2n+2,
 // 最后一個非子節(jié)點位置在(n - 1) / 2
 for (int i = (len - 1) / 2; i >= 0; --i) {
  adjustMinHeap(a, len, i);
 }
}
 
void adjustMinHeap(int a[], int len, int parentNodeIndex) {
 // 若只有一個元素,那么只能是堆頂元素,也沒有必要再排序了
 if (len <= 1) {
  return;
 }
 
 // 記錄比父節(jié)點大的左孩子或者右孩子的索引
 int targetIndex = -1;
 
 // 獲取左、右孩子的索引
 int leftChildIndex = 2 * parentNodeIndex + 1;
 int rightChildIndex = 2 * parentNodeIndex + 2;
 
 // 沒有左孩子
 if (leftChildIndex >= len) {
  return;
 }
 
 // 有左孩子,但是沒有右孩子
 if (rightChildIndex >= len) {
  targetIndex = leftChildIndex;
 }
 // 有左孩子和右孩子
 else {
  // 取左、右孩子兩者中最上的一個
  targetIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex;
 }
 
 // 只有孩子比父節(jié)點的值還要小,才需要交換
 if (a[targetIndex] < a[parentNodeIndex]) {
  int temp = a[targetIndex];
  
  a[targetIndex] = a[parentNodeIndex];
  a[parentNodeIndex] = temp;
  
  
  // 交換完成后,有可能會導致a[targetIndex]結(jié)點所形成的子樹不滿足堆的條件,
  // 若不滿足堆的條件,則調(diào)整之使之也成為堆
  adjustMinHeap(a, len, targetIndex);
 }
}
 
void heapSort(int a[], int len) {
 if (len <= 1) {
  return;
 }
 
 // 初始堆成無序最小堆
 initHeap(a, len);
 
 for (int i = len - 1; i > 0; --i) {
  // 將當前堆頂元素與最后一個元素交換,保證這一趟所查找到的堆頂元素與最后一個元素交換
  // 注意:這里所說的最后不是a[len - 1],而是每一趟的范圍中最后一個元素
  // 為什么要加上>0判斷?每次不是說堆頂一定是最小值嗎?沒錯,每一趟調(diào)整后,堆頂是最小值的
  // 但是,由于len的范圍不斷地縮小,導致某些特殊的序列出現(xiàn)異常
  // 比如說,5, 3, 8, 6, 4序列,當調(diào)整i=1時,已經(jīng)調(diào)整為3,4,5,6,8序列,已經(jīng)有序了
  // 但是導致了a[i]與a[0]交換,由于變成了4,3,5,6,8反而變成無序了!
  if (a[0] < a[i]) {
   int temp = a[0];
   a[0] = a[i];
   a[i] = temp;
  }
  
  // 范圍變成為:
  // 0...len-1
  // 0...len-1-1
  // 0...1 // 結(jié)束
  // 其中,0是堆頂,每次都是找出在指定的范圍內(nèi)比堆頂還小的元素,然后與堆頂元素交換
  adjustMinHeap(a, i - 1, 0);
 }
}

3.C語言版測試

大家可以測試一下:

// int a[] = {5, 3, 8, 6, 4};
int a[] = {89,-7,999,-89,7,0,-888,7,-7};
heapSort(a, sizeof(a) / sizeof(int));
 
for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {
  NSLog(@"%d", a[i]);
}

上一篇:C基礎(chǔ) mariadb處理的簡單實例

欄    目:C語言

下一篇:C/C++雜記 虛函數(shù)的實現(xiàn)的基本原理(圖文)

本文標題:C語言實現(xiàn)基于最大堆和最小堆的堆排序算法示例

本文地址:http://mengdiqiu.com.cn/a1/Cyuyan/2271.html

網(wǎng)頁制作CMS教程網(wǎng)絡(luò)編程軟件編程腳本語言數(shù)據(jù)庫服務(wù)器

如果侵犯了您的權(quán)利,請與我們聯(lián)系,我們將在24小時內(nèi)進行處理、任何非本站因素導致的法律后果,本站均不負任何責任。

聯(lián)系QQ:835971066 | 郵箱:835971066#qq.com(#換成@)

Copyright © 2002-2020 腳本教程網(wǎng) 版權(quán)所有