滴水逆向联盟

标题: 基于visual Studio2013解决面试题之0209最大堆排序 [打印本页]

---

作者: 大灰狼    时间: 2014-8-1 08:45
标题: 基于visual Studio2013解决面试题之0209最大堆排序


题目

解决代码及点评

• <pre code_snippet_id="110194" snippet_file_name="blog_20131213_1_5584546" class="cpp" name="code"><pre code_snippet_id="110194" snippet_file_name="blog_20131213_1_5584546" class="cpp" name="code"><pre code_snippet_id="110194" snippet_file_name="blog_20131213_1_5584546" class="cpp" name="code"><pre code_snippet_id="110194" snippet_file_name="blog_20131213_1_5584546" name="code" class="cpp"><pre code_snippet_id="110194" snippet_file_name="blog_20131213_1_5584546" name="code" class="cpp">/*
•     最大堆是一个数组数据结构，任意一个下标i，它的值大于i*2和i*2+1的值(i从1开始)
•     当这样的堆形成时，最大值在数组最开始的位置。
•     当这样的堆形成后，将第一个元素交换到最后，并在剩余的数据中再调整堆，形成新的堆
•     如此反复完成排序
• */  
•   
• #include <iostream>  
•   
• using namespace std;  
•   
• void swap(int *a, int *b)  
• {  
•     int temp;  
•     temp = *a;  
•     *a = *b;  
•     *b = temp;  
• }  
•   
• /*
•      堆调整函数，i表示需要调整的下标
•      size表示堆长度
•      最大堆的要求是i的值大于i*2的值和i*2+1的值
• */  
• void heap_adjust(int *a, int i, int size)  
• {  
•     int lchild = 2 * i;  
•     int rchild = 2 * i + 1;  
•     int max = i;  
•   
•     if (i <= size / 2) //大于size/2的为叶子节点，不需要调整  
•     {  
•         if (lchild <= size && a[lchild] > a[max])  
•             max = lchild;  
•         if (rchild <= size && a[rchild] > a[max])  
•             max = rchild;  
•         if (max != i)  
•         {  
•             swap(&a, &a[max]);  
•             heap_adjust(a, max, size); //依此调整下面的子树，为了防止交换之后不满足堆的性质  
•         }  
•     }  
• }  
•   
• /*
•     创建堆就是调整堆的过程
• */  
• void create_heap(int *a, int size)  
• {  
•     int i = 0;  
•     for (i = size / 2; i >= 1; i--)  
•         heap_adjust(a, i, size);  
• }  
•   
• /*
•     堆排序
•     a存放数组
•     size表示长度，注意，数据是从下标[1, size]
• */  
• void heap_sort(int *a, int size)  
• {  
•     int i = 0;  
•     int temp = 0;  
•   
•     // 创建最大堆  
•     create_heap(a, size);  
•   
•     for (i = size; i >= 1; i--)  
•     {  
•         // 把第一个值，交换到最后去，最大堆里，第一个值是最大的  
•         // 把它交换到最后的位置，相当于已经有一个数据排序好了  
•         swap(&a, &a[1]);  
•   
•         // 交换之后堆就被破坏了  
•         // 那么需要对除了最后一个元素外的其他元素进行堆调整  
•         // 形成新的最大堆，如此循环完成排序  
•         heap_adjust(a, 1, i - 1);  
•     }  
• }  
•   
• int main(int argc, char **argv)  
• {  
•     int a[100];  
•     int size = 0;  
•     cout << "堆个数：";  
•     // 输入堆中数值个数  
•     while (scanf_s("%d", &size) == 1 && size > 0)  
•     {  
•         int i = 0;  
•         // 从键盘输入数值，并保存在数组  
•         for (i = 1; i <= size; i++)  
•             scanf_s("%d", &a);  
•   
•         // 在数组上进行堆排序，注意下标是从1开始到size，下标为0的值没有用  
•         // 主要是为了方便计算  
•         heap_sort(a, size);  
•   
•         // 打印排序结果  
•         for (i = 1; i <= size; i++)  
•             printf("%d ", a);  
•     }  
•   
•     return 0;  
• }  
•   
• </pre><br></pre><br></pre></pre></pre>  
  
  

代码下载及其运行

代码下载地址：http://download.csdn.net/detail/yincheng01/6704519

解压密码：c.itcast.cn

下载代码并解压后，用VC2013打开interview.sln，并设置对应的启动项目后，点击运行即可，具体步骤如下：

1）设置启动项目：右键点击解决方案，在弹出菜单中选择“设置启动项目”

2）在下拉框中选择相应项目，项目名和博客编号一致

3）点击“本地Windows调试器”运行

程序运行结果

---

欢迎光临 滴水逆向联盟 (http://dtdebug.com/)

Powered by Discuz! X3.2