数据结构 课件 第9章 排序.pptx
CONTENTS;说明：排序数据中可以存在相同关键字的记录。本章仅考虑递增排序。;当待排序记录的关键字均不相同时，排序的结果是唯一的。;如果待排序的表中，存在有多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的。;在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内排序；
反之，若排序过程中要进行数据的内、外存交换，则称之为外排序。;内排序;假设有3个记录(R1，R2，R3)，对应的关键字为(k1，k2，k3)。
初始数据序列有3!=6种情况：;;;决策树可以近似看成是一颗高度为h，叶结点个数为n!的满二叉树。;n个记录采用基于比较的排序方法：
最好的平均时间复杂度为O(nlog2n)。
最好情况是排序序列正序，此时的时间复杂度为O(n)。;typedefintKeyType; //定义关键字类型
typedefstruct //记录类型
{KeyTypekey; //关键字项
InfoTypedata; //其他数据项，类型为InfoType
}RecType; //排序的记录类型定义;主要的插入排序方法：
（1）直接插入排序
（2）折半插入排序
（3）希尔排序;有序区;;设待排序的表有10个元素，其关键字分别为（9，8，7，6，5，4，3，2，1，0）。说明采用直接插入排序方法进行排序的过程。;（9，8，7，6，5，4，3，2，1，0）;voidInsertSort(RecTypeR[]，intn)
{inti，j;RecTypetmp;
for(i=1;in;i++)
{if(R[i].keyR[i-1].key])//反序时
{tmp=R[i];
j=i-1;
do //找R[i]的插入位置
{R[j+1]=R[j]; //将关键字大于R[i].key的记录后移
j--;
}while(j=0R[j].keytmp.key)
R[j+1]=tmp; //在j+1处插入R[i]
}
}
};算法分析;查找采用折半查找方法，称为二分插入排序或折半插入排序。;voidBinInsertSort(RecTypeR[]，intn)
{inti，j，low，high，mid;
RecTypetmp;
for(i=1;in;i++)
{if(R[i].keyR[i-1].key]) //反序时
{tmp=R[i]; //将R[i]保存到tmp中
low=0;high=i-1;
while(low=high) //在R[low..high]中查找插入的位置
{mid=(low+high)/2; //取中间位置
if(tmp.keyR[mid].key)
high=mid-1; //插入点在左半区
else
low=mid+1; //插入点在右半区
}//找位置high
for(j=i-1;j=high+1;j--) //记录后移
R[j+1]=R[j];
R[high+1]=tmp; //插入tmp
}
};;说明：本题为6312年全国考研题;常见的交换排序方法：
（1）冒泡排序（或起泡排序）
（2）快速排序;;voidBubbleSort(RecTypeR[]，intn)
{inti，j;RecTypetemp;
for(i=0;in-1;i++)
{
for(j=n-1;ji;j--) //比较找本趟最小关键字的记录
if(R[j].keyR[j-1].key)
{temp=R[j]; //R[j]?R[j-1]
R[j]=R[j-1];
R[j-1]=temp;
}
}
};/63;/63;voidBubbleSort(RecTypeR[]，intn)
{inti，j;boolexchange;RecTypetemp;
f