欢迎来到天天文库
浏览记录
ID：13054367
大小：91.29 KB
页数：4页
时间：2018-07-20
《腾挪次数的比较及算法分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、算法分析1、插入排序：逐个比较数组中的第i个数和之前已经排好的i-1个数，确定这个数在数组中的位置，然后移动已经排好的数字，将该数字插入到数组中。2、合并排序：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。1、快速排序：为了进一步改进合并排序挪动元素的次数，则继续利用二分的分治策略，将数组划分成左半部、中间元素和右半部部分。其中，左半部一定不大于左半部，则合并时不需再挪动了。对于输入的子数组a[p:r],按三个步骤a)分解：以a[p]为基准元素，将a[p:r]划分成3段a[p:q-1],
2、a[q]和a[q+1:r]b)递归求解：分别对两端进行排序c)合并腾挪次数的比较：当n=10:n=100：n=1000:n=10000:结论：当n比较大的时候，使用合并排序方法可获得较高的执行效率。算法复杂度分析：1、插入排序：O(n^2)2、合并排序：O(nlogn)3、快速排序：O(nlogn)
此文档下载收益归作者所有
