十六算法

长平狐 发布于 2012/08/28 16:41
阅读 94
收藏 2

【Gopher China万字分享】华为云的Go语言云原生实战经验!>>>

 

算法

排序算法

Selection Sort

连续的容器中存放了很多的元素,我们需要对其进行排序,假设每个元素都支持

operator <运算符。

选择排序的做法是先选择第一个元素,然后和其他的n-1个元素逐一比较,找到n-1个当中最小的,并且同时小于第一个元素的,交换位置。

然后用同样的算法考虑后面的n-1n-2n-3...个元素,直到还剩下最后一个元素。

template<typename T>

void SelectionSort(T a[],size_t length)

{

assert(length>1);

size_t curPos=0,minPos,end=length;

while(curPos<length-1)

{

T& cur=a[curPos];

minPos=curPos+1;

for(size_t idx=minPos;idx<length;++idx)

{

if(cur>a[idx])

minPos=idx;

}

if(minPos!=curPos)

{

T temp=cur;

cur=a[minPos];

a[minPos]=temp;

}

curPos++;

}

}


时间复杂度为O(n⊃2;),如图:



Insertion Sort

假设当前需要排序的元素位于已经排好顺序的连续的元素之后,将该元素(先保存副本)从连续元素的末尾开始一个一个向前比较,如果找到有一个元素的值大于当前待排序的元素,待排序的元素位置上赋上该值,然后继续向前查找,直到遇到一个较小值或者遍历结束。

简单来说就是选一个元素(通常从第二个开始),假定这个元素前面的连续元素是已经排好顺序的(从小到大),找到合适的位置插入这个元素(x<cur<y)

上述操作从数组的第二个元素开始重复执行,直到最后一个元素被排序。


template<typename T>

void InsertionSort(vector<T>& v)

{

assert( (!v.empty()) && (v.size()>1) );

size_t curIdx;

size_t n=v.size();

for(curIdx=1;curIdx<n;++curIdx)

{

T cur=v[curIdx];

size_t j=curIdx;

while( (j>0) && (v[j-1]>cur) )

{

v[j]=v[j-1];

--j;

}

v[j]=cur;

}

}

时间复杂度也是O(n⊃2;)

Bubble Sort

冒泡排序是一个比喻,每次在一个子区间内迭代,相邻的元素两两比较,如果前面的比后面的大,则交换位置,通过这种方法,找到最大的一个元素(当成最大的一个气泡),该元素自然会跑到子区间的最后面(就像气泡上升到水面)。

子区间的不停的变化,开始从[0,n-1][0,n-2]... 最后到[0,1]。如果有一次子区间迭代过程中,没有发生元素交换,说明所有的元素已经排序。假设有n个元素。

template<typename T>

void BubbleSort(vector<T>& v)

{

assert( (!v.empty()) && (v.size()>1) );

size_t end=v.size();

bool swap=false;

while( end>1)

{

swap=false;

for(int i=0;i<end-1;++i)

{

if(v[i]>v[i+1])

{

T tmp;

tmp=v[i+1];

v[i+1]=v[i];

v[i]=tmp;

swap=true;

}

}

if(!swap)

return;

--end;

}

}


The bubble sort is generally considered to be the most inefficient sorting algorithm in common usage. Under best-case conditions (the list is already sorted), the bubble sort can approach a constant O(n) level of complexity. General-case is an abysmal O(n2).

While the insertion, selection, and shell sorts also have O(n2) complexities, they are significantly more efficient than the bubble sort.


Radix Sort

Heap Sort

MergeSort

QuickSort

STL Sort Function



为什么需要树?

线形数据结构(比如数组,链表)适用于按照位置访问元素。但是日常应用中也有不少需要按照某个值查找元素的情况,比如通过电话号码查找用户信息,通过商品条形码查找商品价格等。这样的需求需要关联式容器。STL的关联式容器set,map都使用了平衡二叉树的数据结构来管理数据。


树的术语

root

paren 父亲

children儿子

边 父亲->儿子

level 一个结点到root的路径长度 rootlevel0

树的深度(高度)depth(height)=最大level的值

binary tree 二叉树(二元树) 每个结点最多只有两个儿子

binary search tree 二叉搜索树 每个结点的左结点一定小于自己,右结点一定大于自己

退化树指的是每个结点只有一个儿子,等价于链表

