C语言数据结构之堆排序源代码

本文实例为大家分享了C语言堆排序源代码，供大家参考，具体内容如下

1. 堆排序

堆排序的定义及思想可以参考百度百科：

用一句概括，堆排序就是一种改进的选择排序，改进的地方在于，每次做选择的时候，不单单把最大的数字选择出来，而且把排序过程中的一些操作进行了记录，这样在后续排序中可以利用，并且有分组的思想在里面，从而提高了排序效率，其效率为O(n*logn).

2. 源代码

堆排序中有两个核心的操作，一个是创建大顶堆（或者小顶堆，这里用的是大顶堆），再一个就是对堆进行调整。这里需要注意的是，并没有真正的创建堆，只是利用完全二叉树的特性，将其对应到数组的下标中（例如对于节点i，如果其存在左孩子和右孩子，那么其下标一定是2*i, 和2*i+1）其中创建的时候是从下向上创建，而调整则是从上向下调整。

这里为了方便，堆从a[1]位置开始。

代码运行结果如下：

源代码如下：

#include<stdio.h> 

int c=0; 

/*heapadjust()函数的功能是实现从a[m]到a[n]的数据进行调整，使其满足大顶堆的特性*/
/*a[]是待处理的数组，m是起始坐标， n是终止坐标*/
void heapadjust(int a[], int m, int n)
{
  int i, temp;
  temp=a[m]; 

  for(i=2*m;i<=n;i*=2)//从m的左孩子开始
  {
    if(i+1<=n && a[i]<a[i+1])//如果左孩子小于右孩子，则将i++，这样i的值就是最大孩子的下标值
    {
      i++;
    } 

    if(a[i]<temp)//如果最大的孩子小于temp，则不做任何操作，退出循环；否则交换a[m]和a[i]的值，将最大值放到a[i]处
    {
      break;
    }
    a[m]=a[i];
    m=i;
  }
  a[m]=temp;
} 

void crtheap(int a[], int n)//初始化创建一个大顶堆
{
  int i;
  for(i=n/2; i>0; i--)//n/2为最后一个双亲节点，依次向前建立大顶堆
  {
    heapadjust(a, i, n);
  }
} 

/*swap()函数的作用是将a[i]和a[j]互换*/
void swap(int a[], int i, int j)
{
  int temp;
  temp=a[i];
  a[i]=a[j];
  a[j]=temp;
  c++;
} 

void heapsort(int a[], int n)
{
  int i; 

  crtheap(a, n);
  for(i=n; i>1; i--)
  {
    swap(a, 1, i);//将第一个数，也就是从a[1]到a[i]中的最大的数，放到a[i]的位置
    heapadjust(a, 1, i-1);//对剩下的a[1]到a[i]，再次进行堆排序，选出最大的值，放到a[1]的位置
  }
} 

