分类存档: 数据结构与算法

排序算法:归并排序

归并排序的思路是 采用分治法,将一个大的问题拆分成若干个小问题,将一个大数组 拆为多个小数组进行排序 后再进去重组。 入下图锁示

拼合2个数组的思路:因为2个数组其实都是排过序的,只要给2个数组都设置个游标可以跟简单的进行组合。如下图所示



 

实现代码: 继续阅读 »

排序算法:插入排序

插入排序的思路为: 每一步都将一个待排序的元素插入到排好序的数组中的相应位置,知道所有元素都插入完为止。如下图所示:

代码如下:
继续阅读 »

排序算法:快速排序 QuickSort

快速排序的的基本思路是: 通过一次排序,将数组分割为   参考值(1个值)、较大(比参考值都大的一群)、较小值(比参考值度小的一群) 3部分。然后将较大的部分和较小的部分视为2个数组进行再次排序,整个排序过程使用递归进行,以此达到整个数组的排列。  如下图:

在排序过程中可以设置任意一个数组元素为参考值,但是为了遍历的方便性 可以采用头尾使代码更简单,上图r(最后一个元素)为参考值。

j指针为每次遍历的下标,i指针则标识分隔符i之前的素组则都比r小,i之后的则都比r大,
每次遍历j都和r比较,如果j < r则进行i 和j的交换然后i的指针+1 , 到最后一轮时,r和i进行交换,则形成一个结果  比 [r小的区域,  r , 比r大的区域]  依次再次对左右2个区域进行相同的处理。

代码如下…
继续阅读 »

数据结构:二叉堆(BinaryHeap)

概念
a、二叉堆是一种完全二叉树(故而可以使用数组来保存)。二叉堆有最大二叉堆(父节点值永远大于任意子节点的值)和最小二叉堆两种(父节点的值永远小鱼任意子节点的值)。
b、二叉堆父子节点之间有大小关系,兄弟节点之间没有大小顺序关系。

用数组表示为 [开始符,5,6,7,12,8,9,8,13,14,9]

1、结构

//
struct BinaryHeap
{
    int* elements;  //使用数组存储元素列表
    int capacity;  //数组的容量
    int size;   //当前的节点数
};

继续阅读 »

数据结构:平衡二叉树(AVL)

一、概念
1、是一课二叉查找树。(每个节点都是唯一的)
2、每个节点左右子节点高度差不超过1。

二叉查找树为了查找方便我们会将所有左右子节点统一设置规则左小右大,或者反之。
假定左小右大,将1-10的数字插入二叉平衡树 则结果为:

二、树的遍历

常用树的遍历顺序有3种,分别为:先序(前序)、中序、后序

上述二叉树采用三种遍历方式分别得到结果
先序:4 2 1 3 8 6 5 7 9 10
中序:1 2 3 4 5 6 7 8 9 10 (可以看出平衡二叉树 中序遍历就是一个排好顺的结果)
后序: 1 3 2 5 7 6 10 9 8 4

三、结构
继续阅读 »