排序

5.9. sort - sort lines of text files

01-01
$ du -s * | sort -k1,1rn $ rpm -q -a --qf '%10{SIZE}\t%{NAME}\n' | sort -k1,1n $ dpkg-query -W -f='${Installed-Size;10}\t${Package}\n' | sort -k1,1n 5.9.1. 对列排序 sort -k 具体说来, 你可以使用 -k1,1 来对第一列排序, -k1来对全行排序 # sort -t ':' -k 1 /etc/passwd ort -n -t ' '

[LeetCode] Maximum Length of Pair Chain 链对的最大长度

12-06
You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion. Given a set of

传输层

12-05
Ipv4 32位地址 80年代设计 Ipv6 128位地址 90年代设计 TCP 传输控制协议.面向连接的协议,全双工字节流 UDP 用户数据报协议 无连接, ICMP 网际控制消息协议,处理路由器和主机间的错误和控制消息 IGMP 网际组管理协议, RARP 反向地址解析协议 BPF BSD分组过滤器,为进程提供访问链路层数据的接口. DLPI 数据链路提供接口 TCP: 1 提供客户与UDP服务不相同 2 提供可靠性 3 通过给所发送数据的每一个字节关联一个序列号进行排序 4 提供流量控制.

插入排序的简单实现

12-05
最简单的排序算法了,每一次j--到对应的值,不会减到0,这个纠结我好久 1 #include "stdafx.h" 2 #include <iostream> 3 #include <vector> 4 using namespace std; 5 6 template <typename Comparable> 7 void insertionSort(vector<Comparable> & a) 8 { 9 int j; 1

合并排序

12-05
分治算法: 用分治策略实现n个元素进行排序的方法. 基本思想: 将待排序元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终排好序的子集合合并成所要求的排好序的集合. 源码: /* * mergeSort.cpp * 合并排序算法,算法导论P.17 * Created on: 2011-12-21 * Author: LiChanghai */ //#include <iostream> #include <vector> #include <iostream&g

Kruskal算法-最小生成树

