数据结构和算法

一步一步写算法之堆排序

堆排序是另外一种常用的递归排序。因为堆排序有着优秀的排序性能,所以在软件设计中也经常使用。堆排序有着属于自己的特殊性质,和二叉平衡树基本是一致的。打一个比方说,处于大堆中的每一个数据都必须满足这样一个特性: 每一个array[n] 不小于array[2*n] 每一个array[n]不小于array[2 * n + 1] 构建这样一个堆只是基础,后面我们需要每次从堆的顶部拿掉一个数据,不断调整堆,直到这个数组变成有序数组为主。所以详细的堆排序算法应该是这样的: 构建大堆,使得堆中的每一个数据都满足上面提到的性质 将堆的第一个数据和堆的最后一个数据进行互换,然后重新调整堆,直到堆重新平衡为止 重复2的过程,直到整个数组有序。 上面的描述过程很简单,那么实践操作是怎么样的呢? 对入参进行判断

数据结构和算法

一步一步写算法之合并排序

前面一篇博客提到的快速排序是排序算法中的一种经典算法。和快速排序一样,合并排序是另外一种经常使用的排序算法。那么合并排序算法有什么不同呢?关键之处就体现在这个合并上面。 合并算法的基本步骤如下所示: 把0~length-1的数组分成左数组和右数组 对左数组和右数组进行迭代排序 将左数组和右数组进行合并,那么生成的整个数组就是有序的数据数组 下面就开始实践操作: 创建函数,判断参数的合法性 void merge_sort(int array[], int length) { if(NULL == array || 0 == length) return ; _merge_sort(array, 0, length-1); } 进行merge函数迭代操作

数据结构和算法

一步一步写算法之快速排序

快速排序是编程中经常使用到的一种排序方法。可是很多朋友对快速排序有畏难情绪,认为快速排序使用到了递归,是一种非常复杂的程序,其实未必如此。只要我们使用好了方法,就可以自己实现快速排序。 首先,我们复习一下,快速排序的基本步骤是什么: 判断输入参数的合法性 把数组的第一个数据作为比较的原点,比该数据小的数据排列在左边,比该数据大的数据排列在右边 按照2的方法分别对左边的数组和右边的数据进行和2一样的数据排列 那么实际编写代码中,应该怎么做呢? 首先,判断数据的合法性? void quick_sort(int array[], int length) { int median = 0; if(NULL == array || 0

数据结构和算法

一步一步写算法之非递归排序

在上面一篇博客当中,我们发现普通查找和排序查找的性能差别很大。作为一个100万的数据,如果使用普通的查找方法,那么每一个数据查找平均下来就要几十万次,那么二分法的查找呢,20多次就可以搞定。这中间的差别是非常明显的。既然排序有这么好的效果,那么这篇博客中,我们就对排序算做一个总结。 按照我个人的理解,排序可以分为两种:一种是非递归排序,它主要按照非递归的方法对数据进行排序,也就是说主要数据的移位和循环来完成;另外一种就是递归方法,我们在排列当前数据的时候首先把子数据排列有序,然后才会排列当前的数据。这种不断递归调用的方法就是递归排序。 非递归排序的方法很多,这里主要介绍冒泡排序、插入排序、希尔排序;递归的方法也不少,这里介绍的方法是快速排序、归并排序和堆排序。排序的内容很多,本篇博客主要介绍非递归排序,递归排序的内容主要在下一节内容解决。 冒泡排序 冒泡排序的内容并不复杂。假设有n个数据需要排序,

数据结构和算法

一步一步写算法之查找

无论是数据库,还是普通的ERP系统,查找功能数据处理的一个基本功能。数据查找并不复杂,但是如何实现数据又快又好地查找呢?前人在实践中积累的一些方法,值得我们好好学些一下。我们假定查找的数据唯一存在,数组中没有重复的数据存在。 普通的数据查找 设想有一个1M的数据,我们如何在里面找到我们想要的那个数据。此时数据本身没有特征,所以我们需要的那个数据可能出现在数组的各个位置,可能在数据的开头位置,也可能在数据的结束位置。这种性质要求我们必须对数据进行遍历之后才能获取到对应的数据。 int find(int array[], int length, int value) { if(NULL == array || 0 == length) return -1; for(

数据结构和算法

一步一步写算法之内存

内存是程序运行的基础。所有正在运行的代码都保存在内存里面。内存需要处理各种各样的数据,包括键盘的数据、鼠标的数据、usb的数据、串口的数据、摄像头的数据,那么这些数据经过程序的处理之后,就要进行输出到串口、屏幕、usb等。 内存只有一个,但是程序里面的空间有很多种。但是内存中的数据类型只有几种,比如说全局中的数据、堆中的数据、临时堆栈中的数据。那么他们有什么区别呢?我们可以通过代码发现一些问题。 全局数据 static int value = 100; void process() { static int number = 10; } 大家可以在这里看到,value和number的数据其实都属于全局数据,

数据结构和算法

一步一步写算法之递归和堆栈

看过我前面博客的朋友都清楚,函数调用主要依靠ebp和esp的堆栈互动来实现的。那么递归呢,最主要的特色就是函数自己调用自己。如果一个函数调用的是自己本身,那么这个函数就是递归函数。 我们可以看一下普通函数的调用怎么样的。试想如果函数A调用了函数B,函数B又调用了函数C,那么在堆栈中的数据是怎么保存的呢? 函数A ^ 函数B | (地址递减) 函数C | 如果是递归函数呢,举一个简单的递归函数为例: int iterate(int value) { if(value == 1) return 1; return value + iterate(value -1); } 下面我们使用一个函数进行调用,看看会发生什么情况? void

数据结构和算法

一步一步写算法之循环和递归

其实编程的朋友知道,不管学什么语言,循环和递归是两个必须学习的内容。当然,如果循环还好理解一点,那么递归却没有那么简单。我们曾经对递归讳莫如深,但是我想告诉大家的是,递归其实没有那么可怕。所谓的递归就是函数自己调用自己而已,循环本质上也是一种递归。 求和递归函数 我们可以举一个循环的例子,前面我们说过,如果编写一个1到n的求和函数怎么写呢,你可能会这么写: int calculate(int m) { int count = 0; if(m <0) return -1; for(int index = 0;