Data Structures

introduction:

目录
chapter1 C++回顾
chapter2 程序性能分析
chapter3 渐近记法
chapter4 性能测量
chapter5 线性表——数组描述
chapter6 线性表——链式描述
chapter7 数组和矩阵
chapter8 栈
chapter9 队列
chapter10 跳表和散列
chapter11 二叉树和其他树
chapter12 优先级队列
chapter14 搜索树
chapter15 平衡搜索树
chapter16 图
chapter17 贪婪算法
chapter18 分而治之
chapter19 动态规划

选择排序，及时终止的选择排序

冒泡排序，及时终止的冒泡排序

名次排序

原地重排

插入排序

箱子排序

基数排序

堆排序

归并排序

chapter1 C++回顾

递归函数f：自己调用自己。直接递归，f包含了调用f的语句。间接递归，f调用了g，g调用了h，..，又调用了f。

递归函数 = 基础部分 + 递归部分。

斐波那契数列：F0=0，F1=1，Fn=F(n-1)+F(n-2)。

标准模板库STL：

chapter2 程序性能分析

程序性能：运行这个程序所需要的内存和时间的多少。性能分析时采用分析方法，性能测量时采用实验方法。

空间复杂度：该程序的运行所需内存的大小。组成：指令空间，数据空间，环境栈空间。一个程序所需空间=固定部分+可变部分=c+Sp。集中计算Sp。

时间复杂度：编译时间，运行时间。主要关注运行时间。方法：（1）找出一个或多个关键操作，确定它们的执行时间（操作计数）。（2）确定程序总的步数。

操作计数：选择一种或多种关键操作（+×），确定每一种操作的执行次数。

步数：一个语法或语义上的程序片段，该片段执行时间独立于实例特征。

chapter3 渐近记法

大O记法：p(n)，q(n)两个非负函数，称p(n)渐近地大于q(n)，当且仅当lim q(n)/p(n)=0；称q(n)渐近地小于p(n)，当且仅当p(n)渐近地大于q(n)。称p(n)渐近地等于q(n)，当且仅当任何一个都不是渐近地大于另一个。

大O记法：f(n)=O(g(n))，当且仅当存在常数c>0和n0，使得对于所有的n>=n0，有f(n)<=cg(n)。g(n)是f(n)的上界。

渐近记法Ω：f(n)=Ω(g(n))表示f(n)渐近大于或等于g(n)。f(n)=Ω(g(n))当且仅当存在常数c>0和n0，使得对所有的n>=n0，有f(n)>=cg(n)。g(n)是f(n)的下界。

θ记法：f(n)=θ(g(n))，当且仅当存在常数c1>0，c2>0和n0，使得对于所有的n>=n0，有c1g(n)<=f(n)<=c2g(n)。用来表示f的上限和下限都是一个函数的情况。

小o记法：f(n)=o(g(n))，当且仅当f(n)=Og(n)且f(n)≠Ω(g(n))

chapter4 性能测量

chapter5 线性表——数组描述

数据对象：一组实例或值（原子或复合）

数据结构：一个数据对象，同时这个对象的实例以及构成实例的元素都存在着联系，而且这些联系有相关的函数来规定。

线性表：linear list，有序表，每一个实例的形式为(e0,e1,..,en-1)，ei是元素，i是索引，n是长度或大小。

数组描述/公式化描述/顺序存储：

（1）位置映射：location(i)=i；从后往前：location(i)=arrayLength-i-1；环绕：location(i)=(location(0)+i)%arrayLength；

（2）变长一维数组：一个新长度的数组，把原数组的元素复制到新数组，最后改变原数组的值。

（3）arrayList：

1
2
3
4
checkIndex(int theIndex)
    //检查索引不越界
    if(theIndex<0 || theIndex>=listSize)
        throw illeagalIndex(..);
1
2
3
4
get(int theIndex)
    //返回索引为theIndex的元素
    checkIndex(theIndex);
	return element[theIndex];
1
2
3
4
5
6
7
indexOf(const T& theElement)
    //返回元素theElement第一次出现的索引
    int theIndex = (int) (find(element, element+listSize, theElement) - element);
	if(theIndex == listSize)
        return -1
    else
        return theIndex;
1
2
3
4
5
earse(int theIndex)
    //删除索引为theIndex的元素
    checkIndex(theIndex);
	copy(element+theIndex+1, element+listSize, element+theIndex);
	elemnt[--listSize].~T();
1
2
3
4
5
6
7
8
9
insert(int theIndex, const T& theElement)
    //在索引theIndex处插入元素theElement
    check(theIndex);
	if(listSize == arrayLength)
        changeLength1D(element, arrayLenghth, 2*arrayLength);
		arrayLength *= 2;
	copy_backward(element+theIndex, element+listSize, element+listSize+1)；//向右移动一个
    element[theIndex] = theElement;
	listSize++;

（4）迭代器

1
2
3
for(int* y=x; y!=x+3; y++){
    cout<<*y<<" "<<endl;
}

（5）arrayList的迭代器

1
2
3
class iterator;
iterator begin() {return iterator(element);}
iterator end() {return iterator(element+listSize);}

vector

多重表

chapter6 线性表——链式描述

单向链表：每个节点只有一个链

1
2
3
4
5
6
7
8
9
10
template <class T>
struct chainNode{
	T element;
    chainNode<T> *next;
    
