My Blogs
Posts tagged with "C语言"
归并排序(C语言描述)
Published 2009年10月10日 16:52 by james
归并排序是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序算法以O（nlogn）最坏情形运行时间运行，而所使用的比较次数几乎是最优的。但它的一个显著问题就是需要额外的存储空间来辅助排序，空间复杂度是O(n)的，与quicksort和heapsort相比就逊色了不少，不过也可以实现空间复杂度为O（1）的归并排序，这将增加比较操作和交换操作的次数。归并排序可以使用在外部排序上：一般两路的外部排序是从源文件里读出内存大小的一块，然后在内存中排序，在放回文件里，这样生成若干文件。然后在从其中两个文件中读数据，按照merge的方式写到另一个文件中去。这一步根本用不到辅助空间。唯一可能用到辅助空间的地方是前面的一步，即将一块数据在内存中排序。
归并操作
归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。
归并操作的工作原理如下：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
归并排序
归并排序具体工作原理如下（假设序列共有n个元素）:
- 将序列每相邻两个数字进行归并操作（merge），形成floor(n / 2)个序列，排序后每个序列包含两个元素
- 将上述序列再次归并，形成floor(n / 4)个序列，每个序列包含四个元素
- 重复步骤2，直到所有元素排序完毕
算法演示1 （非递归版本）:
#include<stdio.h>
#include<stdlib.h>
void merge( …堆排序(C语言描述)
Published 2009年09月09日 17:15 by james
1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd)和威廉姆斯(J．Williams)在1964年共同发明了著名的堆排序算法(Heap Sort)。 n个关键字序列Kl，K2，…，Kn称为(Heap)，当且仅当该序列满足如下性质(简称为堆性质)：
(1) Ki <= K2i且Ki <= K2i+1 或
(2) Ki >= K2i且KI >= K2i+1 (1≤i≤ n)
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
大根堆和小根堆的根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆,又称最小堆. 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆又称最大堆. 注意： ①堆中任一子树亦是堆. ②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。
堆排序(HeapSort)是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构)，在当前无序区中选择关键字最大(或最小)的记录。
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
实现一个数从小到大排序，既可以使用大根堆，也可以使用小根堆。 …
定义返回函数指针的函数
Published 2008年08月08日 17:15 by james
基础知识：
定义函数指针：
return_type (*func_pointer)(parameter_list)
定义返回函数指针的函数：
return_type(*function(func_parameter_list))(parameter_list)
定义了一个函数function，该函数的参数列表是(function_patameter_list)，返回类型是一个函数指针，这个函数指针的原型是return_type(*)(parameter_list)。
经典例子
signal函数原型
Linux 2.0之前版本 …