int main(void)
{
  int i;
  int a[10]={-1,5,2,6,0,3,9,1,7,4};
  printf("排序前：");
  for(i=1;i<10;i++)
  {
    printf("%d",a[i]);
  }
  heapsort(a, 9);
  printf("\n\n共交换数据%d次\n\n", c);
  printf("排序后：");
  for(i=1;i<10;i++)
  {
    printf("%d",a[i]);
  }
  printf("\n\n\n");
  return 0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

您可能感兴趣的文章:

  • C语言 数据结构堆排序顺序存储（升序）
  • C语言实现基于最大堆和最小堆的堆排序算法示例
  • C语言实现堆排序的简单实例
  • C语言对堆排序一个算法思路和实现代码
赞 (0)

相关推荐

  • C语言 数据结构堆排序顺序存储（升序）

    堆排序顺序存储(升序) 一: 完全二叉树的概念:前h-1层为满二叉树,最后一层连续缺失右结点! 二:首先堆是一棵全完二叉树: a:构建一个堆分为两步:⑴创建一棵完全二叉树      ⑵调整为一个堆 (标注:大根堆为升序,小根堆为降序) b:算法描述:①创建一棵完全二叉树 ②while(有双亲){ A:调整为大根堆: B:交换根和叶子结点: C:砍掉叶子结点: } c:时间复杂度为 O(nlogn)  ,空间复杂度为 O(1), 是不稳定排序! 代码实现: /*堆排序思想:[完全二叉树的定义:前

  • C语言对堆排序一个算法思路和实现代码

    算法思想简单描述: 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称之为堆.在这里只讨论满足前者条件的堆. 由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项.完全二叉树可以很直观地表示堆的结构.堆顶为根,其它为左子树.右子树. 初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的

  • C语言实现基于最大堆和最小堆的堆排序算法示例

    堆定义 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质: Key[i]<=key[2i+1]&&Key[i]<=key[2i+2](小顶堆)或者:Key[i]>=Key[2i+1]&&key>=key[2i+2](大顶堆) 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字. 堆排序的思想 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单. 最大堆:所有节点的子节点比其

  • C语言实现堆排序的简单实例

    本文通过一个C语言实现堆排序的简单实例,帮助大家抛开复杂的概念,更好的理解堆排序. 实例代码如下: void FindMaxInHeap(int arr[], const int size) { for (int j = size - 1; j > 0; --j) { int parent = j / 2; int child = j; if (j < size - 1 && arr[j] < arr[j+1]) { ++child; } if (arr[child] &

  • C语言数据结构之堆排序源代码

    C语言数据结构之堆排序源代码

    本文实例为大家分享了C语言堆排序源代码,供大家参考,具体内容如下 1. 堆排序 堆排序的定义及思想可以参考百度百科: 用一句概括,堆排序就是一种改进的选择排序,改进的地方在于,每次做选择的时候,不单单把最大的数字选择出来,而且把排序过程中的一些操作进行了记录,这样在后续排序中可以利用,并且有分组的思想在里面,从而提高了排序效率,其效率为O(n*logn). 2. 源代码 堆排序中有两个核心的操作,一个是创建大顶堆(或者小顶堆,这里用的是大顶堆),再一个就是对堆进行调整.这里需要注意的是,并没有真

  • C语言数据结构之堆排序详解

    C语言数据结构之堆排序详解

    目录 1.堆的概念及结构 2.堆的实现 2.1堆的向下调整算法 2.2堆的向上调整算法 2.3建堆(数组) 2.4堆排序 2.5堆排序的时间复杂度 1.堆的概念及结构 如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树(二叉树具体概念参见——二叉树详解)的顺序存储方式存储在一个一维数组中,并满足:Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0,1,2…,则称为小堆(或大

  • C语言数据结构之堆排序的优化算法

    C语言数据结构之堆排序的优化算法

    目录 1.堆排序优化算法 1.1建堆的时间复杂度 1.1.1 向下调整建堆:O(N) 1.1.2 向上调整建堆:O(N*logN) 1.2堆排序的复杂度 1.2.1原堆排序的时间复杂度 1.2.2原堆排序的空间复杂度 1.3堆排序优化算法的复杂度 1.3.1 堆排序优化算法的时间复杂度 1.3.2 堆排序优化算法的空间复杂度 1.4堆排序实现逻辑 1.5堆排序实现代码 1.6演示结果 总结 在浏览本篇博文的小伙伴可先浅看一下上篇堆和堆排序的思想: 戳这里可跳转上篇文~~ 1.堆排序优化算法 要堆

  • C语言数据结构二叉树之堆的实现和堆排序详解

    C语言数据结构二叉树之堆的实现和堆排序详解

    目录 一.本章重点 二.堆 2.1堆的介绍 2.2堆的接口实现 三.堆排序 一.本章重点 堆的介绍 堆的接口实现 堆排序 二.堆 2.1堆的介绍 一般来说,堆在物理结构上是连续的数组结构,在逻辑结构上是一颗完全二叉树. 但要满足 每个父亲节点的值都得大于孩子节点的值,这样的堆称为大堆. 每个父亲节点的值都得小于孩子节点的值,这样的堆称为小堆. 那么以下就是一个小堆. 百度百科: 堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆. 若将和此次序列对应的一维数

  • C语言数据结构之堆、堆排序的分析及实现

    C语言数据结构之堆、堆排序的分析及实现

    目录 1.堆的概念结构及分类 1.2堆的分类 1.2.1 大堆 1.2.2 小堆 2. 堆的主要接口 3.堆的实现 3.1 堆的初始化 HeapInit 3.2 堆的销毁 HeapDestory 3.3 堆的打印 HeapPrint 3.4 堆的插入元素 HeapPush   * 3.5 堆的删除元素 HeapPop  * 4.堆的应用:堆排序   *** 4.1 堆排序实现过程分析 4.3 堆排序结果演示 5.堆(小堆)的完整代码 总结  1.堆的概念结构及分类 以上这段概念描述看起来十分复杂

  • C语言数据结构之vector底层实现机制解析

    C语言数据结构之vector底层实现机制解析

    目录 一.vector底层实现机制刨析 二.vector的核心框架接口的模拟实现 1.vector的迭代器实现 2.reserve()扩容 3.尾插尾删(push_back(),pop_back()) 4.对insert()插入时迭代器失效刨析 5.对erase()数据删除时迭代器失效刨析 一.vector底层实现机制刨析 通过分析 vector 容器的源代码不难发现,它就是使用 3 个迭代器(可以理解成指针)来表示的: 其中statrt指向vector 容器对象的起始字节位置: finish指

  • C语言数据结构与算法之排序总结(二)

    C语言数据结构与算法之排序总结(二)

    目录 一.前言 二.选择类排序 1.简单选择排序 2.树形选择排序 3.堆选择排序 三.归并排序 四.分配类排序 1.多关键字排序 2.链式基数排序 五.总结归纳 一.前言 之前的排序总结(一)对插入类和交换类排序作了比较详细的总结,对于直接插入.希尔排序.冒泡排序.快速排序要求熟练掌握 这篇排序全面总结(二)主要介绍选择类排序中的简单.树形和堆排序,归并排序.分配类排序的基数排序 二.选择类排序 选择类:每次从待排序的无序序列中,选择一个最大或最小的数字,放到前面,数据元素为空时排序结束 1.

  • C语言数据结构经典10大排序算法刨析

    C语言数据结构经典10大排序算法刨析

    1.冒泡排序 // 冒泡排序 #include <stdlib.h> #include <stdio.h> // 采用两层循环实现的方法. // 参数arr是待排序数组的首地址,len是数组元素的个数. void bubblesort1(int *arr,unsigned int len) { if (len<2) return; // 数组小于2个元素不需要排序. int ii; // 排序的趟数的计数器. int jj; // 每趟排序的元素位置计数器. int itmp

  • C语言数据结构之二叉树详解

    C语言数据结构之二叉树详解

    目录 1. 树概念及结构 1.1树概念 1.2树的表示 2. 二叉树概念及结构 2.1概念 2.2数据结构中的二叉树 2.3特殊的二叉树 2.4二叉树的存储结构 2.5二叉树的性质 3. 二叉树顺序结构及概念 3.1二叉树的顺序结构 3.2堆的概念及结构 3.3堆的实现 4. 二叉树链式结构及实现 4.1二叉树链式结构的遍历 4.2二叉树的链式实现 1. 树概念及结构 1.1树概念 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵

  • Go语言数据结构之二叉树可视化详解

    Go语言数据结构之二叉树可视化详解

    目录 题目 源代码 做题思路 扩展 左右并列展示 上下并列展示 总结回顾 题目 以图形展示任意二叉树,如下图,一个中缀表达式表示的二叉树:3.14*r²*h/3 源代码 package main import ( "fmt" "io" "os" "os/exec" "strconv" "strings" ) type any = interface{} type btNode struc

随机推荐