C++堆排序算法实例详解
本文实例讲述了C++堆排序算法。分享给大家供大家参考，具体如下：
堆中元素的排列方式分为两种：max-heap或min-heap,前者每个节点的key都大于等于孩子节点的key，后者每个节点的key都小于等于孩子节点的key。
由于堆可以看成一个完全二叉树，可以使用连续空间的array来模拟完全二叉树，简单原始的实现如下：
#include<iostream>
int heapsize=0;//全局变量记录堆的大小
void heapSort(int array[],int n){
void buildHeap(int [],int);
void exchange(int[],int,int);
void heapify(int[],int);
buildHeap(array,n);
for(int i=n-1;i>=1;i--){
exchange(array,0,i);
heapsize--;
heapify(array,0);
}
}
//构建堆
void buildHeap(int array[],int n){
void heapify(int[],int);
heapsize=n;
//从最小的父节点开始，进行堆化，直到树根节点
for(int i=heapsize/2-1;i>=0;i--){
heapify(array,i);
}
}
//堆化
void heapify(int array[],int n){
void exchange(int[],int,int);
int left_child=n*2+1;
int right_child=n*2+2;
int largest;
if(left_child<heapsize&&array[left_child]>array[n]){
largest = left_child;
}
else{
largest = n;
}
if(right_child<heapsize&&array[right_child]>array[largest]){
largest=right_child;
}
if(largest!=n){
exchange(array,largest,n);
heapify(array,largest);
}
}
void exchange(int array[],int i,int j){
int tmp = array[i];
array[i]=array[j];
array[j]=tmp;
}
int main(){
int arr[9]={3,1,6,9,8,2,4,7,5};
heapSort(arr,9);
for(int i=0;i<9;++i){
std::cout<<arr[i]<<" ";
}
std::cout<<std::endl;
return 0;
}
STL中实现了max-heap的操作。在使用heap算法是需添加头文件algorithm。
#include <iostream>
#include<vector>
#include<algorithm>
int main()
{
int arr[9]={0,1,2,3,4,8,9,3,5};
std::vector<int> vec(arr,arr+9);
//0 1 2 3 4 8 9 3 5
for(auto c:vec){
std::cout<<c<<" ";
}
std::cout<<std::endl;
make_heap(vec.begin(),vec.end());
//9 5 8 3 4 0 2 3 1
for(auto c:vec){
std::cout<<c<<" ";
}
std::cout<<std::endl;
vec.push_back(7);
push_heap(vec.begin(),vec.end());
//9 7 8 3 5 0 2 3 1 4
for(auto c:vec){
std::cout<<c<<" ";
}
std::cout<<std::endl;
pop_heap(vec.begin(),vec.end());
//8 7 4 3 5 0 2 3 1 9,只是将最大值挪到了vector的最后，并没有删除
for(auto c:vec){
std::cout<<c<<" ";
}
std::cout<<std::endl;
std::cout<<vec.back()<<std::endl;//9
//将9删除
vec.pop_back();
//连续的pop_heap操作，每次的最大值都放在最尾端，最后呈现递增排序
sort_heap(vec.begin(),vec.end());
//0 1 2 3 3 4 5 7 8
for(auto c:vec){
std::cout<<c<<" ";
}
std::cout<<std::endl;
return 0;
}
希望本文所述对大家C++程序设计有所帮助。
相关推荐
-
C++归并排序算法实例
归并排序 归并排序算法是采用分治法的一个非常典型的应用.归并排序的思想是将一个数组中的数都分成单个的:对于单独的一个数,它肯定是有序的,然后,我们将这些有序的单个数在合并起来,组成一个有序的数列.这就是归并排序的思想.它的时间复杂度为O(N*logN). 代码实现 复制代码 代码如下: #include <iostream> using namespace std; //将有二个有序数列a[first...mid]和a[mid...last]合并. void mergearray(int
-
C++选择排序算法实例
选择排序 选择排序是一种简单直观的排序算法,它的工作原理如下.首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 选择排序的主要优点与数据移动有关.如果某个元素位于正确的最终位置上,则它不会被移动.选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换.在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常
-
C++ 数据结构 堆排序的实现
堆排序(heapsort)是一种比较快速的排序方式,它的时间复杂度为O(nlgn),并且堆排序具有空间原址性,任何时候只需要有限的空间来存储临时数据.我将用c++实现一个堆来简单分析一下. 堆排序的基本思想为: 1.升序排列,保持大堆:降序排列,保持小堆: 2.建立堆之后,将堆顶数据与堆中最后一个数据交换,堆大小减一,然后向下调整:直到堆中只剩下一个有效值: 下面我将简单分析一下: 第一步建立堆: 1.我用vector顺序表表示数组: 2.用仿函数实现大小堆随时切换,实现代码复用: 3.实现向下
-
C++实现各种排序算法类汇总
C++可实现各种排序算法类,比如直接插入排序.折半插入排序.Shell排序.归并排序.简单选择排序.基数排序.对data数组中的元素进行希尔排序.冒泡排序.递归实现.堆排序.用数组实现的基数排序等. 具体代码如下: #ifndef SORT_H #define SORT_H #include <iostream> #include <queue> using namespace std; // 1.直接插入排序 template<class ElemType> void
-
C++堆排序算法的实现方法
本文实例讲述了C++实现堆排序算法的方法,相信对于大家学习数据结构与算法会起到一定的帮助作用.具体内容如下: 首先,由于堆排序算法说起来比较长,所以在这里单独讲一下.堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素. 一.堆的定义 堆的定义如下:n个关键字序列L[n]成为堆,当且仅当该序列满足: ①L(i) <= L(2i)且L(i) <= L(2
-
解读堆排序算法及用C++实现基于最大堆的堆排序示例
1.堆排序定义 n个关键字序列Kl,K2,-,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质): (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ ) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字. [例]关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1
-
C++冒泡排序算法实例
冒泡排序 大学学习数据结构与算法最开始的时候,就讲了冒泡排序:可见这个排序算法是多么的经典.冒泡排序是一种非常简单的排序算法,它重复地走访过要排序的数列,每一次比较两个数,按照升序或降序的规则,对比较的两个数进行交换.比如现在我要对以下数据进行排序: 10 3 8 0 6 9 2 当使用冒泡排序进行升序排序时,排序的步骤是这样的: 3 10 8 0 6 9 2 // 10和3进行对比,10>3,交换位置 3 8 10 0 6 9 2 // 10再和8进行对比,10>8,交换位置 3 8 0
-
C++中十种内部排序算法的比较分析
C++中十种内部排序算法的比较分析 #include<iostream> #include<ctime> #include<fstream> using namespace std; #define MAXSIZE 1000 //可排序表的最大长度 #define SORTNUM 10 //测试10中排序方法 #define max 100 //基数排序时数据的最大位数不超过百位: typedef struct node { int data3; int next; }
-
C++插入排序算法实例
插入排序 没事喜欢看看数据结构和算法,增加自己对数据结构和算法的认识,同时也增加自己的编程基本功.插入排序是排序中比较常见的一种,理解起来非常简单.现在比如有以下数据需要进行排序: 10 3 8 0 6 9 2 当使用插入排序进行升序排序时,排序的步骤是这样的: 10 3 8 0 6 9 2 // 取元素3,去和10进行对比 3 10 8 0 6 9 2 // 由于10比3大,将10向后移动,将3放置在原来10的位置:再取8与前一个元素10进行对比 3 8 10 0 6 9 2 // 同理移动1
-
Java 归并排序算法、堆排序算法实例详解
基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]较小的存入辅助数组
-
C++堆排序算法实例详解
本文实例讲述了C++堆排序算法.分享给大家供大家参考,具体如下: 堆中元素的排列方式分为两种:max-heap或min-heap,前者每个节点的key都大于等于孩子节点的key,后者每个节点的key都小于等于孩子节点的key. 由于堆可以看成一个完全二叉树,可以使用连续空间的array来模拟完全二叉树,简单原始的实现如下: #include<iostream> int heapsize=0;//全局变量记录堆的大小 void heapSort(int array[],int n){ void
-
java 中模式匹配算法-KMP算法实例详解
java 中模式匹配算法-KMP算法实例详解 朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的
-
JavaScript算法系列之快速排序（Quicksort）算法实例详解
"快速排序"的思想很简单,整个排序过程只需要三步: (1)在数据集之中,选择一个元素作为"基准"(pivot). (2)所有小于"基准"的元素,都移到"基准"的左边:所有大于"基准"的元素,都移到"基准"的右边. (3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止. 举例来说,现在有一个数据集{85, 24, 63, 45,
-
Java 选择排序、插入排序、希尔算法实例详解
1.基本思想: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换:然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止. 2.实例 3.算法实现 /** * 选择排序算法 * 在未排序序列中找到最小元素,存放到排序序列的起始位置 * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾. * 以此类推,直到所有元素均排序完毕. * @param numbers */ public static void selectSort(int[] nu
-
KMP 算法实例详解
KMP 算法实例详解 KMP算法,是由Knuth,Morris,Pratt共同提出的模式匹配算法,其对于任何模式和目标序列,都可以在线性时间内完成匹配查找,而不会发生退化,是一个非常优秀的模式匹配算法. 分析:KMP模板题.KMP的关键是求出next的值.先预处理出next的值.然后一遍扫过.复杂度O(m+n) 实例代码: #include<stdio.h> #include<string.h> #define N 1000005 int s[N]; int p[N]; int n
-
KnockoutJS数组比较算法实例详解
这篇文章主要介绍了KnockoutJS数组比较算法实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 前端开发中,数组是一种非常有用的数据结构.这篇博客会解释并分析KnockoutJS实现中使用的数据比较算法. 算法的目的 KnockoutJS使用MVVM的思想,view model中的数组元素会对应data model中的数组数据,当用户进行输入或者请求后台时,数组数据会发生变更, 从而带动UI的更新.例如购物车类的页面,用户可以通过点击
-
python动态规划算法实例详解
如果大家对这个生僻的术语不理解的话,那就先听小编给大家说个现实生活中的实际案例吧,虽然现在手机是相当的便捷,还可以付款,但是最初的时候,我们经常会使用硬币,其中,我们如果遇到手中有很多五毛或者1块钱硬币,要怎么凑出来5元钱呢?这么一个过程也可以称之为动态规划算法,下面就来看下详细内容吧. 从斐波那契数列看动态规划 斐波那契数列:Fn = Fn-1 + Fn-2 ( n = 1,2 fib(1) = fib(2) = 1) 练习:使用递归和非递归的方法来求解斐波那契数列的第 n 项 代码如下: #
-
LRU LFU TinyLFU缓存算法实例详解
目录 简介 一.LRU和LFU算法 LRU算法 LFU算法 小结: 二.TinyLFU 三.Window-TinyLFU 简介 前置知识 知道什么是缓存 听完本节公开课,你可以收获 掌握朴素LRU.LFU算法的思想以及源码 掌握一种流式计数的算法 Count-Min Sketch 手撕TinyLFU算法.分析Window-TinyLFU源码 一.LRU和LFU算法 LRU算法 LRU Least Recently Used 最近最少使用算法 LRU 算法的思想是如果一个数据在最近一段时间没有被访
-
Python决策树和随机森林算法实例详解
本文实例讲述了Python决策树和随机森林算法.分享给大家供大家参考,具体如下: 决策树和随机森林都是常用的分类算法,它们的判断逻辑和人的思维方式非常类似,人们常常在遇到多个条件组合问题的时候,也通常可以画出一颗决策树来帮助决策判断.本文简要介绍了决策树和随机森林的算法以及实现,并使用随机森林算法和决策树算法来检测FTP暴力破解和POP3暴力破解,详细代码可以参考: https://github.com/traviszeng/MLWithWebSecurity 决策树算法 决策树表现了对象属性和