堆的遍历与堆排序
/*最大堆问题，堆数据结构是一颗完全二叉树，用数组来完成其物理实现，逻辑上实际是一种树形结构，
r是下标，parent(r)=int((r-1)/2);
leftchild(r)=2r+1;
rightchild(r)=2r+2;*/
以下是头文件maxheap.h的内容
template
class maxheap
{
private:
Elem* heapArray;
int maxsize;
int n;//堆的大小
public:
maxheap(int size = 10){
maxsize = size;
heapArray = new Elem[maxsize];//注意为中括号
n = 0;
}
~maxheap() {delete [] heapArray;}
int heapsize() {return n;}
int parent(int pos) {
return (pos-1)/2;
}
int leftchild(int pos) {
return 2*pos+1;
}
int rightchild(int pos) {
return 2*pos+2;
}
bool insert(Elem& e);
bool remove(int pos);
bool creatHeap(int ArrLen,Elem* arr);
void preorder(int pos);
void heapSort(int arrlen);
void print();
};
template
bool maxheap
{
if(n>=maxsize-1)return false;
heapArray[n] = e;
// cout< int temp = n; Elem ha; while(parent(temp)>=0 && heapArray[parent(temp)] ha = heapArray[parent(temp)]; heapArray[parent(temp)] = heapArray[temp]; heapArray[temp] = ha; // cout< temp = parent(temp); } n +=1; return true; } template bool maxheap { int n = ArrLen; // heapArray = new Elem[ArrLen]; for(int i = 0; i insert(arr[i]); } return true; } template bool maxheap { if(pos<0 || pos>n)return false; Elem temp; temp = heapArray[pos]; heapArray[pos] = heapArray[n-1]; heapArray[n-1] = temp; n = n-1;//删除一个节点后，堆节点数减1 int j = leftchild(pos); while(j<=n-1){ if( heapArray[leftchild(pos)] < heapArray[rightchild(pos)] && rightchild(pos) <= n-1 ) j = rightchild(pos);//此时，j指向孩子中较大节点 if( heapArray[pos] >= heapArray[j] )break;//如果父节点比左右节点中较大节点大，则循环退出 temp = heapArray[j]; //父节点与较大节点交换 heapArray[j] = heapArray[pos]; heapArray[pos] = temp; pos = j; j = leftchild(pos); } return true; } template void maxheap { // cout< cout< if(leftchild(pos) if(rightchild(pos) } template void maxheap { cout<<"物理实现（数组形式）："; for(int i = 0; i { cout< } cout< cout<<"逻辑结构基于数组的完全二叉树（最大堆）；"< template void maxheap { for(int i = 0; i remove(0); } cout<<"堆排序："< for(i = 0; i cout< } } 以下是usemaxheap.cpp的内容 #include #include"maxheap.h" using namespace std; int main() { maxheap int arr[]={4,8,25,3,91,54,24,36,74,15,11,8,97,102,114,125,33}; mymaxheap1.creatHeap(17,arr); mymaxheap1.print(); cout<<"前序遍历:"< mymaxheap1.preorder(0); mymaxheap1.heapSort(17); return 0; } 以下是测试结果： 顺便说下#include 堆排序——C#实现 一算法描述 堆排序（Heap Sort）是利用一种被称作二叉堆的数据结构进行排序的排序算法。 二叉堆在内部维护一个数组，可被看成一棵近似的完全二叉树，树上每个节点对应数组中的一个元素。除最底层外，该树是满的。 二叉堆中，有两个与所维护数组相关的属性。Length表示数组的元素个数，而HeapSize则表示二叉堆中所维护的数组中的元素的个数（并不是数组中的所有元素都一定是二叉堆的有效元素）。因此，根据上述定义有： 0 = HeapSize = Length。 二叉堆可分为最大堆和最小堆两种类型。在最大堆中，二叉树上所有的节点都不大于其父节点，即 A[Parent(i)] = A[i]。最小堆正好相反：A[Parent(i)] = A[i]。 为维护一个二叉堆是最大（小）堆，我们调用一个叫做MaxHeapify （MinHeapify）的过程。以MaxHeapify，在调用MaxHeapify时，先假定根节点为Left(i)和Right(i)的二叉树都是最大堆，如果A[i]小于其子节点中元素，则交换A[i]和其子节点中的较大的元素。但这样一来，以被交换的子节点为根元素的二叉堆有可能又不满足最大堆性质，此时则递归调用MaxHeapify方法，直到所有的子级二叉堆都满足最大堆性质。如下图所示： 因为在调用MaxHeapify（MinHeapify）方法使根节点为A[i]的 二叉堆满足最大（小）堆性质时我们有其左右子堆均已满足最大（小）堆性质这个假设，所以如果我们在将一个待排序的数组构造成最大（小）堆时，需要自底向上地调用 MaxHeapify（MinHeapify）方法。 在利用最大堆进行排序时，我们先将待排序数组构造成一个最大堆，此时A[0]（根节点）则为数组中的最大元素，将A[0]与A[n - 1]交换，则把A[0]放到了最终正确的排序位置。然后通过将HeapSize 减去1，将（交换后的）最后一个元素从堆中去掉。然后通过MaxHeapify方法将余下的堆改造成最大堆，然后重复以上的交换。重复这一动作，直到堆中元素只有2个。则最终得到的数组为按照升序排列的数组。 二算法实现 1 注意到在C#中数组的起始下标为0，因此，计算一个给定下标的节点的父节点和左右子节点时应该特别小心。 private static int Parrent(int i) return (i - 1) - 2; private static int Left(int i) return 2 * i + 1; private static int Right(int i) return 2 * i + 2; 2 算法的核心部分是MaxHeapify（MinHeapify）方法，根据算法描述中的说明，一下代码分别实现了对整数数组的最大堆化和最小堆化方法，以及一个泛型版本。 数据结构课程设计设计说明书 内部堆排序算法的实现 学生姓名金少伟 学号1121024029 班级信管1101 成绩 指导教师曹阳 数学与计算机科学学院 2013年3月15日 课程设计任务书 2012—2013学年第二学期 课程设计名称：数据结构课程设计 课程设计题目：内部堆排序算法的实现 完成期限：自2013年3 月4日至2013年3 月15 日共 2 周 设计内容： 堆排序（heap sort）是直接选择排序法的改进，排序时，需要一个记录大小的辅助空间。n个关键字序列K1，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。（即如果按照线性存储该树，可得到一个不下降序列或不上升序列）。 本课程设计中主要完成以下内容： 1.设计堆排序算法并实现该算法。 2.对堆排序的时间复杂度及空间复杂度进行计算与探讨。 3.寻找改进堆排序的方法。 基本要求如下： 1.程序设计界面友好； 2.设计思想阐述清晰； 3.算法流程图正确； 4.软件测试方案合理、有效。指导教师：曹阳教研室负责人：申静 课程设计评阅 摘要 堆排序是直接选择排序法的改进。本课设以VC++6.0作为开发环境，C语言作为编程语言，编程实现了堆排序算法。程序运行正确，操作简单，易于为用户接受。 关键词：堆排序；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)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。 2、大根堆和小根堆 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。 注意： ①堆中任一子树亦是堆。 ②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。 3、堆排序特点 堆排序(HeapSort)是一树形选择排序。 堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。 4、堆排序与直接插入排序的区别 直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。 堆排序可通过树形结构保存部分比较结果，可减少比较次数。5、堆排序 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。 （1）用大根堆排序的基本思想 堆排序 堆排序是利用堆的性质进行的一种选择排序，下面先讨论一下堆。 1.堆 堆实际上是一棵完全二叉树，其任何一非叶节点满足性质： Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2] 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。 堆分为大顶堆和小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，满足Key[i]<= key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。 2.堆排序的思想 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。 其基本思想为(大顶堆)： 1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区； 2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n]; 3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。 操作过程如下： 1)初始化堆：将R[1..n]构造为堆； 2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。 因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。 下面举例说明： 给定一个整形数组a[]={16,7,3,20,17,8}，对其进行堆排序。 首先根据该数组元素构建一个完全二叉树，得到 算法与数据结构程设计报告 一．设计题目： 堆排序的算法 二．运行环境： 1、硬件：计算机 2、软件：Microsoft Visual C++6.0 三．目的和意义： 目的：创建一个大堆，按从大到小顺序输出堆元素，实现堆排序。 意义：利用堆排序，即使在最坏情况下的时间复杂度也是O(nlog2n)，相对于快速排序来说，时间复杂度小，这是堆排序的最大优点，可用于对若干元素进行排序，加快排序速度。 四．算法设计的基本思想： 堆排序算法设计基本思想： 堆排序利用了大根堆堆顶记录的关键字最大这一特征，使得在当前无序区中选取最大关键字的记录变得简单。先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区。再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录r[n]交换，由此得到新的无序区r[1..n-1]和有序区r[n]，且满足r[1..n-1].keys≤r[n].key。由于交换后新的根R[1]可能违反堆性质，故应将当前无序区r[1..n-1]调整为堆。然后再次将r[1..n-1]中关键字最大的记录r[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区r[1..n-2]和有序区r[n-1..n]，且仍满足关系r[1..n-2].keys≤r[n-1..n].keys，同样要将r[1..n-2]调整为堆。直到无序区只有一个元素为止. . . 流程图3：打印数组函数print() 六．算法设计分析： 性能分析：堆排序的时间主要由建立初始堆和不断重复建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。其中：建立初始堆时，总共需进行的关键字比较次数≤ 4n =O(n) ;排序过程中进行n-1次重建堆所进行的总比较次数不超过下式：2*(└ log2(n-1) ┘+└ log2(n-2) ┘+…+ └ log22 ┘) < 2n └ log2n ┘=O(n log2n)因此堆排序总的时间复杂度是 O(n+ n log2n)= O(n log2n)。堆排序在最坏情况下的时间复杂度也是O(nlog2n)，相对于快速排序来说，这是堆排序的最大优点。另外，堆排序仅需一个记录大小供交换用的辅助空间。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录较少的文件，但对n较大的文件还是很有效的。堆排序是就地排序，辅助空间为O(1)，它是不稳定的排序方法。 堆的描述：堆排序(HeapSort)是一树形选择排序。堆是对基于数组的树的重要应用场合之一。它是节点间具有层次次序关系的完全二叉树。其中，父节点值大于或等于其孩子节点值的，叫“最大堆（maximum heap）”;父节点值小于或等于孩子节点值的，叫“最小堆（minimum heap）”.在最大堆中，根中的元素值最大；在最小堆中，根中的元素值最小。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。 从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。 堆的存储特点：在这里，讨论作为顺序表存储的堆。它是按某种次序将一系列数据以完全二叉树形式存放的一种表。它要求堆中的节点的值都大于或等于其孩子节点的值。 按照这种存储方式，可知第i个元素的左右儿子分别是第2i和第2i+1个元素，而它的父亲节点是第i/2个元素。由于父亲节点和儿子节点具有这样的顺序关系，所以可以方便地由父亲节点找到儿子节点，反之亦然。 可见，这种存储方式大大节省了存储空间，高效快速。 堆的相关操作：作为抽象表结构，堆允许增加和删除表项。插入过程不用假定新表项占有一个特定的位置而只需维持堆顺序。但是删除操作总是删去表中的最大项（根）。堆可以用于那些客户程序想直接访问最大（小）元素的场合。作为表，堆并不提供Find操作，而对表的直接访问是只读的。所有的堆处理算法都有责任更新树和维持堆顺序。 1.建堆：数组具有对应的树表示形式。一般情况下，树并不满足堆的条件。通过重新排列元素，可以建立一棵“堆化”的树。 2.插入一个元素：新元素被加入到表中，随后树被更新以恢复堆次序。例如，下面的步骤将15加入到表中。 3.删除一个元素：删除总是发生在根节点处。用表中的最后一个元素来填补空缺位置，结果树被更新以恢复堆条件。 在堆实现时我们是采用数组来存储堆的完全二叉树表示，并且用一种有效的算法来保证对堆的所有操作不破坏堆的性质。这种表示的主要问题在于数组的大小需要事先确定，这使得对堆的大小有了一个初始的限定。在堆中数据增长到 基本思想 堆的定义： n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称堆性质)： (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤FLOOR(n/2)) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小 根堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。 用大根堆排序的基本思想： (1) 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区; (2) 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key; (3) 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 排序过程 假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，数组大小为20。 （一）初始建堆 首先执行的初始建堆（在建堆的过程中需要调整堆）。过程如下： 1、求出当前堆中最后一个存在孩子结点的索引 这里，把数组array看做是一棵完全二叉树，这样数组每个索引位置上的元素都对应到二叉树中的结点，如图所示： 其中需要在这棵树中找到最后一个有孩子最大的一个结点的索引： pos = (array.length-1)/2 = (20-1)/2 = 9 也就是索引为9的array[9] = 76，由后至前层次遍历，从array[9]一直到array[0]，对初始堆进行调整。 2、对初始堆进行调整 一、试验内容 内部排序算法效率比较平台的设计与实现 二、试验目的 问题描述：各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较几种主要的基本算法的关键字比较次数和关键字移动次数，以取得直观感受。 三、流程图 冒泡排序 否 是 否 否 开始 J=N-1 I=0 a[i]>a[i+1] a[i]与a[i+1]交换 I++ I=j J=J-1 J=0? 结束 简单选择排序 假 假 真 真 真 假 开 始 i 序 真 真 假 假 真 假 开始 i=2 i<=L.length L.r[i].key 序 假 真 真 真 假 假 真 假 开始 k=0 i<=L.length L.r[i].key 数据结构课程设计设计说明书 堆排序的算法的实现 学生姓名 学号 班级 成绩 指导教师 计算机科学与技术系 2011年3月4 日 数据结构课程设计评阅书 注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。 课程设计任务书 2010 —2011 学年第二学期 专业：学号：姓名： 课程设计名称：数据结构课程设计 设计题目：堆排序算法的实现 完成期限：自 2011年 2 月 19 日至 2011 年 3 月 4 日共 2 周 设计依据、要求及主要内容（可另加附页）： 堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。如关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆。 大根堆和小根堆：根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆(Binary Heap)， 大根堆排序的基本思想： ① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区。 ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key。 ③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 要求：（1）给出一个符合堆序列的一组数，能够建立大根堆和小根堆。 （2）界面友好，可操作性强。 （3）能够实现数据个数的变化输入，并建立相应的堆。 指导教师（签字）：教研室主任（签字）： 批准日期：年月日 数据结构实验报告 八种排序算法实验报告 一、实验容 编写关于八种排序算法的C语言程序，要求包含直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序和基数排序。 二、实验步骤 各种部排序算法的比较： 1.八种排序算法的复杂度分析（时间与空间）。 2.八种排序算法的C语言编程实现。 3.八种排序算法的比较，包括比较次数、移动次数。 三、稳定性，时间复杂度和空间复杂度分析 比较时间复杂度函数的情况： 时间复杂度函数O(n)的增长情况 所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。 时间复杂度来说： (1)平方阶(O(n2))排序 各类简单排序:直接插入、直接选择和冒泡排序； (2)线性对数阶(O(nlog2n))排序 快速排序、堆排序和归并排序； (3)O(n1+§))排序,§是介于0和1之间的常数。 希尔排序 (4)线性阶(O(n))排序 基数排序，此外还有桶、箱排序。 说明： 当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）； 而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）； 原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。 稳定性： 排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。 稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较； 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序 C语言主流的排序算法效率分析及总结 班级：计科二班作者：XXX 日期：2016-3-29 工作：算法搜集及程序组合，结论总结。 星期二同组者：刘文 工作：程序测试，时间记录以及程序演示这次我们组主要搜集了冒泡排序算法，简单排序算法，直接插入排序算法，希尔排序算法，堆排序算法，快速排序算法六种常见的排序算法，并对它们的运行效率作了一个简单的测试与分析。 A冒泡排序： 算法思想简单描述： 在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。冒泡排序是稳定的。 算法时间复杂度：O(N2) 下面我们来测试一下不同数据量的排序时间： 这是200个乱序随机数： 冒泡排序运行时间为0.000000毫秒 这是1000个乱序随机数： 冒泡排序运行时间为3.000000毫秒这是5000个乱序随机数： 冒泡排序运行时间为70.000000毫秒这是20000个乱序随机数： 冒泡排序运行时间为1464.000000毫秒 从不同数据量的纵向分析来看， 1，在冒泡排序算法里，随着数据量的增加，其运行时间也会越来越长。 2，在两百个数据的时候，其运行时间少到忽略不计，即运算瞬间完成。这说明冒泡排序在处理小数据量的时候还是很给力的 3，当处理的数据量从5000提到20000的时候，冒泡排序的运行时间发生了质的增加。从几十毫秒到几千毫秒，运行时间大大增加，从这里可见，冒泡排序在处理稍微大的数据的时候便已经显现出了力不从心感，我个人感觉已不大适用。 B 简单选择排序： 算法思想简单描述： 在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。选择排序是不稳定的。 时间复杂度：O(N2) 下面我们依然来测试一下简单选择排序在不同数据量的运行时间： 这是200个乱序随机数： 排序算法汇总（选择排序，直接插入排序，冒泡排序，希尔排序，快速排序，堆排序）2009-07-16 20:12=============================================== 作者：rerli 时间：2003-12-15 目的：重温经典排序思想，并用C语言指针实现排序算法 ================================================ */ /* ====================================================================== ======= 相关知识介绍（所有定义只为帮助读者理解相关概念，并非严格定义）： 1、稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就 说这种排序方法是稳定的。反之，就是非稳定的。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5， 则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4, a2,a3,a5就不是稳定的了。 2、内排序和外排序 在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 3、算法的时间复杂度和空间复杂度 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 ====================================================================== ========== */ /* ================================================ 功能：选择排序 输入：数组名称（也就是数组首地址）、数组中元素个数 ================================================ 实验五堆排序（四号黑体） 【一】实验目的（小四黑体） 1．实现堆的创建和堆排序； 2．理解变治法的思想。 【二】实验内容（小四黑体） 1．给定一个序列，构造大根堆并实现堆排序； 2．分析堆排序算法的时间复杂度，并与合并排序、快速排序比较。 【三】实验步骤（代码、结果）（小四黑体） 程序代码 #include 所以须要又一次调整使其成为大根堆结构*/ } } } void build_bheap(int *a, int size) /*建立大根堆*/ { int i; for(i=size/2; i >= 1; i--) /*非叶节点最大序号值为size/2*/ { heap_ajust(a, i, size); /*每一个非叶子结点都须要调用这个函数*/ } } void heap_sort(int *a, int size) /*堆排序*/ { int i; int temp; build_bheap(a, size); for(i=size; i >= 1; i--) { temp = a[1]; a[1] = a[i]; a[i] = temp; /*交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面*/ heap_ajust(a, 1, i-1); /*又一次调整堆顶节点成为大顶堆，仅仅有被交换的分支才有可能不是大根堆*/ } } int main() { printf("Z09315221谭召\n"); int a[7]={0,7,6,1,2,4,8}; int i; for(i=1;i <= 6; i++) printf("%d ", a[i]); printf("\n"); heap_sort(a, 6); for(i=1;i <= 6; i++) printf("%d ", a[i]); printf("\n");堆 排 序 算 法
内部堆排序算法的实现课程设计说明书
堆排序算法的基本思想及算法实现示例
堆排序算法分析(C语言版)
堆排序
堆排序思想
数据结构：简单选择,直接插入,快速排序,冒泡排序希尔排序,堆排序算法比较平台
堆排序算法课程设计
排序算法实验报告
排序算法效率分析及总结
排序算法汇总(选择排序_,直接插入排序,冒泡排序,希尔排序,快速排序,堆排序)
算法分析实验5堆排序