acm基本算法大全
第一章 排序、顺序统计与解题的基本策略1.1计数排序/ 计数排序.cpp : Defines the entry point for the console application./计数排序，输入数字，在0100之间，数字个数一般远多于100#include "stdafx.h"#include <iostream>using namespace std;int main(int argc, char* argv)int n;while(cin>>n)int count101=0,arrayA10000,arrayB10000,i;for(i=0;i<n;i+)cin>>arrayAi;countarrayAi+;for(i=1;i<101;i+)counti+=counti-1;for(i=0;i<n;i+)arrayB-countarrayAi=arrayAi;for(i=0;i<n;i+)cout<<arrayBi<<' 'cout<<endl;return 0;1.2 快速排序/ 快速排序sort和qsort.cpp : Defines the entry point for the console application./#include "stdafx.h"#include <iostream>#include <cstdlib>#include <algorithm>using namespace std;typedef struct int x,y;Node;bool cmpfn(Node a,Node b)return a.x<b.x;int Cmp(const void *a,const void *b)return (*(Node *)a).x-(*(Node *)b).x;int main(int argc, char* argv)int i,n;Node array100;for(cin>>n,i=0;i<n;i+)cin>>arrayi.x>>arrayi.y;sort(array,array+n,cmpfn);/qsort(array,n,sizeof(arrayi),Cmp);for(i=0;i<n;i+)cout<<arrayi.x<<' '<<arrayi.y<<endl;return 0;1.3稳定排序/ 稳定排序.cpp : Defines the entry point for the console application./#include "stdafx.h"#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;/从小到大排序bool cmpfn(int a,int b)return a<b;/*/从大到小排序bool cmpfn(int a,int b)return a>b;*/int main(int argc, char* argv)int i,n,array100;for(cin>>n,i=0;i<n;i+)cin>>arrayi;stable_sort(array,array+n,cmpfn);for(i=0;i<n;i+)cout<<arrayi<<' 'cout<<endl;return 0;1.4堆排序/ 堆排序.cpp : Defines the entry point for the console application./*堆排序排成完全二叉树，满足一下性质： 1.如果某节点有孩子，则根节点的值都小于孩子节点的值。我们称之为小堆根 2.如果某节点有孩子，则根节点的值都大于孩子节点的值。我们称之为大堆根以小堆根为例，根节点是最小值，次小值在根节点的两个孩子中 调整建堆的时间复杂度为W(lbn)小根堆 */#include "stdafx.h"#include <iostream>using namespace std;void DownHeap(int heap,int r,int len)int i,s=heapr;i=r<<1;while(i<=len)if(i+1<=len && heapi+1<heapi)i+;if(heapi<s)heapr=heapi;r=i;i=r<<1;elsebreak;heapr=s;void UpHeap(int heap,int r,int len)int i,s=heapr;i=r>>1;while(i>0 && s<heapi)heapr=heapi;r=i;i=r>>1;heapr=s;void MakeHeap(int heap,int len)for(int i=len>>1;i>0;i-)DownHeap(heap,i,len);void PushHeap(int heap,int x,int &len)heap+len=x;UpHeap(heap,len,len);void PopHeap(int heap,int &x,int &len)x=heap1;heap1=heaplen;DownHeap(heap,1,-len);void PrintHeap(int heap,int len)int i=len,x,a100;while(i>0)PopHeap(heap,x,i);alen-i=x;for(i=1;i<=len;i+)cout<<ai<<' 'cout<<endl;len=0;int main(int argc, char* argv)int len;while(cin>>len)int heap100,i;for(i=1;i<=len;i+)cin>>heapi;MakeHeap(heap,len);/PrintHeap(heap,len);PushHeap(heap,10,len);PrintHeap(heap,len);return 0;1.5“二分思想”/ 快速排序.cpp : Defines the entry point for the console application./*快速排序体现了“二分”的思想，排序的时间复杂度为nlog2(n)，速度最快其排序分成三个步骤：分解、解决和合并 */#include "stdafx.h"#include <iostream>using namespace std;void QuickSort(int array,int st,int ed)if(st<ed)int temp=array(ed+st)/2,i=st,j=ed;while(i<j)while(arrayi<temp)i+;while(arrayj>temp)j-;if(i<j)int t=arrayi;arrayi=arrayj;arrayj=t;QuickSort(array,st,j);QuickSort(array,j+1,ed);int main(int argc, char* argv)int n;while(cin>>n)int array10000,i;for(i=0;i<n;i+)cin>>arrayi;QuickSort(array,0,n-1);for(i=0;i<n;i+)cout<<arrayi<<' 'cout<<endl;return 0;/ 最近点对.cpp : Defines the entry point for the console application./#include <iostream>#include<cmath>#include <cstdio>#include <cstdlib>#include <cstring>using namespace std;const int N = 100005;const double MAX = 10e100;const double eps = 0.00001;typedef struct TYPEdouble x, y;int index; Point;Point aN, bN, cN;double closest(Point *, Point *, Point *, int, int);double dis(Point, Point);int cmp_x(const void *, const void*);int cmp_y(const void *, const void*);int merge(Point *, Point *, int, int, int);inline double min(double, double);int main()int n, i;double d;scanf("%d", &n);while (n)for (i = 0; i < n; i+)scanf("%lf%lf", &(ai.x), &(ai.y);qsort(a, n, sizeof(a0), cmp_x);for (i = 0; i < n; i+)ai.index = i;memcpy(b, a, n *sizeof(a0);qsort(b, n, sizeof(b0), cmp_y);d = closest(a, b, c, 0, n - 1);printf(
