排序思想和其应用.ppt

排序思想及其应用 ;排序问题;;装箱问题;计数排序的思想与应用;数据结构;程序;例如，A=（2，5，3，0，2，3，0，3）。显然k=5。 ;总结（1）;总结（2）;总结（3）;【试题1】独木舟上的旅行;猜想;定理：如果我们把V中的所有元素按重量从小到大依次与可能匹配的另一个尽可能重元素相匹配，那么匹配数是最多的，该方案称为方案1。;讨论各种可能出现的情况来证明可以通过调整的方法来使v匹配v1且不减少被匹配的元素数。;;计算过程;任务调度问题;;;;数据结构;;二分法 ;快速排序;procedure qsort(st,ed);{ 按照递增顺序排列区间[p[st]…p[ed]]} begin if st≥ed then exit;{排序完毕，成功退出} temp←p[(ed+st)div2];{选取一个中间元素} i←st-1;j←ed+1;{左右指针初始化} while ij do begin{右移左指针i，左移右指针j，使得左区间[p[st]…p[i-1]]的每一个元素均小于中间元素temp，右区间[p[j+1]…p[ed]] 的每一个元素均大于中间元素temp，p[i]≥temp ，p[j]≤temp} repeat inc(i) until p[i]≥temp; repeat dec(j) until p[j]≤temp; if ij then p[i]←→p[j];{若左右区间存在,则交换p[i]和p[j]} end;{while} qsort(st,j); qsort(j+1,ed){分别递归排序左右区间} end;{ qsort };排序工作量;思路点拨;二分法;求出d(lo,med)和d(med+1,hi)后，A[lo,med]和A[med+1,hi]已排序;;分析;背包问题;思路;;数据结构;;;堆排序的思想与应用;;在调整中保持堆性质(小根堆);从a[s]出发向下调整建堆;建堆;3、堆排序;例如对26，5，77，1，61进行堆排序;合并果子;数学模型;解决方案;　设堆尾指针为n，合并过程：将目前最小的一堆果子a[1]与a[n]对换，然后对a[1]‥a[n-1]进行堆排序（heap(1,n-1)），将排序后最小的一堆果子a[1]与a[n-1]对换，并对a[1]‥a[n-2]进行堆排序（heap(1,n-2)）。显然，被删除的两堆果子为a[n-1]和a[n]，将它们合并为a[n-1]= a[n-1]+ a[n]。 　接下来，用类似方法对a[1]‥a[n-1]进行一次合并。依次类推，直至合并成一堆为止。最小的体力耗费值 　　　　　　t= ; readln(n);{读入果子的种类数} for i←1 to n do read(a[i]);{读入每种果子的数目} buildheap(n);{建堆} t←0;{最小的体力耗费值初始化} while n1 do begin{若未最后合并成一堆} i←a[n];a[n] ←a[1];a[1] ←i;{交换a[n]与a[1]} heap(1,n-1);{将a[1]‥a[n-1]调整为堆} n←n-1;{删除a[n] } i←a[n];a[n] ←a[1];a[1] ←i; {交换a[n-1]与a[1]} heap(1,n-1);{将a[1]‥a[n-2]调整为堆} a[n] ←a[n]+a[n+1]; t←t+a[n];{将最小的两个结点合并成a[n-1]，并计入最小的体力耗费值} end;{while} writeln(t);{输出最小的体力耗费值} 这个算法的时间复杂度为O(nlog2n) ;设 var a,b:array[1..10002] of longint;{a为排序后的堆序列；b为合并的堆序列} i,j,n,p,t,x,y,min,method,ans:longint;{n为果子的种类数；min为当前合并消耗的体力；method为合并类型，ans为最小的体力耗费值；p为b序列的长度；x，y为合并过程中a序列和b序列的指针} num:array[1..20000] of integer;{num[i]为i个果子成一堆的堆数};首先我们将n堆果子按照果子数递增的顺序排成一个序列a[1]‥a[n],a[n+1]=∞,a[n+2]=∞。b序列设为空(b[1]=b[2]= ‥b[n]= ∞，p=0)。然后从a序列和b序列的第一个元素开始寻找合并方案（x=1，y=1）。每一次合并方案不外乎三种 合并两个初始堆（a[x]+a[x+1]）； 一个初始堆与一个先前被合并的堆进行合并（a[x]+b[y]）； 两个先前被合并的堆进行合并（b[y]+b[y+1]）； 显然，本次合并耗费