加载中……

Category: 算法

3 篇文章

C/C++实现归并排序
归并排序 归并排序和快速排序有类似之处,同样采用分治法,不同的是,归并排序不选取基准值,采用递归方式直接将数据分为两个区间,再进行排序合并。需要注意的是,排序实际是从最小单位,即分区大小为1时开始的。 时间复杂度 因为都是从中间划分区间,且无基准值。归并排序时间复杂度较稳定 O(nlogn) 步骤 对半划分区间 递归,直到分区大小为1 依次合并区间…
C/C++实现快速排序
提出 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序,它有一种比较重要的思想——分治思想。大致可以描述为,确保一组序列中存在一个特别的数据,其左边的数据都比他大(小),右边的数据都比它小(大),那么可以将这个数作为基准数,在其左边和右边分别再次确保一个数满足同等关系,直到区间大小为1,则排序完成。 时间复杂度 O(N*logN)…
C/C++实现堆排序
堆 在介绍堆前需要引入一个二叉树的概念 完全二叉树:若二叉树有k层,除第k层外,1-(k-1)层均达到最大值,则称为完全二叉树。 满二叉树:节点数n与层数k满足n=2^k-1关系的二叉树。 满二叉树一定是完全二叉树。 堆:满足父节点总是大于等于两个子节点或父节点总是小于等于两个子节点的完全二叉树,则称为堆。即节点值y1,y2,y3,yi...yn始…