以下是为您整理出来关于【算法导论】合集内容，如果觉得还不错，请帮忙转发推荐。
目录 1、计数排序介绍 2、流程图 3、代码实现 4、性能分析 5、参考资料内容 1、计数排序介绍 什么是计数排序？ 计数排序是一种特殊的排序算...
讨论内容不说明，仅提供相应的程序。2.1:归并插入排序θ(nlgn)void mergeInsertionSort(int a[], int l, int r, int k) {int m;if(r-l+1 > k){m = (l + r) / 2;mergeInsertionSort(a, l, m, k);mergeInsertionSort(a, m+1, r, k);merge(a, l, m, r);}elseif(l < r)insertSort(a, l, r); }void insertSort(int a[], int l, int r) {int i, j, key;j = l;for(i=l+1; i<=r; i++)if(a[i] < a[j]) j = i;if(j > l){key = a[j];a[j] = a[...
计数排序假设n个输入元素中的每一个都介于0和k之间的整数，k为n个数中最大的元素。当k=O(n)时，计数排序的运行时间为θ(n)。计数排序的基本思想是：对n个输入元素中每一个元素x，统计出小于等于x的元素个数，根据x的个数可以确定x在输出数组中的最终位置。此过程需要引入两个辅助存放空间，存放结果的B[1...n]，用于确定每个元素个数的数组C[0...k]。算法的具体步骤如下： （1）根据输入数组A中元素的值确定k的值，并初始化C[1.......
heap// heap.h// PARENT(i) // return i / 2 // LEFT(i) // return 2 * i // RIGHT(i) // return 2 * i + 1// MAX-HEAPIFY(A, i) // l = LEFT(i) // r = RIGHT(i) // if l <= A.heap-size and A[l] > a[i] // largest = l // else largest = i // if r <= A.heap-size and A[r] > A[largest] // largest = r // if largest != i // exchange A[i] with A[largest] // MAX-HEAPIFY(A, largest)// BUILD-MAX-HEAP(A)...
最近又抽空读了一遍《算法导论》，关于图的内容贯穿了多个章节（比如在动态规划一章埋了无权最短路径的伏笔，后面才专门讲），适用条件各异，而且都有证明过程。 如果不打算熟记证明，仅仅是应用，遇到具体场景再去回忆适用于哪种算法不太方便。以下内容以手头的机械工业出版社基于原书第2版的译本整理了一下，便于速查。 不包含思考题、标注为“*”的章节和习题内容。符号定义一般地， 图G=(V, E)，其中V代表顶点集合，E代表边集合...
算法法导论》P129页课后题5.3-7 suppose we want to create a random sample of the set {1,2,3,…,n}, thatis, an m-element subset S, where0≤m≤n, such that each m-subset is equally likely to be created. One waywould be to set A[i]=i for i=1,2,3,…,n, call RANDOMIZE-IN-PLACE(A),and then take just the first marray elements. This method would make n calls to the RANDOM procedure.If n is much larger t...
一、一般的快速排序QuickSort.h文件#pragma once /*交换两个数*/ template<class T> void Swamp(T &a, T &b) {T temp;temp = a;a = b;b = temp; } /* 将数组分为小于等于x，和大于x的两个部分 其中这里x选择为数组的最后一个元素 如当输入{ 2,8,7,1,3,5,6,4 }时，输出为{2,1,3,4,7，5,6,8}，函数返回值为3，即数组中x的索引 */ template<class T> int Partition(T *src,int startIndex,int endIndex) {T x = src[endIndex];int i =...
原题：双向链表中，需要三个基本数据，一个携带具体数据，一个携带指向上一环节的prev指针，一个携带指向下一环节的next指针。请改写双向链表，仅用一个指针np实现双向链表的功能。定义np为next XOR prev，请根据表头提供的信息，为双向链表编写插入函数、删除函数和查找函数，并在O(1)时间内实现链表的翻转。 分析：问题的关键，在于怎样利用prev指针和next指针的异或结果，来获得上一节点或下一节点的地址值。也就是说，如何利用...
---恢复内容开始---5.1-1证明：假设在程序HIRE-ASSISTANT的第4行中，我们总是能够决定哪一个应聘者最佳，则意味着我们知道应聘者排名的总次序 既然我们总是能够决定哪一个应聘者最佳，想必我们已经对应聘者进行比较了，既然已经进行比较，排序就不应是个问题，既然可以进行排序，总次序也就可以知道了5.1-2描述RANDOM(a,b)过程的一种实现，它只调用RANDOM(0,1)。作为a和b的函数，你的程序的期望运行时间是多少？ 没看懂，不会...
class Graph:def__init__(self):self.V = []class Vertex:def__init__(self, x):self.key = xself.color = ‘white‘self.d = 10000self.f = 10000self.pi = Noneself.adj = []self.next = Noneclass Solution:def Dfs(self, G):for u in G.V:u.color = ‘white‘u.pi = Noneglobal timetime = 0for u in G.V:if u.color == ‘white‘:self.DfsVisit(G, u)def DfsVisit(self, G, u):global timetime = time + 1u.d = timeu.color =...