《acm基本算法大全》由会员分享，可在线阅读，更多相关《acm基本算法大全（140页珍藏版）》请在金锄头文库上搜索。
1、第一章 排序、顺序统计与解题的基本策略1.1计数排序/ 计数排序.cpp : Defines the entry point for the console application./计数排序，输入数字，在0100之间，数字个数一般远多于100#include stdafx.h#include using namespace std;int main(int argc, char* argv)int n;while(cinn)int count101=0,arrayA10000,arrayB10000,i;for(i=0;iarrayAi;countarrayAi+;for(i=1;i101;
2、i+)counti+=counti-1;for(i=0;in;i+)arrayB-countarrayAi=arrayAi;for(i=0;in;i+)coutarrayBi ;coutendl;return 0;1.2 快速排序/ 快速排序sort和qsort.cpp : Defines the entry point for the console application./#include stdafx.h#include #include #include using namespace std;typedef struct int x,y;Node;bool cmpfn(Node a
3、,Node b)return a.xn,i=0;iarrayi.xarrayi.y;sort(array,array+n,cmpfn);/qsort(array,n,sizeof(arrayi),Cmp);for(i=0;in;i+)coutarrayi.x arrayi.yendl;return 0;1.3稳定排序/ 稳定排序.cpp : Defines the entry point for the console application./#include stdafx.h#include #include #include using namespace std;/从小到大排序bool
4、 cmpfn(int a,int b)return ab;*/int main(int argc, char* argv)int i,n,array100;for(cinn,i=0;iarrayi;stable_sort(array,array+n,cmpfn);for(i=0;in;i+)coutarrayi ;coutendl;return 0;1.4堆排序/ 堆排序.cpp : Defines the entry point for the console application./*堆排序排成完全二叉树，满足一下性质： 1.如果某节点有孩子，则根节点的值都小于孩子节点的值。我们称之为小
5、堆根 2.如果某节点有孩子，则根节点的值都大于孩子节点的值。我们称之为大堆根以小堆根为例，根节点是最小值，次小值在根节点的两个孩子中 调整建堆的时间复杂度为W(lbn)小根堆 */#include stdafx.h#include using namespace std;void DownHeap(int heap,int r,int len)int i,s=heapr;i=r1;while(i=len)if(i+1=len & heapi+1heapi)i+;if(heapis)heapr=heapi;r=i;i=r1;while(i0 & s1;heapr=s;void MakeHeap(
6、int heap,int len)for(int i=len1;i0;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(i0)PopHeap(heap,x,i);alen-i=x;for(
7、i=1;i=len;i+)coutai ;coutlen)int heap100,i;for(i=1;iheapi;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
8、#include using namespace std;void QuickSort(int array,int st,int ed)if(sted)int temp=array(ed+st)/2,i=st,j=ed;while(ij)while(arrayitemp)j-;if(in)int array10000,i;for(i=0;iarrayi;QuickSort(array,0,n-1);for(i=0;in;i+)coutarrayi ;coutendl;return 0;/ 最近点对.cpp : Defines the entry point for the console ap
9、plication./#include #include#include #include #include 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
10、(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(
