归并排序算法:选择排序，归并排序算法

教学目:

每趟在n-i+1(i=1,2,...n-1)个记录中选取关键字最小记录作为有序序列中第i个记录

算法:

Smp_Selecpass(ListType &r, i)

{

k=i;

for(j=i+1;j<n;i)

(r[j].key<r[k].key)

k=j;

(k!=i)

{ t=r[i];r[i]=r[k];r[k]=t;}

}

Smp_Sort(ListType &r)

{

for(i=1;i<n-1;i)

Smp_Selecpass(r,i);

}

又称锦标赛排序首先对n个记录关键字进行两两比较然后在其中半较小者的间再进行两两比较如此重复直到选出最小关键字记录为止

只需要个记录大小辅助空间每个待排序记录仅占有个存储空间

什么是堆？n个元素序列{k1,k2,...,kn}当且仅当满足下列关系时称的为堆关系:ki<=k2i 关系 2:ki<=k2i+1(i=1,2,...,n/2)

堆排序要解决两个问题:1、如何由个无序序列建成个堆？2、如何在输出堆顶元素的后调整剩余元素成为个新堆？

问题2解决思路方法:

st(ListType &r, k, m)

{

i=k;j=2*i;x=r[k].key;finished=FALSE;

t=r[k];

while((j<=m)&&(!finished))

{

((j<m)&&(r[j].key>r[j+1].key)) j;

(x<=r[j].key)

finished:=TRUE;

{r[i]=r[j];i=j;j=2*i;}

}

r[i]=t;

}

HeapSort(ListType &r)

{

for(i=n/2;i>0;i--) st(r,i,n);

for(i=n;i>1;i--){

r[1]<->r[i];

st(r,i,i-1)

}

}

将两个或两个以上有序表组合成个新有序表思路方法叫归并

假设序列含有n个记录则可看成是n个有序子序列每个子序列长度为1然后两两归并得到n/2个长度为2或1有序子序列；再两两归并如此重复



merge(ListType r, l, m, n,ListType &r2)

{

i=l;j=m+1;k=l-1;

while(i<=m) and(j<n) do

{

k=k+1;

(r[i].key<=r[j].key) {r2[k]=r[i];i;}

{r2[i]=r[j];j}

}

(i<=m) r2[k+1..n]=r[i..m];

(j<=n) r2[k+1..n]=r[j..n];

}

mergesort(ListType &r,ListType &r1, s, t)

{



(st)

r1[s]=r[s];

{

mergesort(r,r2,s,s+t/2);

mergesort(r,r2,s+t/2+1,t);

merge(r2,s,s+t/2,t,r1);

}

]

延伸阅读

• 2010-12-15-- 归并排序算法,根据Merge Sort原理， 自己实现的归并排序算法+详细注释+代码(C#，
• 2011-4-3-- 归并排序算法,算法-排序-归并排序(MergeSort)分析
• 2011-4-25-- 大话数据结构,《大话数据结构》第9章 排序 9.8 归并排序（上）
• 2011-4-26-- 大话数据结构,《大话数据结构》第9章 排序 9.8 归并排序（下）
• 2009-1-9-- 两路归并算法:C#两路归并排序
• 2009-10-3-- 排序算法:箱子排序算法
• 2009-10-3-- 排序算法:选择排序算法
• 2009-2-12-- 归并排序:磁盘分片归并排序函数
• 2009-2-12-- 归并排序的算法:递归算法学习（归并排序）
• 2009-2-12-- 归并排序算法:C语言算法之归并排序