`
chiyx
  • 浏览: 274697 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

常用排序算法的实现(C语言版)-堆排序

阅读更多
堆排序:
/**
*排序过程中使用到的堆的结构
*/
typedef struct heap {
	int heapSize;
	int *ap;
	int apLength;
} Heap;

/*
*调整i位置上的元素,以保持最大堆的性质
*/
void maxHeapify(int a[], int i, int hSize) {
	int l, r, largest;
	l = 2 * i + 1;
	r = l + 1;

	if (l < hSize && a[l] > a[i]) {
		largest = l;
	} else {
		largest = i;
	}

	if (r < hSize && a[r] > a[largest]) {
		largest = r;
	}

	if (largest != i) {
		swap(a, i, largest);
		maxHeapify(a, largest, hSize);
	}
}

/*
*构建最大堆
*/
Heap buildMaxHeap(int a[], int n) {
	Heap hp;
	int i;

	hp.ap = a;
	hp.heapSize = n;
	hp.apLength = n;

	for (i = n / 2 - 1; i >= 0; i--) {
		maxHeapify(a, i, n);
	}
	return hp;
}

/*
*堆排序算法
*/
void heapSort(int a[], int n) {
	int i;
	//build max-heap
	Heap heap = buildMaxHeap(a, n);

	for (i = n - 1; i > 0 ; i--) {
		swap(a, i , 0);
		heap.heapSize--;
		maxHeapify(a, 0, heap.heapSize);
	}

}
1
0
分享到:
评论

相关推荐

    几种常用排序算法的C语言实现

    一些常用排序算法的C语言实现,包括直接选择排序,希尔排序,直接插入排序,快速排序,归并排序,冒泡排序,堆排序

    各种常用排序算法的C语言实现

    本资源提供了各种常用排序算法的C语言实现,源自严蔚敏的经典教材《数据结构》。下面将详细介绍这些排序算法及其在C语言中的实现原理。 1. 冒泡排序(Bubble Sort) 冒泡排序是最基础的排序方法,通过不断交换相邻...

    c语言常用算法-----列举C语言各种常用算法

    例如,CH16可能涵盖了更高级的排序算法,如堆排序和快速排序;CH2可能涉及基础的数据结构,如数组和指针;CH13可能是关于字符串处理和模式匹配的;CH20可能讲解了图论和图的遍历方法。通过深入学习每个章节,可以...

    常用排序算法C语言实现

    本资源"常用排序算法C语言实现"提供了一个实践平台,帮助学习者将理论知识转化为实际代码。 首先,让我们探讨几种常见的排序算法及其C语言实现: 1. **冒泡排序(Bubble Sort)**:冒泡排序是最基础的排序方法,...

    用C语言实现常用排序算法

    本项目旨在实现并比较六种经典的排序算法——直接插入排序、折半插入排序、起泡排序、简单选择排序、堆排序以及2-路归并排序,使用C语言编程。为了全面评估这些算法,我们将在一组随机生成的30000个整数上运行它们,...

    常用排序算法C语言实现.zip

    本压缩包“常用排序算法C语言实现.zip”包含了多种经典的排序算法用C语言编写的源代码,这对于我们理解和实践这些算法非常有帮助。下面将详细解释其中可能包含的一些常见排序算法。 1. 冒泡排序(Bubble Sort) ...

    C++实现常用排序算法(快速,归并,选择,谢尔,堆排序)

    本文将深入探讨五种常用的排序算法:快速排序、归并排序、选择排序、谢尔排序和堆排序。 **快速排序** 是由C.A.R. Hoare在1960年提出的,是一种效率较高的分治策略。其基本思想是通过一趟排序将待排序的数据分割成...

    浅析基于C语言的常用排序算法比较.pdf

    插入排序算法同样是基于C语言的一种常用排序算法。插入排序的基本思想是:把待排序的序列分为已排序和未排序两部分,每次将一个未排序的元素,按照其大小插入到已排序序列中的适当位置,直到所有元素都被插入。插入...

    常用排序算法C语言示例代码解说PDF

    个人原创总结的常用排序算法C语言示例代码解说PDF,可以动态输出排序过程,以便理解排序算法的主旨思想。包含有直接插入排序,折半插入排序,2路直接插入排序,起泡排序,简单选择排序,快速排序,堆排序,(希尔排序,归并...

    C语言应用-C语言算法集

    C语言中常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。每种排序算法都有其特点和适用场景,例如冒泡排序和选择排序简单但效率较低,快速排序和归并排序则在平均情况下有较高的性能...

    直接插入排序算法:C语言实现直接插入排序算法

    直接插入排序是一种基础且常用的排序算法,其工作原理可以形象地比喻为打扑克牌时将新拿到的牌插入到已排序好的牌堆中的过程。在计算机科学中,这个过程通过编程语言来实现,C语言是其中一种常用的语言,以其简洁...

    c语言经典排序算法(8种-含源代码)

    希尔排序(Shell Sort)是一...以上这些排序算法是C语言中常见的经典排序算法,它们各有优缺点和适用场景,适用于不同规模和不同性质的数据集。在实际应用中,要根据具体情况选择合适的排序算法以达到最优的性能表现。

    内部排序算法比较,C语言

    要求对以下6种常用的内部排序算法进行比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。待排序表的表长不小于1000;其中的数据要用伪随机数产生程序产生,至少要用5组不同的输入数据作比较...

    常用算法(C语言源代码)

    《C语言实现的常用算法详解》 在编程领域,算法是解决问题的核心,是软件的灵魂。C语言以其简洁高效的特点,成为实现算法的理想选择。本文将深入探讨标题为“常用算法(C语言源代码)”的资源包中所包含的算法,并...

    (完整word版)十大经典排序算法-C语言.pdf

    这两种排序算法在实际应用中并不常用,因为有更高效的算法如快速排序、归并排序和堆排序等。然而,学习这些基本排序算法有助于理解排序原理,为理解和优化更复杂的算法奠定基础。 在C语言中实现这些排序算法,通常...

    8大常用排序算法实现

    本文将详细解析八大常用排序算法的实现,帮助你更好地理解和测试这些算法。 1. 冒泡排序(Bubble Sort): 冒泡排序是一种简单的交换排序,通过不断比较相邻元素并交换,使得每次遍历都将最大(或最小)的元素“冒...

    常用算法程序集(C语言描述)第三版源代码

    《常用算法程序集(C语言描述)第三版源代码》是一个专门为C语言学习者和开发者提供的资源,包含了大量的经典算法实现。这个集合旨在帮助程序员深入理解各种基础和高级算法,提高编程技能,以及解决实际问题的能力。...

    常用算法的C语言实现.zip

    "常用算法的C语言实现.zip"这个压缩包文件很可能是包含了一些经典算法的C语言代码实现,这对于学习算法和深入理解C语言的开发者来说是非常有价值的资源。 算法是计算机科学的基础,它是一系列解决问题或执行任务的...

    C语言-常用经典算法及讲解

    1. **排序算法**:排序是数据处理的基础,常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。这些算法各有优缺点,学习者需要理解它们的工作原理,并能用C语言实现。 2. **查找算法**...

    常用C语言排序算法试验

    本资源“常用C语言排序算法试验”聚焦于C语言实现的各种常见排序算法,是提升编程技能和理解算法原理的重要实践。 排序算法是计算机科学中的基础组成部分,它在数据处理、数据库管理和许多其他应用中起着关键作用。...

Global site tag (gtag.js) - Google Analytics