ACM-排序（非常有用）资源-CSDN文库

需积分: 9 79 浏览量 2014-11-15 18:40:40 上传评论收藏 702KB DOCX 举报

资源推荐

资源详情

资源评论

ACM-排序算法整理

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排

序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。我们这里说

说八大排序就是内部排序。



当 n 较大，则应采用时间复杂度为 O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

 快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速

排序的平均时间最短；



算法实现：



我们简单处理增量序列：增量序列 d = {n/2 ,n/4, n/8 .....1}n 为要排序数的个数

即：先将要排序的一组记录按某个增量 d（n/2,n 为要排序数的个数）分成若干组子序列，

每组中记录的下标相差 d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量

（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为 1，最后使用

直接插入排序完成排序。

1. voidprint(inta[],intn,inti){

2. cout<<i<<":";

3. for(intj=0;j<8;j++){

4. cout<<a[j]<<"";

5. }

6. cout<<endl;

7. }

8. /**

9. *直接插入排序的一般形式¨

10. *

11. *@paramintdk缩小增量，如果是直接插入排序，dk=1

12. *

13. */

14. 

15. voidShellInsertSort(inta[],intn,intdk)

16. {

17. for(inti=dk;i<n;++i){

18. if(a[i]<a[i-dk]){//若第 i 个元素大于 i-1 元素，直接插入。小于的话，

移动有序表后插入¨¨

19. intj=i-dk;

20. intx=a[i];//复制为哨兵，即存储待排序元素¨¨

21. a[i]=a[i-dk];//首先后移一个元素¨¨

22. while(x<a[j]){//查找在有序表的插入位置¨¨

23. a[j+dk]=a[j];

24. j-=dk;//元素后移¨¨

25. }

26. a[j+dk]=x;//插入到正确位置¨¨

27. }

28. print(a,n,i);

29. }

剩余35页未读，继续阅读

内容反馈

慕丸

粉丝: 0
资源: 2

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip