排序算法之堆排序(代码片段)

  1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 
  5 using namespace std;
  6 
  7 //大根堆
  8 
  9 void push_up(vector<int>&heap , int heapPosize)
 10 
 11     int t = heapPosize;
 12     while (t/2 && heap[t/2] < heap[t])///在堆里面，计数是从一开始的
 13     
 14         swap(heap[t],heap[t/2]);
 15         t = t/2;
 16     
 17 
 18 void push_down(vector<int> &heap ,int heapSize, int heapPosion)
 19 
 20     int t = heapPosion ;
 21     int leftChild = heapPosion*2;
 22     int rightChild = heapPosion*2+1;
 23     if (leftChild <= heapSize && heap[t] < heap[leftChild])
 24     
 25         t = leftChild ;
 26     
 27     if (rightChild <= heapSize && heap[t] < heap[rightChild])
 28     
 29         t = rightChild ;
 30     
 31     if (t != heapPosion)
 32     
 33         swap( heap[t] , heap[heapPosion]);
 34         push_down(heap , heapSize , t);
 35     
 36 
 37 void insert(vector<int>&heap ,int data, int &heapsize)
 38 
 39     heap.push_back(data);
 40     heapsize++;
 41     push_up(heap,heapsize);
 42 
 43 
 44 void remove_top(vector<int>&heap , int &heapsize)
 45 
 46    swap(heap[1],heap[heapsize]);
 47    heapsize--;
 48    heap.pop_back();
 49    push_down(heap,heapsize,1);
 50 
 51 int creatHeap(vector<int> &heap )
 52 
 53     int length = heap.size();
 54     heap.push_back(0);
 55 
 56     for (int i = length ; i > 0 ; i --) ///将heap的长度加一，移动数据
 57     
 58         heap[i] = heap[i-1];
 59     
 60 
 61     for(int i =1 ;i <= length ;i++)
 62     
 63         push_up(heap,i);
 64 
 65         printf("push_up 第%d次 :" ,i);
 66         for (int j =1 ;j <= length ;j++)
 67         
 68             printf("%d ",heap[j]);
 69         
 70         printf("\n");
 71     
 72     return length;
 73 
 74 void heap_sort(vector<int> &heap ,int heapSize)
 75 
 76     //int heapSize = creatHeap(heap);
 77     int size = heapSize;
 78     for (int i = 1 ; i <= size ;++i)
 79     
 80         swap(heap[1],heap[heapSize]);
 81         heapSize--;
 82         push_down(heap , heapSize , 1);
 83         printf("push_down 第%d次 :" ,i);
 84         for (int j =1 ;j <= size ;j++)
 85         
 86             printf("%d ",heap[j]);
 87         
 88         printf("\n");
 89     
 90     for (int i = 0 ; i < size ;i++) ///将数据还原
 91     
 92         heap[i] = heap[i+1];
 93     
 94     heap.pop_back();
 95 
 96 #define n 5
 97 int main()
 98 
 99     vector<int> heapData;
100     heapData.resize(n);
101     for(int i = 0 ; i < n ;i++)
102     
103         cin >> heapData[i];
104     
105 
106     puts("排序前的数据为 ：");
107     for(int i = 0 ; i < n ;i++)
108     
109         printf("%d ",heapData[i]);
110     
111     printf("\n");
112 
113     int length = creatHeap(heapData);
114     remove_top(heapData,length);
115     puts("删除头节点后的值为 ：");
116     for(int i = 1 ; i <= length ;i++)
117     
118         printf("%d ",heapData[i]);
119     
120     printf("\n");
121 
122     puts("增加节点后的值为 ：");
123     insert(heapData ,26515, length);
124     for(int i = 1 ; i <= length ;i++)
125     
126         printf("%d ",heapData[i]);
127     
128     printf("\n");
129 
130     heap_sort(heapData,length);
131     puts("排序后的数据为 ：");
132     for(int i = 0 ; i < length ;i++)
133     
134         printf("%d ",heapData[i]);
135     
136     printf("\n");
137     return 0;
138