堆排序的小例子,可以参考一下
#include <stdio.h>
int parent(int i)
{
return i/2;
}
int left_child(int i)
{
return 2*i;
}
int right_child(int i)
{
return 2*i+1;
}
//n the range needed to sort
void build_max_heap(int A[], int i, int n) // 数组A中,除A[i]外,其它元素是大顶堆
{
int max = i, temp;
if (i<0 || n<1 || i>=n)
return ;
/* find max element among a[i] a[left_child] a[right_child] */
if (left_child(i)<n && A[max]<A[left_child(i)])
max = left_child(i);
if (right_child(i)<n && A[max]<A[right_child(i)])
max = right_child(i);
// exchange a[i], a[max]
if (i!=max)
{
temp = A[i];
A[i] = A[max];
A[max] = temp;
build_max_heap(A, max, n);
}
return;
}
void max_heap_sort(int A[], int n)
{
int temp;
// exchange A[0] A[n-1]
if (n==1)
return ;
temp = A[0];
A[0] = A[n-1];
A[n-1] = temp;
build_max_heap(A, 0, n-1);
max_heap_sort(A, n-1);
}
int main()
{
int A[10] = {5,8,9,52,47,65,3,45,26,81};
int i, n = 10;
for (i=(n-1)/2; i>=0; i--)
{
build_max_heap(A, i, n);
}
max_heap_sort(A, n);
for (i=0; i<n; i++)
{
printf("%d ", A[i]);
}
printf("\n");
system("pause");
return 0;
}
分享到:
相关推荐
/*1.编写完整的堆排序程序*/ /*1.编写完整的堆排序程序*/
本资源提供了七大经典排序算法的实现程序,包括快速排序、冒泡排序、选择排序、归并排序、插入排序、希尔排序和堆排序。下面将逐一详细介绍这些排序算法及其原理。 1. 快速排序:由C.A.R. Hoare提出,是一种采用...
堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在本场景中,我们关注的是堆排序的源代码,它适用于openSUSE 11.4操作系统,并且是使用GCC version 4.5.1编译器编译的。在这个名为"sort...
下面是一个简单的C++代码示例: ```cpp #include using namespace std; void heapify(int arr[], int n, int i) { int largest = i; // 初始化最大值为根节点 int left = 2 * i + 1; int right = 2 * i + 2; ...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
本文将深入探讨四种在C++中实现的常见排序算法:插入排序、冒泡排序、堆排序和快速排序。这些算法各有特点,适用于不同的场景,理解并掌握它们对于提升编程能力至关重要。 1. **插入排序**: 插入排序是一种简单的...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
九九乘法表是简单的数值计算和字符串处理,而堆排序是一种基于比较的动态数据结构,需要理解和实现堆的构建、调整和提取最大/最小元素的过程。八皇后问题是一个经典的回溯算法应用,目标是在棋盘上放置八个皇后,...
下面是一个简单的C语言实现堆排序的示例: ```c #include void heapify(int arr[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left [left] > arr[largest]) ...
堆排序分为建堆和调整堆两个阶段,首先将无序序列构造成一个大顶堆或小顶堆,然后将堆顶元素与末尾元素交换,调整剩下的元素为新的堆,如此反复进行,直到所有元素排序完毕。堆排序是一种不稳定的排序方法,但效率...
本资源包含了几种常见的排序算法,包括堆排序、选择排序、冒泡排序、归并排序和插入排序。这些排序算法各有特点,适用于不同的场景,并且在理解它们的工作原理后,能够帮助初学者更好地掌握编程基础。 1. **堆排序*...
以下是一个简单的C++堆排序示例: ```cpp #include using namespace std; void heapify(int arr[], int n, int i) { int largest = i; // 初始化最大元素为根 int left = 2 * i + 1; int right = 2 * i + 2; ...
以下问题要求统一在一个大程序里解决。 21、折半插入排序 22、21、折半插入排序 22、冒泡排序 21、折半插入排序 22、冒泡排序 23、快速排序 21、折半插入排序 22、冒泡排序 23、快速排序 24、简单选择排序 21、折半...
2. **堆排序**:堆排序是利用二叉堆(最大堆或最小堆)性质进行排序的一种方法。首先将待排序的序列构造成一个大顶堆,然后将堆顶元素与最后一个元素交换,接着重新调整堆,再将新的堆顶元素与倒数第二个元素交换,...
堆排序首先将待排序的序列构造成一个大顶堆(或小顶堆),然后将堆顶元素(最大或最小元素)与末尾元素交换,接着重新调整剩余元素为堆,重复此过程直到所有元素都排好序。堆排序的平均和最坏情况时间复杂度均为O(n ...
本文将深入探讨五种常用的排序算法:快速排序、归并排序、选择排序、谢尔排序和堆排序。 **快速排序** 是由C.A.R. Hoare在1960年提出的,是一种效率较高的分治策略。其基本思想是通过一趟排序将待排序的数据分割成...
5. **堆排序**:堆排序是一种树形选择排序,它的基本思想是建立一个大顶堆或小顶堆,然后将堆顶元素与末尾元素交换,调整剩余元素重新成堆,如此反复进行。源码实现主要包括建堆、交换堆顶与末尾元素、调整堆的过程...
本文将深入探讨Java编程语言中实现的七种主要排序算法:直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序以及归并排序。每种算法都有其独特性,适用于不同的场景和数据特性。 1. **直接插入排序**:...
- 堆排序利用了堆这种数据结构,先将待排序序列构造成一个大顶堆或小顶堆,然后将堆顶元素与末尾元素交换,调整剩下的元素重新构造成堆,直到整个序列有序。 - C# 实现堆排序时,主要涉及建堆、交换堆顶和调整堆的...
10种排序算法代码+综合比较代码(直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、折半插入排序、2路插入排序),其中不仅有各种排序算法的代码,还包含10种代码在关键字...