歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

【算法導論】C++實現堆排序

堆排序的過程就不說明了,代碼如下:

  1. void Build_Max_Heap(int array_list[] ,const int array_size,const int index); 
  2. bool HeapSort(int array_list[],const int array_size); 
  3. int main() 
  4.     const int size = 10; 
  5.     int array_list [] ={16,14,10,8,7,9,3,2,4,1}; 
  6.     HeapSort(array_list,size); 
  7.      
  8.     return 0; 
  9. bool HeapSort(int array_list[],const int array_size) 
  10.     if(array_size < 0) 
  11.     { 
  12.         return false
  13.     } 
  14.     for(int i=0;i<array_size;i++) 
  15.     { 
  16.         for(int j = ((array_size - i)/2-1);j>=0;j--) 
  17.         { 
  18.             Build_Max_Heap(array_list,array_size - i,j); 
  19.         } 
  20.         int tmp = array_list[0]; 
  21.         array_list[0] = array_list[array_size -1 - i]; 
  22.         array_list[array_size -1 - i] = tmp; 
  23.         std::cout<<"Sorted:"<<i+1<<"\t"; 
  24.         for(int i=0;i<array_size;i++) 
  25.         { 
  26.             std::cout<<array_list[i]<<"\t"; 
  27.         } 
  28.         std::cout<<std::endl; 
  29.     } 
  30.     return true
  31. /*構建大根堆*/ 
  32. void Build_Max_Heap(int array_list[] ,const int array_size,const int index) 
  33.     int left_index = 2*index + 1; 
  34.     int right_index = 2*index + 2; 
  35.     int largest = index; 
  36.     if((right_index < array_size) ) 
  37.     {/*在建立大根堆時,如果父節點比兩個子節點都小,則交換最大的一個子節點*/ 
  38.         if((array_list[left_index] < array_list[right_index])) 
  39.         { 
  40.             largest = right_index; 
  41.         } 
  42.         else 
  43.         { 
  44.             largest = left_index; 
  45.         } 
  46.     } 
  47.     else 
  48.     { 
  49.         if(left_index < array_size) 
  50.         { 
  51.             largest = left_index; 
  52.         } 
  53.     } 
  54.     if((array_list[index] < array_list[largest]) && (largest != index)) 
  55.     { 
  56.         int tmp = array_list[index]; 
  57.         array_list[index] = array_list[largest]; 
  58.         array_list[largest] = tmp; 
  59.         /*如果交換了某個節點的值,則需要遞歸交換其子樹的節點*/ 
  60.         Build_Max_Heap(array_list,array_size,largest); 
  61.     } 
Copyright © Linux教程網 All Rights Reserved