12-05
算法思想: 1 将G的n个顶点看成n个孤立的连通分支,所有的边按权从小到大排序 2 当查看到第k条边时, 如果断点v和w分别是当前的两个不同的连通分支t1和t2中的顶点时,就用边(v,m)j将t1,t2连接成一个连通分支,然后继续查看第k+1条边: 如果端点v和w当前的同一个连通分支中,就直接查看第k+1条边 实现代码: template <class Type> class EdgeNode{ friend ostream& operator<<(ostream&

0-1背包-回溯法

12-05
算法描述: 0-1背包的回溯法,与装载问题的回溯法十分相似.在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入其左子树.当右子树中有可能包含最优解时才进入右子树进行搜索.否则将右子树剪去. 计算右子树上界的更好算法是: 将剩余物品依其单位重量价值排序,然后依次装入物品,直至装不下时,再装入该物品的一部分而装满背包. 算法实现: 由Bound函数计算当前节点处的上界. 类Knap的数据成员记录解空间树的节点信息,以减少参数传递及递归调用所需的栈空间. 在解空间树的当前扩展结点处,仅当要进

Kruskal算法

12-05
同样是求最小生成树,kruskal适合从边的角度出发,因此适合稀疏图.而prim算法从点的角度出发,适合稠密图. 时间复杂度为O(eloge).因为外层循环了e(边数)层,而内部find循环了loge层. 算法首先把二维矩阵图转化为边图 for(i=0;i<MAXSIZE;i++){ for(j=0;j<MAXSIZE;j++){ flag = 1; if(i != j && num[i][j] != INF){ for(k=0;k<=max;k++){ if(g->

AOV网络拓扑排序

12-05
这个算法,主要是为输出一个无环图的拓扑序列 算法思想: 主要依赖一个栈,用来存放没有入度的节点,每次读取栈顶元素,并将栈顶元素的后继节点入度减一,如果再次出现入度为零的节点,就加入到栈中.参考<大话数据结构>,写下下面完整代码,并发现,其中程序的进行,出现错误.v6执行完,应该执行v9,因为此时v9是站顶元素,并不是v0. 算法流程: int topGraph(graph g){ EdgeNode *e; int i,k,gettop; int top = 0 ; int count = 0;

二叉排序树1

12-05
二叉排序树,是一种规整的二叉树.每个节点的左子树都小于他,每个节点的右子树都大于他. 二叉树的遍历: void InOrderTree(BTree *b){ if( !b ) return; InOrderTree(b->lchild); printf("%d ",b->data); InOrderTree(b->rchild); } 二叉树的查找: int searchTree(BTree *b,int key,BTree *f,BTree *&p){ if

二叉排序树的删除操作

12-05
算法思想 二叉排序树,删除操作主要针对三种情况. 1 叶子节点-直接删除就可以了 2 没有左孩子的节点-直接嫁接右子树就可以了(没有右孩子的节点-直接嫁接左子树就可以了) 3 如果左右子树都存在,则寻找删除节点的直接前驱(即左子树里面的最右的节点) 编程时需要注意,函数时针对指针的操作,因此为了修改指针,要使用二级指针传参才可以 例如: void delete(BinaryTree **b){ .... } int main(){ BinaryTree *b = (BinaryTree *)ma

直接插入排序

12-05
时间复杂度: 如果排序的数组是正序的,那么时间复杂度相当于O(n), 而如果排序是随机的,时间复杂度相当于O(n^2/4). 倒置的时间复杂度是最高的,O(n^2). 算法思想: 该算法是设置了一个中间存储,每次读到的数据存储到中间值.向前遍历,如果大于这个值,继续向前,每次向前遍历时,把数据向后移,最后空出的位置,就是他本身应该在的位置.因此,如果是一个正序的数组,就不会出现移动的情况,时间复杂度也就降低了. 主要代码: void straightInsert(int *arr,int len

(递归版)合并排序

12-05
递归版的合并排序,时间复杂度为O(nlogn),空间复杂度为O(n+logn); 算法思想: 利用分而自治的思想,把排序分成两块,每块内部排序,再进行一次遍历排序即可,递归调用此过程即可. 主要代码: void MergeSort(int *arr,int length){ Msort(arr,arr,0,length-1); } void Msort(int *arr1,int *arr2,int begin,int end){ int arr3[10]; int m; if(begin ==

非递归版归并排序

12-05
非递归版的归并排序,省略了中间的栈空间,直接申请一段O(n)的地址空间即可,因此空间复杂度为O(n),时间复杂度为O(nlogn); 算法思想: 开始以间隔为1的进行归并,也就是说,第一个元素跟第二个进行归并.第三个与第四个进行归并: 然后,再以间隔为2的进行归并,1-4进行归并,5-8进行归并: 再以2*2的间隔,同理,知道2*k超过数组长度为止. while(i<length){ Merge(arr,temp,i,length); i *= 2; } 当不够两组进行归并是,如果超过k个元素,

(JAVA版)冒泡排序

12-05
核心代码: public void bubbleSort(){ for(int i=0;i<length-1;i++){ for(int j=0;j<length-i-1;j++){ if(a[j]>a[j+1]) swap(j,j+1); } } } public void swap(int indexa,int indexb){ int temp = a[indexa]; a[indexa] = a[indexb]; a[indexb] = temp; } 主要代码 class Ar

【设计模式】—— 策略模式Strategy

12-04
模式意图 定义一系列的算法,把他们封装起来,使得算法独立于适用对象. 比如,一个系统有很多的排序算法,但是使用哪个排序算法是客户对象的自有.因此把每一个排序当做一个策略对象,客户调用哪个对象,就使用对应的策略方法. 应用场景 1 当许多的类,仅仅是行为或者策略不同时,可以把行为或策略单独提取出来,这样主体的类就可以进行统一了. 2 需要使用不同的算法. 3 一个类定义了多种行为. 模式结构 Context 环境角色的,策略的调用者 class Context{ private Strategy

[大数据之Spark]——Transformations转换入门经典实例

12-04
Spark相比于Mapreduce的一大优势就是提供了很多的方法,可以直接使用:另一个优势就是执行速度快,这要得益于DAG的调度,想要理解这个调度规则,还要理解函数之间的依赖关系. 本篇就着重描述下Spark提供的Transformations方法. 依赖关系 宽依赖和窄依赖 窄依赖(narrow dependencies) 窄依赖是指父RDD仅仅被一个子RDD所使用,子RDD的每个分区依赖于常数个父分区(O(1),与数据规模无关). 输入输出一对一的算子,且结果RDD的分区结构不变.主要是ma

工作中的问题~按着枚举类型的字段进行排序

12-04
如果一个类中,有一个属性的类型是枚举型,那么,如果我们建立了一个类的集合对象,如List<类>,那我要根据它枚举值进行排序,如何进行? 事实上.net把枚举和整型自动给我们进行了一个转换,如果要排序枚举,我们可以理解成排序整型字段,没有任何分别,如果枚举没有赋值,那么.net 运行时会根据枚举元素出现的顺序进行排序,第1个元素的值为0,依次向下加1 看这个实例代码: enum Example { hihi , ok , yes , good , bad , } class exam { pub

常用算法和复杂度总结

01-03
一.常用算法和复杂度 算法 名称 复杂度 备注 快速排序 QuickSort(A,p,r) 最坏:O(n2) 平均:O(nlog n) 均衡划分:O(nlog n)   合并排序 MergeSort(A,p,r) O(nlog n)   选最大 FindMax O(n)   选最大和最小 FindMaxMin W(n)=3n/2-2=O(n)   找第二大 锦标赛法 n+logn-2   选择第k小 Select O(n)   动态规划:矩阵连乘 MatrixChain(P,n) 递归:O(2n

慎重选择容器类型

09-05
  慎重选择容器类型 一.回顾C++提供的容器 Ø        标准的STL序列容器 vector.string.deque和list. Ø        标准的STL关联容器 set.multiset.map和multimap. Ø        非标准序列容器 slist和rope. Ø        非标准的关联容器 hash_set.hash_multiset.hash_map和hash_multimap. Ø        几种标准的非STL容器 数组.bitset.valarray