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

算法思想简单描述：

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。

由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。

初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

堆排序是不稳定的。算法时间复杂度O(nlog2n)。

void sift(int *x, int n, int s){
  int t, k, j;
  t = *(x+s);
  k = s;
  j = 2*k + 1;

  while (j{
    if (j< *(x+j+1)) && *(x+j) /> {  //判断是否满足堆的条件：满足就继续下一轮比较，否则调整。
      j++;
    }
    if (t<*(x+j)){
      *(x+k) = *(x+j);
      k = j;
      j = 2*k + 1;
    }else{
      break;
    }
  }
  *(x+k) = t;
}

void heap_sort(int *x, int n){
  int i, k, t;
  int *p;
  for (i=n/2-1; i>=0; i--){
    sift(x,n,i);
  }
  for (k=n-1; k>=1; k--){
    t = *(x+0);
    *(x+0) = *(x+k);
    *(x+k) = t;
    sift(x,k,0);
  }
}

void main(){
  #define MAX 4
  int *p, i, a[MAX];

  p = a;
  printf("Input %d number for sorting :\n",MAX);
  for (i=0; i<MAX; i++){
    scanf("%d",p++);
  }
  printf("\n");

  p = a;
  select_sort(p,MAX);
  for (p=a, i=0; i++){
    printf("%d ",*p++);
  }
  printf("\n");
  system("pause");
}
赞 (0)

相关推荐

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

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

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

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

  • 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语言对堆排序一个算法思路和实现代码

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

  • 深入解析堆排序的算法思想及Java代码的实现演示

    深入解析堆排序的算法思想及Java代码的实现演示

    一.基础知识 我们通常所说的堆是指二叉堆,二叉堆又称完全二叉树或者叫近似完全二叉树.二叉堆又分为最大堆和最小堆. 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法,它是选择排序的一种.可以利用数组的特点快速定位指定索引的元素.数组可以根据索引直接获取元素,时间复杂度为O(1),也就是常量,因此对于取值效率极高. 最大堆的特性如下: 父结点的键值总是大于或者等于任何一个子节点的键值 每个结点的左子树和右子树都是一个最大堆 最小堆的特性如下: 父结点的键值总是小于或者等于任何一个

  • C语言实现各种排序算法实例代码(选择,冒泡,插入,归并,希尔,快排,堆排序,计数)

    C语言实现各种排序算法实例代码(选择,冒泡,插入,归并,希尔,快排,堆排序,计数)

    目录 前言 选择排序 冒泡排序 插入排序 归并排序 希尔排序 快速排序 堆排序 计数排序 总结 前言 平时用惯了高级语言高级工具高级算法,难免对一些基础算法感到生疏.但最基础的排序算法中实则蕴含着相当丰富的优化思维,熟练运用可起到举一反三之功效. 选择排序 选择排序几乎是最无脑的一种排序算法,通过遍历一次数组,选出其中最大(小)的值放在新数组的第一位:再从数组中剩下的数里选出最大(小)的,放到第二位,依次类推. 算法步骤 设数组有n个元素,{ a 0 , a 1 , - , a n } 从数组第

  • 基于Go和PHP语言实现爬楼梯算法的思路详解

    爬楼梯(Climbing-Stairs) 题干: 假设你正在爬楼梯.需要 n 阶你才能到达楼顶.每次你可以爬 1 或 2 个台阶.你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数.示例 1:  输入: 2  输出: 2  解释: 有两种方法可以爬到楼顶.  1. 1 阶 + 1 阶  2. 2 阶示例 2:  输入: 3  输出: 3  解释: 有三种方法可以爬到楼顶.  1. 1 阶 + 1 阶 + 1 阶  2. 1 阶 + 2 阶  3. 2 阶 + 1 阶来源:力扣 这题

  • java语言实现权重随机算法完整实例

    java语言实现权重随机算法完整实例

    前言 现在app就是雨后春笋,嗖嗖的往外冒啊,有经验的.没经验的.有资历的.没资历的都想着创业,创业的90%以上都要做一个app出来,好像成了创业的标配. 做了app就得推广啊,怎么推,发券送钱是最多用的被不可少的了,现在好多产品或者运营都要求能够随机出优惠券的金额,但是呢又不能过于随机,送出去的券都是钱吗,投资人的钱,是吧. 所以,在随机生成的金额中就要求,小额度的几率要大,大额度的几率要小,比如说3元的70%,5块的25%,10块的5%,这个样子的概率去生成优惠券,这个怎么办呢? 对于上述的

  • Go语言实现常用排序算法的示例代码

    Go语言实现常用排序算法的示例代码

    目录 冒泡排序 快速排序 选择排序 插入排序 排序算法是在生活中随处可见,也是算法基础,因为其实现代码较短,应用较常见.所以在面试中经常会问到排序算法及其相关的问题,可以说是每个程序员都必须得掌握的了.为了方便大家学习,花了一天的时间用Go语言实现一下常用的算法且整理了一下,如有需要可以参考. 冒泡排序 思路:从前往后对相邻的两个元素依次进行比较,让较大的数往下沉,较小的网上冒,即每当两个相邻的元素比较后发现他们的排序要求相反时,就将它们互换. 时间复杂度:O(N^2) 空间复杂度:O(1) f

  • C语言杨氏矩阵查找算法实例讲解

    目录 一.杨氏矩阵介绍 二.查找算法 1.查找思路 2.步骤 3.代码 三.杨氏矩阵例题 代码 特别注意 四.总结 本文以C语言实现,介绍杨氏矩阵中通用的查找算法. 一.杨氏矩阵介绍 杨氏矩阵种,每一行的数都从左到右递增,每一列的数都从上到下递增.如下图是一个简单的杨氏矩阵: 有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在. 要求:时间复杂度小于O(N) 二.查找算法 1.查找思路 杨氏矩阵是很有特点的,它有规律递增的特点决定了针对

  • 基于Go语言实现选择排序算法及优化

    目录 选择排序 图片演示 普通算法 优化算法 小结 选择排序 选择排序是一种简单的比较排序算法,它的算法思路是首先从数组中寻找最小(大)的元素,然后放到数组中的第一位,接下来继续从未排序的元素中寻找最小(大)元素,然后放到已排序元素的末尾,依次类推,直到所有元素被排序. 图片演示 普通算法 import "fmt" func main() { nums := [8]int{8, 2, 3, 1, 6, 5, 7, 4} fmt.Println("原数组:", num

  • C语言实现输入一个字符串后打印出该字符串中字符的所有排列

    本文实例讲述了C语言实现输入一个字符串后打印出该字符串中字符的所有排列的方法,属于数学里的排列问题.是一个很实用的算法技巧.分享给大家供大家参考.具体实现方法如下: 例如输入字符串abc,则输出由字符a.b.c所能排列出来的所有字符串abc.acb.bac.bca.cab和cba. C语言实现代码如下: /* * Copyright (c) 2011 alexingcool. All Rights Reserved. */ #include <iostream> #include <al

随机推荐