完全二叉树满足两个条件:

1)高度为N的二叉树中,从0N-1层所有的子结点都是满的

2)第N层的结点如果不满,应该总是作为N-1层的左子结点出现

请看下面的例图:



树的特性

1)二叉树的第N层结点数目在12N次方之间。

2)假设完全二叉树的深度为d.则结点数目n大于等于2d次方,并且小于等于2d+1次方-1的差,小于2d+1次方

3)假设完全二叉树的结点数目为N,则深度k=int(log(N)),这里的取整是指去掉小数,不采用四舍五入法。


树的遍历

二叉树的遍历

先根遍历(左遍历)

先访问自身,然后访问左子树,再访问右子树。

递归版本实现代码如下:

template<typename T>

class TNode

{

public:

TNode(T const& value,TNode<T> const* left=0,TNode<T> const* right=0)

:left_(left),right_(right),value_(value)

{

}

public:

TNode<T> const* left_;

TNode<T> const* right_;

T value_;


};


template<typename T>

void preOrderIterator(TNode<T> const* p)

{

if(p!=NULL)

{

cout<<p->value_<<endl;

preOrderIterator(p->left_);

preOrderIterator(p->right_);

}

}


采用非递归的实现:

左遍历本身就是一种递归操作,很难用一个完全不同的循环性算法来替代。因此我们使用栈的数据结构来模仿递归调用。算法如下:

创建栈

把根结点压入栈

当栈不为空时,循环

弹出栈顶元素

如果该结点不为NULL

输出值

如果右结点不为NULL,把右结点压入栈

如果左结点不为NULL,把左结点压入栈



template<typename T>

void preOrderIterator2(TNode<T> const* p)

{

stack<TNode<T>const*> nodeStack;

nodeStack.push(p);

while(!nodeStack.empty())

{

TNode<T> const* node=nodeStack.top();

nodeStack.pop();

cout<<node->value_<<endl;

if(node->right_!=NULL)

nodeStack.push(node->right_);

if(node->left_!=NULL)

nodeStack.push(node->left_);

}

}

中根遍历

template<typename T>

void inOrderIterator(TNode<T> const * p)

{

if(p!=NULL)

{

inOrderIterator(p->left_);

cout<<p->value_<<endl;

inOrderIterator(p->right_);

}

}

后根遍历(右遍历)

template<typename T>

void postOrderIterator(TNode<T> const* p)

{

if(p!=NULL)

{

postOrderIterator(p->left_);

postOrderIterator(p->right_);

cout<<p->value_<<endl;

}

}



宽度优先遍历(层次遍历)

从根开始,一层层的迭代,每层总是从左到右的顺序。

template<typename T>

void levelIterator(TNode<T> const* p)

{

queue<TNode<T>const*> nodeQueue;

if(p!=NULL)

{

nodeQueue.push(p);

while(!nodeQueue.empty())

{

TNode<T> const* node=nodeQueue.front();

nodeQueue.pop();

cout<<node->value_<<endl;

if(node->left_!=NULL)

nodeQueue.push(node->left_);

if(node->right_!=NULL)

nodeQueue.push(node->right_);

}

}

}

深度优先遍历



统计叶结点的数目

我们可以使用任何一种遍历算法,只需要在遍历的时候检查一下是否是叶结点(没有儿子的结点),是则计数器加一。

template<typename T>

void preOrderCountLeaf(TNode<T> const* p,int& count)

{

if(p!=NULL)

{

if((p->left_==NULL)&&(p->right_==NULL))

{

count++;

}

preOrderCountLeaf(p->left_,count);

preOrderCountLeaf(p->right_,count);

}

}

计算树的深度

树的深度=max(左子树的深度,右子树的深度)+1,叶结点的深度=0

我们可以使用后根遍历算法来计算深度。

为了保证叶结点的深度为1,我们考虑:

叶结点深度=max(空左子树深度,空右子树深度)+1

因此,当depth函数发现自己为空时,应该认为自己的深度为-1



template<typename T>

int depth(TNode<T> const* p)

{

int d,depth1,depth2;

if(p==NULL)

return -1;

depth1=depth(p->left_);

depth2=depth(p->right_);

d=(depth1>depth2?depth1:depth2) + 1;

return d;

}



树的查找


原文链接:http://blog.csdn.net/sheismylife/article/details/1694964
加载中
返回顶部
顶部