常用排序算法.ppt

文档介绍：常用排序算法
第1页，本讲稿共56页
内部排序: 指的是待排序记录存放在计算机随机存储器中进行的排序过程。
外部排序: 指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
内 //共进行n-1次插入
{int left=0,right=i-1; temp=pnum[i];
while(left<=right)
{ int middle=(left+right)/2; //取中点
if(temp<pnum[middle])
right=middle-1; //取左区间
else
left=middle+1; //取右区间
} for(int j=i-1;j>=left;j--)
pnum[j+1]=pnum[j]; //元素后移空出插入位
pnum[left]=temp;
}
}
折半插入排序——算法描述
第11页，本讲稿共56页
折半插入效率分析
二分插入算法与直接插入算法相比，
需要辅助空间与直接插入排序基本一致；
时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况坏，
两种方法的元素的移动次数相同，
因此二分插入排序的时间复杂度仍为O(n2)。
二分插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的。
第12页，本讲稿共56页
直接插入排序
1. 若待排序记录序列按关键字基本有序，则排序效率可大大提高；
2. 待排序记录总数越少，排序效率越高；
希尔(shell)排序
第13页，本讲稿共56页
将待排序记录序列分割成为若干子序列分别进行直接插入排序；
待整个序列中的记录基本有序后，再全体进行一次直接插入排序。
例，序列 49 38 65 97 76 13 27 48 55 4 19
第一趟排序
49 13 19
38 27
65 48
97 55
76 4
13 19 49
27 38
48 65
55 97
4 76
希尔(shell)排序——算法思想
第14页，本讲稿共56页
第二趟排序
13 19 49
27 38
48 65
55 97
4 76
13 55 38 76
27 4 65 49
48 19 97
13 38 55 76
4 27 49 65
19 48 97
第三趟排序
4 13 19 27 38 48 49 55