acm算法

ACM专题讲座-排序By:LDL问题引入为什么要排序？有序表的优点？缺点？按照什么原则排序？如何进行排序？基本概念排序（Sorting）：简单地说，排序就是把一组记录按照某个（或某几个）字段的值以递增（由小到大）或递减（由大到小）的次序重新排列的过程。排序算法是算法学习中最基本的问题！常见的排序算法1.冒泡排序2.选择排序3.插入排序4.归并排序5.快速排序6.希尔排序7.堆排序排序算法的评价评价排序算法好坏的标准执行算法的时间复杂度执行算法的空间复杂度算法本身的复杂程度排序的时间开销是算法好坏的最重要的标志排序的时间开销衡量标准:算法执行中的比较次数（必须）。算法执行中的移动次数（有可能避免）。通常关注最坏情况和平均复杂度冒泡排序思想：重复地交换相邻的两个反序元素，直到无反序元素伪代码：BubbleSort(A)fori=1tolength[A]doforj=length[A]downtoi+1doifA[j]A[j-1]thenexchangeA[j]-A[j-1]复杂度：O(n2)选择排序思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。伪代码：SelectSort(A)fori=1tolength[A]-1doforj=i+1tolength[A]doifA[j]A[j-1]thenexchangeA[j]-A[j-1]复杂度：O(n2)插入排序思想：每步将一个待排序的记录，按其排序码大小插到前面已经排序的字序列的合适位置，直到全部插入排序完为止伪代码：InsertionSort(A)forj=2tolength[A]dokey-A[j]i=j-1//InsertA[j]intothesortedsequeceA[1..j-1]Whilei0andA[i]keydoA[i+1]-A[i]i=i-1A[i+1]=key复杂度：O(n2)归并排序思想:分治法(divide-and-conquer)分治策略：将原问题划分为n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，得到原问题的解伪代码：MergeSort(A,p,r)if(pr)thenq=|(p+r)/2|MergeSort(A,p,q)MergeSort(A,q+1,r)Merge(A,p,q,r+1)//nextpageMerge(A,p,q,r)Merger(A,p,q,r)//L1p-q,L2q+1-rn1=q-p+1n2=r-qCreatarraysL[1..n1+1]andR[1..n2+1]fori=1ton1doL[i]=A[p+i-1]Forj=1ton2doR[j]=A[q+j]L[n1+1]=INFR[n2+1]=INF//sentinelcardi=1j=1Fork=ptordoifL[i]=R[j]thenA[k]-L[i]i=i+1elseA[k]=R[j]j=j+1快速排序思想：同合并排序一样，快速排序基于分治模式。排序的三个步骤为：分解，解决，合并伪代码：QuickSort(A,p,r)If(pr)thenq=Partition(A,p,r)QuickSort(A,p,q-1)QuickSort(A,q+1,r)最初调用QuickSort(A,1,length[A])Partition对A[p..r]进行就地重排伪代码：Partition(A,p,r)x-A[r]i=p-1forj=ptor-1doifA[j]=xtheni=i+1exchangeA[i]-A[j]exchangeA[i+1]-A[r]returni+1希尔排序思想：Shell排序算法依赖一种称之为“排序增量”的数列，增量最后为1，即普通排序，1排序是整个排序过程的最后一步，增量的选择对排序效率影响较大实例：37905168420615734982--原数列33205157440616879982--7-排序后00112233445656877989--3-排序后00112233445566778899--1-排序后（完成）Shell排序高效原因：在每一趟、每一组的排序中我们总是使用插入排序，每一趟排序使得序列部分有序，从而快速找到插入位置堆排序思想：利用堆这种数据结构。堆的定义：可以被视为一棵完全二叉树，树中每个节点与数组中存放该节点值的那个元素相对应堆的插入操作是平均常数的，而删除一个根节点需要花费O(logn)的时间。因此，完成堆排序需要线性时间建立堆（把所有元素依次插入一个堆），然后用总共O(nlogn)的时间不断取出最小的那个数。堆排序的基本过程Max-Heapify：运行时间O(logn)，保持最大堆性质的关键Build-Max-Heap:线性时间运行，可以在无序的输入数组的基础上构造出最大堆HeapSort：运行时间O(logn)，对一个数组原地进行排序Max–Heap-Insert,Heap-Extract-Max,Heap-Increase-Key和Heap-Maximum，运行时间为O(logn)，可以让堆结构作为优先队列使用各种排序算法的比较排序算法之间的比较主要考虑以下几个方面∶算法的时间复杂度算法的辅助空间排序的稳定性算法结构的复杂性参加排序的数据的规模排序码的初始状态排序算法的选择当数据规模n较小时，n2和nlog2n的差别不大，则采用简单的排序方法比较合适如直接插入排序或直接选择排序等由于直接插入排序法所需记录的移动较多，当对空间的要求不多时，可以采用表插入排序法减少记录的移动当文件的初态已基本有序时，可选择简单的排序方法如直接插入排序或起泡排序等当数据规模n较大时，应选用速度快的排序算法快速排序法最快，被认为是目前基于比较的排序方法中最好的方法当待排序的记录是随机分布时，快速排序的平均时间最短。但快速排序有可能出现最坏情况，则快速排序算法的时间复杂度为O(n2)，且递归深度为n，即所需栈空间为O(n)ACM比赛中排序方法1.C的qsort#includestdlib.h代码：intcmp(constvoid*p,constvoid*q){return*((int*)p)-*((int*)q);}qsort(array,n,sizeof(array[0]),cmp)ACM比赛中排序方法2.C++的Sort#includealgorithm代码：sort(array,n)手写排序，根据题目要求选择合适的排序方法排序题目推荐PKU2388Who'sintheMiddlePKU1828Monkeys'PridePKU2299Ultra-QuickSortPKU1838BananaPKU1007DNASortingPKU2379ACMRankTable题库推荐国内题库-北京大学浙江大学天津大学哈工大!