    chainNode() {}
    chainNode(const T& element){this->element = element;}
    chainNode(const T& element, chainNode<T>* next)
    	{this->element = element; this->next = next;}
};
1
2
3
4
5
6
7
8
get(int theIndex) const
    //返回索引为theIndex的元素
    checkIndex(theIndex);
	chainNode<T>* currentNode = firstNode;
	for(int i=0; i<theIndex; i++){
    	currentNode = currentNode->next;
        return currentNode->element;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
indexOf(const T& theElement) const
    //返回元素theElement首次出现时的索引
    chainNode<T>* currentNode = firstNode;
	int index = 0;
	while(currentNode != NULL && 
		currentNode->element != theElement){
    	currentNode = currentNode->next;
        index++;
	}
	if(currentNode == NULL)
        return -1;
	else
        return index;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
erase(int theIndex)
    //删除索引为theIndex的元素
    checkIndex(theIndex);
    chainNode<T>* deleteNode;
	if(theIndex == 0){
    	deleteNode = firstNode;
        firstNode = firstNode->next;
    }else{
        chainNode<T>* p = firstNode;
        for(int i=0; i<theIndex-1; i++){
            p = p->next;
        }
        deleteNode = p->next;
        p->next = p->next->next;
    }
	listSize--;
	delete deleteNode;
1
2
3
4
5
6
7
8
9
10
11
12
13
insert(int theIndex, const T& theElement)
    //在索引为theIndex处插入元素theElement
    checkIndex(theIndex);
	if(theIndex == 0){
    	firstNode = new chainNode<T>(theElement, firstNode);
    }else{
        chainNode<T>* p = firstNode;
        for(int i=0; i<theIndex-1; i++){
            p = p->next;
        }
        p->next = new chainNode<T>(theElement, p->next);
    }
	listSize++;

iterator

extendedChain：lastNode

1
2
3
4
5
6
7
8
clear()
    //删除链表所有节点
    while(firstNode != NULL){
        chainNode<T>* nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
	listSize = 0;
1
2
3
4
5
6
7
8
9
10
push_back(const T& theElement)
    //在链表尾端插入元素theElement元素
    chainNode<T>* newNode = new chainNode<T>(theELment, NULL);
	if(firstNode == NULL)
        firstNode = lastNode = newNode;
	else{
    	lastNode->next = newNode;
        lastNode = newNode;
	}
	listSize++;

循环链表：将单向链表的头结点和尾节点连接起来。使用头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
indexOf(const T& theElment) const
	//返回元素theElement首次出现的索引
    headerNode->element = theElement;
	chainNode<T>* currentNode = headerNode->next;
	int index = 0;
	while(currentNode->element != theElement){
    	currentNode = currentNode->next;
        index++;
	}
	if(currentNode == headerNode)
        return -1;
	else
        return index;

双向链表：next指向右边节点，previous指向左边节点。

箱子排序

基数排序

凸包

并查集：（1）等价类，等价关系 当且仅当 自反，对称，传递。相互等价的元素的最大集合。（2）离线等价类，已知n和R，确定等价类，每个元素只能属于一个等价类。（3）在线等价类，初始n，每个元素都属于一个等价类，需要combine和find。

1
2
3
4
5
classA = find(A);
classB = find(B);
if(classA != classB){
    unite(classA, classB);
}

chapter7 数组和矩阵

行主映射：map(i1, i2) = i1u2+i2；u2是数组的列数；列主映射：map(i1, i2) = u1i2+i1；

矩阵：

1
2
3
4
5
6
7
8
9
10
11
operator=(const matrix<T> m){
    //赋值 (*this) = m
    if(this != &m){
        delete [] element;
        theRows = m.theRows;
        theColumns = m.theColumns;
        element = new T [theRows*theColumns];
        copy(m.element, m.element+theRows*theColumns, element);
    }
    return *this;
}
1
2
3
4
5
6
operator() (int i, int j) const{
    //返回元素element(i,j)的引用
    if(...)
        //检测越界
    return element[(i-1)*theColumns+j-1];
}
1
2
3
4
5
6
7
8
9
10
operator+(const matrix<T>& m) const{
    //返回矩阵w = (*this)+m
    if(..)
        //检测
    matrix<T> w(theRows, theColunns);
    for(int i=0; i<theRows*theColumns; i++){
        w.element[i] = element[i]+m.element[i];
    }
    return w;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
operator* (const matrix<T>& m) const{
    if(..)
        //检测
    matrix<T> w(theRows, m.theColumns);
    int ct=0, cm=0, cw=0;
    for(int i=1; i<=theRows; i++){
        //结果矩阵第i行
        for(int j=1; j<=m.theColumns; j++){
            T sum = element[ct]*m.element[cm];
            for(int k=2; k<=theColumns; k++){
                ct++;
                cm += m.theColumns;
                sum += element[ct]*m.element[cm];
            }
            w.element[cw++] = sum;
            ct -= theColumns-1;
            cm = j;
        }
        ct += theColumns;
        cm = 0;
    }
    return w;
}

对角矩阵：

三对角矩阵：i=j，i=j+1，i=j-1.

对称矩阵

稀疏矩阵：大多数元素是0，记录非0元素的行号和列号，

chapter8 栈

栈：一种特殊的线性表，其插入和删除操作都在表的同一端进行。这一端称为栈顶，另一端称为栈底。后进先出

数组描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
template <class T>
void arrayStack : public stack<T>
{
	public:
		arrayStack(int initialCapacity = 10);
		~arrayStack() {delete [] stack;}
		bool empty() const {return stackTop == -1;}
		int size() const {return stackTop+1;}
        T& top(){
        	if(stackTop == -1)
        		throw stackEmpty();
        	return stack[stackTop];
        }
        void pop(){
        	if(stackTop == -1)
        		throw stackEmpty();
        	stack[stackTop--].~T();
        }
        void push(const T& theElement);
    private:
    	int stackTop;
    	int arrayLength;
    	T *stack;
};

template<class T>
arrayStack<T>::arrayStack(int initialCapacity){
	if(initialCapacity < 1)
        ..
    arrayLength = initialCapacity;
    stack = new T[arrayLength];
    stackTop = -1;
}

template<class T>
void arrayStack<T>::push(const T& theElement){
    if(stackTop == arrayLength-1){
        changeLength1D(stack, arrayLength, 2*arrayLength);
        arrayLength *= 2;
    }
    stack[++stackTop] = theElement;
}

链表描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
template<class T>
class linkedStack : public stack<T>{
	public:
    	linkedStack(int initialCapacity = 10)
        	{stackTop = NULL; stackSize = 0;}
    	~linkedStack();
    	bool empty() const {return stackSize == 0;}
    	T& top() {
        	if(stackSize == 0)
                throw ..
            return stackTop->element;
    	}
    	void pop();
    	void push(const T& theElement){
        	stackTop = new chainNode<T>(theElement, stackTop);
            stackSize++;
    	}
    private:
    	chainNode<T>* stackTop;
    	int stackSize;
}

template<class T>
linkedStack<T>::~linkedStack(){
    while(stackTop != NULL){
        chainNode<T>* nextNode = stackTop->next;
        delete stackTop;
        stackTop = nextNode;
    }
}

template<class T>
void linkedStack<T>::pop(){
	if(stackSize == 0)
        ..
    chainNode<T>* nextNode = stackTop->next;
    delete stackTop;
    stackTop = nextNode;
    stackSize--;
}

括号匹配：对一个字符串的左右括号进行匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void printMatchedPairs(string expr){
    //括号匹配
    arrayStack<int> s;
    int length = (int)expr.size();
    //扫描找左右括号
    for(int i=0; i<length; i++){
        if(expr.at(i) == '('){
            s.push(i);
        }else{
            if(expr.at(i) == ')'){
                cout<<s.top();
                s.pop();
            }
        }
    }
    
    while(!s.empty()){
        cout<<"no match"<<endl;
    }
}

chapter9 队列

队列：一个线性表，其插入和删除操作在表的不同端进行。插入元素的一端为队尾，删除元素的一端为队首。

数组描述：环形数组：location(i) = (location(队列首元素)+i)%arrayLength；

1
2
3
4
5
6
7
8
template<class T>
void arrayQueue<T>::push(const T& theElement){
    if((theBack+1)%arrayLength == theFront){
        //加倍长度
    }        
    queueBack = (queueBack+1)%arrayLength;
    queue[queueBack] = theElement;
}

加倍长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
T* newQueue = new T[2*arrayLength];
//复制
int start = (theFront+1)%arrayLength;
if(start<2){
    copy(queue+start, queue+start+arrayLength-1, newQueue);
}else{
    //队列形成环
    copy(queue+start, queue+arrayLength, newQueue);
    copy(queue, queue+theBack+1, newQueue+arrayLength-start);
}
theFront = 2*arrayLength-1;
theBack = arrayLength-2;
arrayLength *= 2;
delete[] queue;
queue = newQueue;
1
2
3
4
5
6
7
8
void pop(){
    //删除队首
    if(theFront == theBack){
        ..
    }
    theFront = (theFront+1)%arrayLength;
    queue[theFront].~T();
}

列车车厢重排

chapter10 跳表和散列

字典：形如(k,v)的数对所组成的集合，其中k是关键字，v是与关键字对应的值。任意两个数对，其关键字都不等。

线性表描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class K, class E>
pair<const K, E>* sortedChain<K,E>::find(const K& theKey) const{
	pairNode<K,E>* currentNode = firstNode;
    while(currentNode != NULL &&
         currentNode->element.first != theKey){
     	currentNode = currentNode->next;   
    }
    if(currentNode != NULL && 
       currentNode->element.first == theKey){
        return &currentNode->element;
    }
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<class K, class E>
void sortedChain<K,E>::insert(const pair<const K,E>& thePair){
	pairNode<K,E> *p = firstNode, *tp = NULL;
    while(p != NULL && p->element.first < thePair.first){
        tp = p;
        p = p->next;
    }
    if(p != NULL && p->element.first == thePair.first){
        //替换旧值
        p->element.second = thePair.seconde;
        return;
    }
    //无配对
    pairNode<K,E> *newNode = new pairNode<K,E>(thePair, p);
    if(tp == NULL){
        firstNode = newNode;
    }else{
        tp->next = newNode;
    }
    dSize++;
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class K, class E>
void sortedChain<K,E>::erase(const k& theKey){
	pairNode<K,E> *p = firstNode, *tp = NULL;
    while(p != NULL &&
          p->element.first < theKey){
        tp = p;
        p = p->next;
    }
    if(p != NULL && p->element.first == theKey){
        if(tp == NULL) firstNode = p->next;//要删除p所以first往后
        else tp->next = p->next;
        delete p;
        dSize--;
    }
}

跳表：在链表的中部节点加一个指针，可减少比较次数。查找一个数对，首先和中间比较，查找关键字小则在左部分找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class K, class E>
pair<const K,E>* skipList<K,E>::find(const K& theKey) const{
	if(theKey >= tailKey)
        return null;
    skipNode<K,E>* beforeNode = headNode;//theKey之前，最右边
    for(int i=levels; i>=0; i--){
        //从上级到下级
        while(beforeNode->next[i]->element.first < theKey){
            beforeNode = beforeNode->next[i];
        }
    }
    
    if(beforeNode->next[0]->element.first == theKey){
        return &beforeNode->next[0]->element;
    }
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
template<class K, class E>
skipNode<K,E>* skipList<K,E>::search(const K& theKey) const{
	skipNode<K,E>* beforeNode = headerNode;
    for(int i=levels; i>=0; i--){
        while(beforeNode->next[i]->element.first < theKey){
            beforeNode = beforeNoe->next[i];
        }
        last[i] = beforeNode;
    }
    return beforeNode->next[0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<class K, class E>
void skipList<K,E>::insert(const pair<const K, E>& thePair){
    if(thePair.first >= tailKey){
        ...
    }    
    skipNode<K,E>* theNode = search(thePair.first);
    if(theNode->element.first == thePair.first){
        theNode->element.second == thePair.second;
        return;
    }
    int theLevel = level();
    if(theLevel > levels){
        theLevel = ++levels;
        last[theLevel] = headerNode;
    }
    skipNode<K,E>* newNode = new skipNode<K,E>(thePair, theLevel+1);
    for(int i=0; i<=theLevel; i++){
        //插入i级链表
        newNode->next[i] = last[i]->next[i];
        last[i]->next[i] = newNode;
    }
    dSize++;
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class K, class E>
void skipList<k,E>::erase(const K& theKey){
    if(theKey >= tailKey){
        ...
    }      
    skipNode<K,E>* theNode = search(theKey);
    if(theNode->element.first != theKey)
        return;
    for(int i=0; i<=levels && last[i]->next[i]==theNode; i++){
        last[i]->next[i] = theNode->next[i];
    }
    while(levels>0 && headerNode->next[levels]==tailNode){
        levels--;
        delete theNode;
        dSize--;
    }
}

散列：用一个散列函数把字典的数对映射到一个散列表。

桶：散列表的每个位置叫一个桶，对关键字为k 的桶，f(k)是起始桶，桶的数量等于散列表的长度或大小。

除法散列函数：f(k) = k%D。理想的D，既是素数又不能被小于20的数整除。

冲突：当两个不同的关键字所对应的起始桶相同

溢出：如果存储桶没有空间存储一个数列

均匀散列函数

线性探查：找到下一个可用的桶。。

搜索方法：首先搜索起始桶f(k)，然后把散列表当做环表继续继续搜索下一个桶，直到以下情况之一发生为止：（1）存有关键字k的桶已找到；（2）到达一个空桶；（3）又回到起始桶f(k)。后两种说明关键字为k的数对不存在。

删除方法：①删除关键字后，需要一移动若干个数对。从删除位置的下一个桶开始，逐个检查每个桶，以确定要移动的元素，直至到达一个空桶或回到删除位置为止。在做删除移动时，不要把一个数对移到它的起始桶之前，否则查找会失败。②为每个桶增加一个域neverUsed。在散列表初始化时，这个域被置为true，当一个数对存入一个桶中时，置为false。搜索的结束条件： （2）变成neverUsed为tue。

链式散列：如果散列表的每一个桶可以容纳无限多的记录，则不存在溢出问题。给每个散列表的位置配置一个线性表。

chapter11 二叉树和其他树

一棵树t是一个非空的有限元素集合，其中一个元素为根，其余的元素组成t的子树。

级：level，树根是1级，其孩子是2级，..

一棵树的高度或深度：树中级的个数

一个元素的度：其孩子的个数

一棵树的度：其元素的度的最大值

二叉树：binary tree，t是有限个元素的集合（可以为空）。当二叉树非空时，其中有一个元素称为根，余下的元素被划分为两棵二叉树，分别称为t的左子树和右子树。

二叉树和树的根本区别：（1）二叉树的每个元素都恰好有两棵子树。树的每个元素可以有任意数量的子树。（2）二叉树中每个元素的子树都是有序的，有左子树和右子树之分。树的子树是无序的。（二叉树可以为空，但是树不能为空）

算术表达式树没有括号。

二叉树的特性：（1）一棵二叉树有n个元素，n>0，它有n-1条边。（2）一棵二叉树的高度为h，h>=0，它最少有h个元素，最多有2^h-1个元素。（3）一棵二叉树有n个元素，n>0，它的高度最大为n，最小高度为log2(n+1)。当高度为2^h-1个元素时，称为满二叉树。

对高度为h的满二叉树的元素，从第一层到最后一层，在每一次中从左至右，顺序编号，删除k个其编号为2^h-i元素，1<=i<=k<2^h，得到完全二叉树。

设完全二叉树的一元素其编号为i，（1）i=1，为根，i>1，父节点为i/2取整。（2）2i>n，元素无左孩子，否则左孩子为2i。（3）2i+1>n，无右孩子，否则右孩子为2i+1。

数组描述：把二叉树看成是缺少了部分元素的完全二叉树。

链表描述：节点两个指针域，leftChild，rightChild，一个element。

二叉树遍历：（1）前序遍历，根左右。（2）中序遍历，左根右。（3）后序遍历，左右根。（4）层次遍历。复杂性均为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void preOrder(binaryTreeNode<T> *t){
    if(t != NULL){
        visit(t);
        preOrder(t->leftChild);
        preOrder(t->rigthChild);
    }
}

void inOrder(binaryTreeNode<T>* t){
    if(t != NULL){
        preOrder(t->leftChild);
        visit(t);
        preOrder(t->rigthChild);
    }
}

void postOrder(binaryTreeNode<T>* t){
    if(t != NULL){
        preOrder(t->leftChild);
        preOrder(t->rigthChild);
        visit(t);
    }
}

在层次遍历中，从顶层到底层，在同一层中，从左到右，依次访问树的元素，需要队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void levelOrder(binaryTreeNode<T>* t){
    arrayQueue<binaryTreeNode<T>*> q;
    while(t != NULL){
        visit(t);
        if(t->leftChild != NULL){
            q.push(t->leftChild);
        }
        if(t->rigthChild != NULL){
            q.push(t->rightChild);
        }
        try{t = q.front();}
        catch{..}
        q.pop();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//确定树的高度
int height() const {return height(root);}

int linkedBinaryTree<E>::height(BinaryTreeNode<T>* t){
	if(t == NULL)
        return 0;
    int hl = height(t->leftChild);
    int hr = height(t->rightChild);
    if(hl > hr)
        return ++hl;
    else
        return ++hr;
}

当树t有节点超过两个孩子时，依然用二叉树表示。对每个节点x，可用其孩子节点的rightChild指针把x的所有孩子连成一条链表。x节点的leftChild指针指向该链表的第一个节点。

并查集：把每一个集合表示为一棵树，在查找时，我们把根元素作为集合标志符。为了确定元素theElement属于哪一个集合，从theElement节点开始，沿着节点到其父节点向上移动，直到根节点为止。

chapter12 优先级队列

优先级队列：是0个或多个元素的集合，每个元素都有一个优先级或值，操作top() push() pop()。最小/大优先级队列。相同优先级，任意顺序处理。

堆：一棵大根树，每个节点的值都大于或等于其子节点的值。一个大根堆，既是大根树也是完全二叉树。

插入：把新元素插入新节点，然后沿着从新节点到根节点的路径，执行一趟起泡操作，将新元素与其父节点的元素比较交换，直到后者大于或等于前者为止。

删除：删除根节点元素，把最后位置的删除，从根节点开始调整->最大堆/小。

O(height) = O(logn)

初始化：在空堆中执行n次插入操作。O(nlogn)

为了将完全二叉树转换成最大堆，从最后一个具有孩子的节点开始检查。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void maxHeap<T>::push(const T& theElement){
    if(heapSize == arrayLength-1){
        //数组长度加倍
    }
    //寻找插入位置
    //从新叶子向上移动
    int currentNode = ++heapSize;
    while(currentNode!=1 && heap[currentNode/2]<theElement){
        //父节点小于..
        heap[currentNode] = heap[currentNode/2];
        currentNode /= 2;//父节点移下来
    }
    heap[currentNode] = theElement;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void maxHeap<T>::pop(){
    if(heapSize == 0)
        throw queueEmpty();
    heap[1].~T();
    T lastElement = heap[heapSize--];
    int currentNode = 1,
    	child = 2;
    while(child <= heapSize){
        if(child<heapSize && heap[child]<heap[child+1]){
            child++;
        }
        if(lastElement >= heap[child]){
            break;//可以放在这个位置
        }
        //不可以
        heap[currentNode] = heap[child];
        currentNode = child;
        child *= 2;
    }
    heap[currentNode] = lastElement;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void maxHeap<T>::initialize(T *theHeap, int theSize){
    //初始化
    delete [] heap;
    heap = theHeap;
    heapSize = theSize;
    
    for(int root=heapSize/2; root>=1; root--){
        T rootElement = heap[root];
        int child = 2*root;
        while(child <= heapSize){
            if(child<heapSize && heap[child]<heap[child+1]){
                child++;
            }
            if(rootElement >= heap[child]){
                break;
            }
            heap[child/2] = heap[child];
            child *= 2;
        }
        heap[child/2] = rootElement;
        
    }
    
}

堆排序

霍夫曼编码：利用小根堆实现，小根堆的每个元素包括一棵二叉树和它的权。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
linkedBinaryTree<int>* huffmanTree(T weight[],int n){
    huffmanNode<T> *hNode = new huffmanNode<T>[n+1];
    linkedBinaryTree<int> emptyTree;
    for(int i=1; i<=n; i++){
        hNode[i].weight = weight[i];
        hNode[i].tree = new linkedBinaryTree<int>;
        hNode[i].tree->makeTree(i, emptyTree, emptyTree);
    }
    minHeap<huffmanNode<T> > heap(1);
    heap.initialize(hNode, n);
    huffmanNode<T> w, x, y;//从小根堆中提取两个树合并，直到剩下一棵树
    linkedBinaryTree<int>*z;
    fo(int i=1; i<n; i++){
        x = heap.top(); heap.pop();
        y = heap.top(); heap.pop();
        z = new linkedBinaryTree<int>;
        z->makeTree(0, *x.tree, *y.tree);
        w.weight = x.weight+y.weight;
        w.tree = z;
        heap.push(2);
        delete x.tree;
        delete y.tree;
    }
    return heap.top().tree;
}

chapter14 搜索树

二叉搜索树：一棵二叉树，可能为空；一棵非空二叉搜索树满足：（1）每个元素有一个关键字，并且任意两个元素的关键字都不同。所有关键字都是唯一的。（2）在根节点的左子树中，元素的关键字都小于根节点的关键字。（3）在根节点的右子树中，元素的关键字都大于根节点的关键字。（4）根节点的左、右子树也都是二叉搜索树。

索引二叉搜索树：在每个节点中添加一个leftSize域，这个域的值是该节点左子树的元素个数。

二叉搜索树的元素数量和形状随着操作而改变，所以用链表。

搜索：查找关键字为theKey的元素，先从根开始查找，如果根为空，那么搜索树不包含；如果不空，将theKey与根的关键字比较。如果theKey小，则在左子树中查找；大则在右子树中找；等于则查找成功。O(h)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pair<const K,E>* binarySearchTree<K,E>::find(const K& theKey) const{
    binaryTreeNode<pair<const K,E>> *p = root;
    while(p != NULL){
        if(theKey < p->element.first){
            p = p->leftChild;
        }else{
            if(theKey > p->element.first){
                p = p->rightChild;
            }else{
                return &p->element;
            }
        }
    }
    return NULL;
}

插入：插入新元素thePair，首先通过查找确定是否存在关键字与要插入的相同。搜索成功就替换；不成功就将新元素作为搜索中断节点的孩子插入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void binarySearchTree<K,E>::insert(const pair<const K,E>& thePair){
    binaryTreeNode<pair<const K,E>> *p = root, *pp = NULL;
    while(p != NULL){
        pp = p;
        if(thePair.first < p->element.first){
            p = p->leftChild;
        }else{
            if(thePair.first > p->element.first){
                p = p->rightChild;
            }else{
                p->element.second = thePair.second;
                return;
            }
        }
    }
    binaryTreeNode<pair<const K,E>> *newNode
        = new binaryTreeNode<pair<const K,E>>(thePair);
    if(root != NULL){
        if(thePair.first < pp->element.first){
            pp->leftChild = newNode;
        }else{
            pp->rightChild = newNode;
        }
    }else{
        root = newNode;
    }
    treeSize++;
}

删除：删除p（1）p是树叶，释放空间，若是根节点则为NULL。（2）p只有一棵非空子树，p是根节点，则p的唯一子树的根节点成为根节点，如果p有父节点pp，则修改pp的指针域，使其指向p的唯一孩子，释放节点p。（3）p有两棵非空子树，先将该节点替换为其左子树的最大元素或者右子树的最小元素，然后把替换元素的节点删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
void binarySearchTree<K,E>::erase(const K& theKey){
    binaryTreeNode<pair<const K,E>> *p = root, *pp = NULL;
    while(p != NULL && p->elemnt.first != theKey){
        pp = p;
        if(theKey < p->element.first){
            p = p->leftChild;
        }else{
            p = p->rightChild;
        }
        if(p == NULL){
            return;
        }
    }
    if(p == NULL){
        return;
    }
    if(p->leftChild != NULL && p-rightChild !=NULL){
        //转变成另外两种情况
        binaryTreeNode<pair<const K,E>> *s = p->leftChild,
        	*ps = p;
        while(s->rightChild != NULL){
            ps = s;
            s = s->rightChild;//max
        }
        binaryTreeNode<pair<const K,E>> *q = 
            new binaryTreeNode<pair<const K,E>>(s->element, p->leftChild, p->rightChild);
        if(pp == NULL){
            root = q;
        }else if(p == pp->leftChild){
            pp->leftChild = q;
        }else{
            pp->rightChild = q;
        }
        if(ps == p) pp = q;//无孩子
        else pp = ps;//1个
        delete p;
        p = s;
    }
    binaryTreeNode<pari<const K,E>> *c;
    if(p->leftChild != NULL)
        c = p->leftChild;
    else
        c = p->rightChild;
    if(p == root)
        root = c;
    else{
        if(p == pp->leftChild)
            pp->leftChild = c;
        else
            p->rightChild = c;
    }
    treeSize--;
    delete p;
}

二叉搜索树的高度：O(logn)

索引二叉搜索树：一个节点的数值域：leftSize、key、value。

chapter15 平衡搜索树

AVL树：最坏情况下的高度为O(logn)的树称为平衡树。一棵空的二叉树是AVL树；如果T是一棵非空二叉树，TL和TR分别是其左子树和右子树，那么T满足以下条件时，T是一棵AVL树：1）TL和TR是AVL树；2）|hL-hR|<=1。

一棵AVL搜索树既是二叉搜索树，又是AVL树。

AVL树特征：（1）一棵n个元素的AVL树，其高度是O(logn)。（2）对于每一个n，n>=0，都存在一棵AVL树；（3）对一棵n元素的AVL搜索树，在O(logn)时间内可实现查找；（4）将一个新元素插入一棵n元素的AVL搜索树总，可以得到一棵n+1个元素的AVL树，而且插入用时为O(logn)；（5）一个元素从一棵n元素的AVL搜索树中删除，可以得到一棵n-1个元素的AVL树，而且用时为O(logn)。

AVL树一般用链表描述，为每个节点增加一个平衡因子bf，节点x的平衡因子bf(x)定义为：x的左子树高度-x的右子树高度。可能取值：-1,0,1。

AVL搜索树的插入：插入导致不平衡的几种情况：（1）不平衡树中，平衡因子的值限于：-2,-1,0,1,2。（2）平衡因子为2的节点在插入前的平衡因子为1.（3）只有从根到新插入节点的路径上的节点的平衡因子在插入后会改变。（4）假设A是离新插入节点最近的祖先，且平衡因子是-2或2，在插入前，从A到新插入节点的路径上，所有节点的平衡因子都是0。

一棵树从平衡变为不平衡的唯一过程：在插入操作之后，平衡因子bf(X)的值由-1变为-2，或者由1变为2。后一种情况只有在X的左子树XL中进行插入时才会出行。

B树：

m叉索引树：可以是一棵空树，如果非空，必须满足以下特征：（1）在相应的扩充搜索树中，每个内部节点最多可以有m个孩子以及1~m-1个元素。（2）每一个含有p个元素的节点都有p+1个孩子。（3）对任意一个含有p个元素的节点，设k1,k2…,kp分别为关键字，k1<k2<..<kp，设c0,c1,..,cp是该节点的p+1个孩子。在以c0为根的子树中，元素的关键字小于k1；在以cp为根的子树中，元素的关键字大于kp；…

m叉搜索树的搜索：先从根节点开始，位于…，按照指针往下找。搜索中间子树的根，…找到或到达外部节点没找到。

m叉搜索树的插入：先查找，在x节点处查找失败，根据节点可容纳元素的个数插入位置。还可以加则根据大小插入，已经满了则生成一个新节点容纳。

m叉搜索树的删除：首先查找，（1）子节点都空，可以直接删除；（2）子节点至少有一个为空，用相邻非空子树的最大元素替换；（3）在根节点中删除，可能有多次替换。

m叉搜索树的高：logm(n+1)~n

m阶B-树：是一棵m叉搜索树，如果B-树非空，那么特征：（1）根节点至少有2个孩子；（2）除根节点外，所有内部节点至少有>=m/2个孩子；（3）所有外部节点在同一层，不算在高度里。

B-树的高度：设T是一棵高度为h的m阶B-树。令d=「m/2，则（1）2d^(h-1)<=n<=m^h-1；（2）logm(n+1)<=h<=logd((n+1)/2)+1

B-树的搜索：与m叉搜索树的算法类似。

B-树的插入：首先查找，如果不存在则将元素插入在搜索路径中所遇到的最后一个内部节点中。不允许有重复的关键字。

B树的删除：（1）该元素位于叶节点，（2）该元素位于非叶节点，（2）可转变成（1），过程是用一个元素来替换被删除元素，可以是左相邻子树最大的或者是右相邻子树最小的，替换元素必须在叶节点。只讨论情况（1）。①如果要删除的元素所在的叶节点其元素个数大于最少数，则直接删除

chapter16 图

图：有限集V和E的有序对，其中V的元素称为顶点，E的元素称为边。每一条边连接两个不同的顶点，而且用元组(i,j)表示，i,j为顶点。

有向边：带方向；无向边：不带方向。

当且仅当(i,j)是图的边，称顶点i和j是邻接的。边(i,j)关联于顶点i,j。

有向边(i,j)是关联至顶点j，关联于顶点i。顶点i邻接至顶点j，顶点j邻接于顶点i。

一个图是不能有重复的边，在无向图的任意两个顶点之间，最多只能有一条边。在有向图的任意两个顶点i,j之间，i到j至多一条边，j到i至多一条边。一个图不可能包含自连边/环。

权：每条边赋予一个表示成本的值。

G=(V,E)，G是连通的，当且仅当G的每一对顶点之间都有一条路径。如果H的顶点和边的集合分别是G的顶点和边的集合的子集，那么称H是G的子图。

一条始点和终点相同的简单路径称为环路。

没有环路的连通无向图是一棵树。

一个G的子图，如果包含G的所有顶点，且是一棵树，则称为G的生成树。

一个具有n个顶点的连通无向图至少有n-1条边。

在一个无向图中，有一个顶点i相关联的边数称为该顶点的度di。

特性：（1）∑d = 2e；（2）0<=e<=n(n-1)/2

一个具有n个顶点和n(n-1)/2条边的无向图是一个完全图。

设G是一个有向图，顶点i的入度指关联至该顶点的边数。顶点i的出度是指关联于该顶点的边数。

特性：（1）0<=e<=n(n-1)；（2）∑din = ∑dout = e

无权图的描述：邻接矩阵，邻接链表，邻接数组。

图的遍历：

BFS，广度优先搜索，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
virtual void bfs(int v, int reach[], int label){
    arrayQueue<int> q(10);
    reach[v] = label;
    q.push(v);
    while(!q.empty()){
        int w = q.front();
        q.pop();
        vertexIterator<T> *iw = iterator(w);
        int u;
        while((u=iw->next()) != 0){
            if(reach[u] == 0){
                q.push(u);
                reach[u] = label;
            }
        }
        delete iw;
    }
}

DFS，深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int v, int reach[], int label){
    graph<T>::reach = reach;
    graph<T>::label = label;
    rDfs(v);
}
void rDfs(int v){
    reach[v] = label;
    vertexIterator<T> *iv = iterator(v);
    int u;
    while((u=iv->next()) != 0){
        if(reach[u] == 0){
            rDfs(u);
        }
    }
    delete iv;
}

chapter17 贪婪算法

贪婪算法：greedy method，逐步构造一个最优解。每一步，在一定的标准下，作出一个最优决策。在每一步作出的决策，在以后的步骤中都不可更改。做出决策所依据的标准称为贪婪准则。

拓扑排序：任务有先后顺序，有向图表示，顶点活动网络（AOV，activity on vertex）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
bool topologicalOrder(int *theOrder){
    int n = numberOfVertices();
    //计算入度
    int *inDegree = new int[n+1];
    fill(inDegree+1, inDegree+n+1, 0);
    for(int i=1; i<=n; i++){
        vertexIterator<T> *ii = iterator(i);
        int u;
        while((u=ii->next()) != 0){
            inDegree[u]++;
        }
    }
    //入度=0的顶点入栈
    arrayStack<int> stack;
    for(int i=1; i<=n; i++){
        if(inDegree[i] == 0){
            stack.push(i);
        }
    }
    int j = 0;
    while(!stack.empty()){
        int nextVertex = stack.top();
        stack.pop();
        theOrder[j++] = nextVertex;
        vertexIterator<T> *iNextVertex = iterator(nextVertex);
        int u;
        while((u=iNextVertex->next()) != 0){
            inDegree[u]--;
            if(inDegree[u] == 0){
                stack.push(u);
            }
        }
    }
    return (j == n);
}

单源最短路径：

predecessor[i]是从源顶点到达顶点i的路径中顶点i前面的那个顶点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void shortestPath(int sourceVertex, T* distanceFromSource, int* predecessor){
    //distanceFromSource中返回最短路径
    graphChain<int> newReachableVertices;
    //初始化
    for(int i=1; i<=n; i++){
        distanceFromSource[i] = a[sourceVertex][i];
        if(distanceFromSource[i] == noEdge){
            predecessor[i] = -1;
        }else{
            predecessor[i] = sourceVertex;
            newReachableVertices.insert(0, i);
        }
    }
    distanceFromSource[sourceVertex] = 0;
    predecessor[sourceVertex] = 0;
    
    while(!newReachableVertices.empty()){
        chain<int>::iterator iNewReachableVertices = newReachableVertices.begin();
        chain<int>::iterator theEnd = newReachableVertices.end();
        int v = *iNewReachableVertiecs;
        iNewReachableVertices++;
        while(iNewReachableVertices != theEnd){
            int w = *iNewReachableVertices;
            iNewReachableVertices++;
            if(distanceFromSource[w] < distanceFromSource[v]){
                v = w;
            }
        }
        
        newReachableVertices.eraseElement(v);
        for(int j=1; j<=n; j++){
            if(a[v][j]!=noEdge && (predecessor[j]==-1 || distanceFromSource[j]>distanceFromSource[v]+a[v][j])){
                distanceFromSource[j] = distanceFromSource[v]+a[v][j];
                if(predecessor[j] == -1){
                    newReachableVertices.insert(0, j);
                }
                predecessor[j] = v;
            }
        }
    }
}

最小生成树

kruskal：分步骤选择n-1条边，每步选择一条边，贪婪准则：从剩下的边中，选择一条权最小且不会产生环路的边加入已经选择的边集。O(n+eloge)

Prim：分布选边来创建最小生成树，而且一步选择一条边。贪婪准则：从剩余的边中，选择一条成本最小的边，并且把他们加入已选的边集中形成一棵树。快一点。O(n^2)

Sollin：△

chapter18 分而治之

归并排序

快速排序

选择：从n元素数组a[0:n-1]中找出第k小的元素。首先对n个元素的数组a[0:n-1]排序，然后取出a[k-1]中的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
T select(T a[], int n, int k){
    int max = indexOfMax(a, n);
    swap(a[n-1], a[max]);
    return select(a, 0, n-1, k);
}

T select(T a[], int leftEnd, int rightEnd, int k){
    if(leftEnd >= rightEnd)
        return a[leftEnd];
    int leftCursor = leftEnd,
    	rightCursor = rightEnd+1;
    T pivot = a[leftEnd];
    while(true){
        do{
            leftCursor++;
        }while(a[leftCursor] < pivot);
        do{
            rightCursor--;
        }while(a[rightCursor] > pivot);
        if(leftCursor >= rightCursor) return;
        swap(a[leftCursor], a[rightCursor]);
    }
    if(rightCursor-leftEnd+1 == k){
        return pivot;
    }
    a[leftEnd] = a[rightCursor];
    a[rightCursor] = pivot;
    if(rightCursor-leftEnd+1 < k){
        return select(a, rightCursor+1, rightEnd,
                     k-rightCursor+leftEnd-1);
    }else{
        return select(a, leftEnd, rightCursor-1, k);
    }
}

chapter19 动态规划

所有顶点对之间的最短路径：

可以Dijkstra算法n次求解。

Floy算法：假设图G有n个顶点，且从1到n编号，c(i,j,k)表示从顶点I到j的一条最短路径的长度，其中间顶点的编号不都大于k。如果(i,j)存在，则c(i,j,0)表示该边长度。c(i,j,n)是从i到j的最短路径长度。

kay表示i到j的最短路径中的最大的k值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void allPairs(T **c, int **kay){
    //initialize
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            c[i][j] = a[i][j];
            kay[i][j] = 0;
        }
    }
    for(int i=1; i<=n; i++){
        c[i][i] = 0;
    }
    
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(c[i][k]!=noEdge && c[k][j]!=noEdge &&
                   (c[i][j]==noEdge || c[i][j]>c[i][k]+c[k][j])){
                    c[i][j] = c[i][k]+c[k][j];
                    kay[i][j] = k;
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class T>
int indexOfMax(T a[], int n){
    //查找数组a[0:n-1]的最大元素
    if(n <= 0){
        throw illeaglaParameterValue("..");
    }
    int indexOfMax = 0;
    for(int i=1; i<n; i++){
        if(a[indexOfMax] < a[i]){
            indexOfMax = i;
        }
    }
    return indexOfMax;
}

1、选择排序

首先找出最大的元素，把它调a[n-1]，然后在余下的n-1个元素中找出最大的元素，把它移到a[n-2]，如此直到剩下一个元素。

比较次数：n(n-1)/2，移动次数：3(n-1)

1
2
3
4
5
6
7
8
9
template<class T>
void selectionSort(T a[], int n){
    //选择排序a[0:n-1]
    for(int size=n; size>1; size--){
        //先找出n个元素中最大的，再n-1中的,..
        int j = indexOfMax(a, size);//size  not n
        swap(a[j], a[size-1]);
    }
}

及时终止的选择排序：

为了去除不必要的迭代，在查找最大元素时，同时检查数组是否已经有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class T>
void selectionSort(T a[], int n){
	//及时终止的选择排序
    bool sorted = false;
    for(int size=n; !sorted&&(size>1); size--){
        int indexOfMax = 0;
        sorted = true;
        //查找最大元素
        for(int i=1; i<size; i++){
            if(a[indexOfMax] <= a[i])
                indexOfMax = i;//index从0开始，大的在后面
            else
                sorted = false;
        }
        swap(a[indexOfMax], a[i]);
    }
}

2、冒泡排序

在一次冒泡过程中，相邻的元素比较，如果左边的元素大于右边的元素，则交换。把最大的元素移到序列最右端。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
void bubble(T a[], int n){
    //一次冒泡，把a[0:n-1]中最大元素移到右边
    for(int i=0; i<n-1; i++){//n-1
        if(a[i] > a[i+1]){
            swap(a[i], a[i+1])；
        }
    }
}

template<class T>
void bubbleSort(T a[], int n){
    for(int i=n; i>1; i--){
        bubble(a[], i);
    }    
}

及时终止的冒泡排序：

如果在一次冒泡过程中没有发生元素互换，说明数组已经有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
bool bubble(T a[], int n){
    bool swapped = false;
    for(int i=0; i<n-1; i++){
        if(a[i] > a[i+1]){
            swap(a[i], a[i+1]);
            swapped = true;
        }
    }
    return swapped;
}

template<class T>
void bubbleSort(T a[], int n){
    for(int i=n; i>1&&bubble(a,i); i++);
}

3、名词排序

计算出名次，就可以移到与其名次对应的位置。

名次：所有比该元素小的元素的个数加上在它左边出现的与它相同的元素的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
template<class T>
void rank(T a[], int n, int r[]){
    //计算名次
    for(int i=0; i<n; i++){
        r[i] = 0;//初始化
    }
    //比较所有元素对
    for(int i=1; i<n; i++){
        for(int j=0; j<i; j++){//!
            if(a[j] <= a[i])
                r[i]++;
            else
                r[j]++;//!
        }
    }
}

template<class T>
void rearrange(T a[], int n, int r[]){
    //使用附加数组将元素排序
    T *u = new T [n];//附加数组
    //把a中元素移到u中正确位置
    for(int i=0; i<n; i++){
        u[r[i]] = a[i];
    }
    //把u中元素移回a
    for(int i=0; i<n; i++){
        a[i] = u[i];
    }
}

4、原地重排

已经用rank计算出名次，不借助其他空间，将a中的元素按照名次排序。

1
2
3
4
5
6
7
8
9
10
11
template<class T>
void rearrange(T a[], int n, int r[]){
    //原地重排
    for(int i=0; i<n; i++){
        while(r[i] != i){//r[i]中是名次
            int t = r[i];
            swap(a[i], a[t]);
            swap(r[i], r[t]);
        }
    }
}

5、插入排序

从单元数组开始，不断实施插入操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
void insert(T a[], int n, const T& x){
    //x插入有序数组
    for(int i=n-1； i>=0&&x<a[i]; i--){
        a[i+1] = a[i];//大的往后挪
    }
    a[i+1] = x;
}

template<class T>
void insertionSort(T a[], int n){
    for(int i=1; i<n; i++){
        T t = a[i];
        insert(a, i, t);
    }    
}

6、箱子排序

首先把分数相同的节点放在同一个箱子里，然后把箱子链接起来就得到有序的链表。每一个箱子都是一个链表，一个箱子的节点数目介于0~n之间。开始时所有箱子都是空的，排序：（1）逐个删除输入链表的节点，把删除的节点分配到相应的箱子里；（2）把每一个箱子中的链表手机并链接起来，使其成为一个有序链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void binSort(chain<T>& theChain, int range){
    //初始化
    chain<T> *bin;
    bin = new chain<T>[range+1];
    //取出分配到箱子里
    int numberOfElements = theChain.size();
    for(int i=1; i<=nu,berOfElements; i++){
        T x = theChain.get(0);
        theChain.erase(0);
        bin[x.score].insert(0,x);
    }
    //从箱子中手机元素
    for(int j=range; j>=0; j--){
        while(!bin[j].empty()){
            T x = bin[j].get(0);
            bin[j].erase(0);
            theChain.insert(0,x);
        }
    }
    delete [] bin;
}

7、基数排序

把数按照某种基数分解为数字，然后对数字排序。

（1）利用箱子排序，根据最低位数字，对10个数进行排序。

（2）利用箱子排序，对（1）的结果根据次低位排序。….

8、堆排序

先用n个待排序的元素来初始化一个大根堆，然后从堆中逐个提取元素。按非递减排列。初始化O(n)，每次删除O(logn)，总的O(nlogn)。

1
2
3
4
5
6
7
8
9
10
void heapSort(T a[], int n){
    maxHeap<T> heap(1);
    heap.initialize(a, n);
    for(int i=n-1; i>=1; i--){
        T x = heap.top();
        heap.pop();
        a[i+1] = x;
    }
    heap.deactivateArray();
}

9、归并排序

若n为1，则算法终止；否则，将序列划分为k个子序列。先对每一个子序列排序，然后将有序子序列归并为一个序列。k=2称为merge sort

首先将每两个相邻的大小为1的子序列归并，然后将每两个相邻的大小为2的子序列归并，。。直到只剩下一个有序序列。轮流地将元素从a到b，从b到a。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void mergeSort(T a[], int n){
    T *b = new T[n];
    int segmentSize = 1;
    while(segmentSize < n){
        mergePass(a, b, n, segmentSize);
        segmentSize += segmentSize;
        mergePass(b, a, n, segmentSize);
        segmentSize += segmentSize;
    }
    delete[] b;
}

//仅确定要归并的子序列的左右边界
void mergePass(T x[], T y[], int n, int segmentSize){
    int i=0;
    while(i <= n-2*segmentSize){
        merge(x, y, i,i+segmentSize-1, i+2*segmentSize-1);
        i = i+2*segmentSize;
    }
    //少于两个满数据段
    if(i+segmentSize < n){
        merge(x, y, i, i+segmentSize-1, n-1);
    }else{
        //1个
        for(int j=i; j<n; j++){
            y[j] = x[j];
        }
    }
}

void merge(T c[], T d[], int startOfFirst, int endOfFirst, int endOfSecond){
    int first = startOfFirst;
    int second = endOfFirst+1;
    int result = startOfFirst;
    while((first<=endOfFirst) && (second<=endOfSecond)){
        if(c[first] <= c[second])
            d[result++] = c[first++];
        else
            d[result++] = c[second++];
    }
    //归并剩余元素
    if(first > endOfFirst)
        for(int q=second; q<=endOfSecond; q++)
            d[result++] = c[q];
    else
        for(int q=first; q<=endOfFirst; q++)
            d[result++] = c[q];
}

10、快速排序

把n个元素划分为三段：左段left，中间段middle，右段right。中段仅有一个元素，左段的元素都不大于中间段的元素，右段的元素都不小于中间段的元素，可对左右独立排序，且排序后不用归并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void quichSort(T a[], int n){
    if(n <= 1){
        return;
    }
    int max = indexOfMax(a, n);
    swap(a[n-1], a[max]);
    quickSort(a, 0, n-2);
}

void quickSor(T a[], int leftEnd, int rightEnd){
    if(leftEnd >= rightEnd)
        return;
    int leftCursor = leftEnd;
    int rightCursor = rightEnd+1;
    T pivot = a[leftEnd];
    while(true){
        do{
            leftCursor++;
        }while(a[leftCursor] < pivot);
        
        do{
            rightCursor--;
        }while(a[rightCursor] > pivot);
        
        if(leftCursor >= rightCursor){
            break;
        }
        swap(a[leftCursor], a[rightCursor]);
    }
    a[leftEnd] = a[rightCursor];
    a[rightCursor] = pivot;
    quickSort(a, leftEnd, rightCursor-1);
    quickSort(a, rightCursor+1， rightEnd);
}
赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

机会要自己把握<br><br>再勇敢一点吧<br>女孩