课件数据结构a-修改-9第九章排序

数据结构第九章排序计算机科学系施化吉E-mail:

本章将介绍一些常用的排序算法,并对有关的算法进行性能分析和对比。这些排序算法是：交换排序（冒泡排序、快速排序）插入排序（直接插入排序、折半插入排序、希尔排序）选择排序（直接选择排序、树形选择排序、堆排序）归并排序（二路归并排序）基数排序（链式基数排序）第九章排序9.1基础知识9.1基础知识

1．排序:

设含有n个数据元素的数据表为:{R[1]、…、R[n-1]、R[n]}

其相应的关键字序列为:

{K[1]、…、K[n-1]、K[n]}

若这些数据元素已按各关键字的递增(或递减)次序排列,则称该数据表是已排序的。那么把一个数据表变成已排序的数据表的过程就叫排序。姓名年龄体重1李由54622王天57763七大24754张强24725陈华2453上表按年龄无序,如果按关键字年龄用某方法排序后可以得到下表,则按年龄是有序的:姓名年龄体重3七大24754张强24725陈华24531李由54622王天5776例如:9.1基础知识

2．排序的稳定性:

假设在排序表中有任意两个i≠j的数据元素R[i]和R[j],它们的关键字K[i]==K[j],且在排序之前,数据元素R[i]排在R[j]的前面。那么若在排序之后,数据元素R[i]仍在数据元素R[j]的前面,则称这种排序方法是稳定的,否则称这种排序方法是不稳定的。也就是说如果关键字相同的数据元素在排序前、后的相对位置没有改变,则称这种排序方法是稳定的,否则称这种排序方法是不稳定的。请见下页举例:9.1基础知识

上表按年龄无序,如果按关键字年龄用某方法排序后得到下表:注意反色的三条记录保持原有排列顺序,则称该排序方法是稳定的！姓名年龄体重3七大24754张强24725陈华24531李由54622王天5776姓名年龄体重1李由54622王天57763七大24754张强24725陈华24539.1基础知识

如果用另一方法排序后得到下表:原3,4,5记录顺序改变,则称该排序方法是不稳定的！姓名年龄体重1李由54622王天57763七大24754张强24725陈华2453姓名年龄体重4张强24723七大24755陈华24531李由54622王天57769.1基础知识

3．内部排序与外部排序:

根据在排序过程中数据元素是否全部在内存中进行,排序可分为两大类:内部排序和外部排序。

内部排序是指在排序过程中数据元素全部存放在内存进行的排序;

外部排序是指由于数据元素太多,在排序期间全部数据元素不能同时存放在内存中,必须在排序过程中,不断地在内存和外存之间交换数据元素的排序。9.1基础知识

4．排序的效率:排序算法的效率可以从时间复杂度和空间复杂度两个方面来分析。即:时间复杂度空间复杂度

关键字的比较次数数据元素的移动次数辅助空间大小5．排序表的抽象数据类型描述

见教材P293-P2959.1基础知识

const

intMaxSize=100;template<classType>classsortlist;//排序表template<classType>classelement{//数据元素的类定义friend

classsortlist<Type>;private:

Typekey;//数据元素的关键字

//

other其它信息6.用顺序表表示的排序表的类定义:9.1基础知识

public://数据元素的类定义TypegetKey(){returnkey;}//取数据元素关键字

voidsetKey(constTypek){key=k;}//修改数据元素关键字

element<Type>&operator=(element<Type>&x){this=x;}

intoperator==(Type&k){return!(key<k||k<key);}intoperator!=(Type&k){return(key<k||k<key);}

intoperator<=(Type&k){return!(key>k);}

intoperator>=(Type&k){return!(key<k);}

intoperator<(Type&k){return(key<k);}

intoperator>(Type&k){return(key>k);}}//classelement数据元素的类定义

6.用顺序表表示的排序表的类定义:9.1基础知识

template<classType>classsortlist{//排序表的类定义private:element<Type>*Arr;//存储数据元素的向量(排序表)

intCurrentSize;//数据表中数据元素的个数public:sortlist():CurrentSize(0){Arr=newelement<Type>[MaxSize];}//构造函数

sortlist(){deleteArr[]};//析构函数

voidswap(element<Type>&x,element<Type>&y)//数据元素x和y交换位置

{element<Type>temp=x;x=y;y=temp;}}//classsortlist排序表的类定义6.用顺序表表示的排序表的类定义:9.1基础知识

9.2交换排序

在本节中,将介绍两种交换排序的方法:

交换排序的基本思想是两两比较待排序对象的关键字,如果发生逆序(即排列顺序与排序后的次序正好相反),则交换之,直到所有对象都排好序为止。

冒泡排序和快速排序。9.2.1冒泡排序

046131206319423531*

将第1个记录的关键字与第2个记录的关键字进行比较,若为逆序,即Arr[0].Key>Arr[1].Key,则交换;

然后比较第2个记录与第3个记录;

依次类推;

直至第n-1个记录和第n个记录比较为止

排序过程:设待排序对象序列中的对象个数为n46464646463106192331*469.2.1冒泡排序

046131206319423531*

将第1个记录的关键字与第2个记录的关键字进行比较,若为逆序,即Arr[0].Key>Arr[1].Key,则交换;

然后比较第2个记录与第3个记录;

依次类推;

直至第n-1个记录和第n个记录比较为止

排序过程:设待排序对象序列中的对象个数为n3106192331*469.2.1冒泡排序

046131206319423531*3106192331*46

将第1个记录的关键字与第2个记录的关键字进行比较,若为逆序,即Arr[0].Key>Arr[1].Key,则交换;

然后比较第2个记录与第3个记录;

依次类推;

直至第n-1个记录和第n个记录比较为止这是第一趟冒泡排序,其结果是:

关键字最大的记录被安置在最后一个记录位置上对前n-1个记录进行第二趟冒泡排序,结果使关键字次大的记录被安置在第n-1个记录位置上排序过程:设待排序对象序列中的对象个数为n9.2.1冒泡排序

046131206319423531*3106192331*46

将第1个记录的关键字与第2个记录的关键字进行比较,若为逆序,即Arr[0].Key>Arr[1].Key,则交换;

然后比较第2个记录与第3个记录;

依次类推;

直至第n-1个记录和第n个记录比较为止这是第一趟冒泡排序,其结果是:

关键字最大的记录被安置在最后一个记录位置上对前n-1个记录进行第二趟冒泡排序,结果使关键字次大的记录被安置在第n-1个记录位置上排序过程:设待排序对象序列中的对象个数为n9.2.1冒泡排序

031106219323431*5460619233131*46

将第1个记录的关键字与第2个记录的关键字进行比较,若为逆序,即Arr[0].Key>Arr[1].Key,则交换;

然后比较第2个记录与第3个记录;

依次类推;

直至第n-1个记录和第n个记录比较为止这是第一趟冒泡排序,其结果是:

关键字最大的记录被安置在最后一个记录位置上对前n-1个记录进行第二趟冒泡排序,结果使关键字次大的记录被安置在第n-1个记录位置上排序过程:设待排序对象序列中的对象个数为n9.2.1冒泡排序

031106219323431*5460619233131*46

将第1个记录的关键字与第2个记录的关键字进行比较,若为逆序,即Arr[0].Key>Arr[1].Key,则交换;

然后比较第2个记录与第3个记录;

依次类推;

直至第n-1个记录和第n个记录比较为止这是第一趟冒泡排序,其结果是:

关键字最大的记录被安置在最后一个记录位置上对前n-1个记录进行第二趟冒泡排序,结果使关键字次大的记录被安置在第n-1个记录位置上排序过程:设待排序对象序列中的对象个数为n重复上述过程,直到"在一趟排序过程中没有进行过交换记录的操作"为止冒泡排序示例之一:冒泡排序示例之一:4938659776132730开始排序3849657613273097第一趟结果38496513273076第二趟结果384913273065第三趟结果3813273049第四趟结果13273038第五趟结果132730第六趟结果384976971397279730971376767627301365276530651313494930492738273830381327第七趟结果4938659776132730初始关键字冒泡排序的算法:template<classType>voidBubbleSort(sortlist<Type>&table){

inti=1;while(i<=table.CurrentSize-1){//表示要进行n-1趟

i++;}//while}4938659776132730初始关键字3849657613273097第一趟如果某一趟没有发生交换,说明什么问题？说明已经是"正序",则可以提前结束。怎么改进？for(intj=0;j<=CurrentSize-i-1;j++)if(table.Arr[j].GetKey()>table.Arr[j+1].GetKey()))Swap(table.Arr[j],table.Arr[j+1]);冒泡排序示例之二:原来共需要7趟,但现在第6趟没有发生交换,则可提前结束4938659776132730初始关键字3849657613273097第1趟结果38496513273076第2趟结果384913273065第3趟结果3813273049第4趟结果13273038第5趟结果132730第6趟结果冒泡排序的算法(改进):template<classType>voidBubbleSort(sortlist<Type>&table){

inti=1;

while(i<=table.CurrentSize-1){

for(intj=0;j<=table.CurrentSize-i-1;j++)

if(table.Arr[j].GetKey()>table.Arr[j+1].GetKay())Swap(table.Arr[j],table.Arr[j+1]);

i++;}//while}4938659776132730初始关键字3849657613273097第1趟结果intfinish=0;//0表示还没有排好序

finish=1;//本趟开始时可认为已经正序,如果发生逆序,则改变finish值为0,表示还需要考察下一趟的情况{finish=0;}//排序结束标志置为0,表示本趟发生了交换,说明还不能结束,还需要考察下一趟的情况&&!finish冒泡排序示例之三:第3趟没有发生交换！可提前结束算法评价(改进的冒泡排序)时间复杂度最好情况(正序)比较次数:n-1(只要进行一趟即可)移动次数:0最坏情况(逆序)比较次数:(需n-1趟,每趟达到最大比较次数)移动次数:空间复杂度:S(n)=O(1)在最坏情况下,时间复杂度为:T(n)=O(n²)稳定性:冒泡排序算法是一种稳定的排序方法1122334455667788正序8877665544332211逆序快速排序9.2.2快速排序

快速排序(QuickSort)又被称做分区交换排序,这是一种平均性能非常好的排序方法。其算法基本思想是:任取排序表中的某个数据元素(例如取第一个数据元素)作为基准（也称枢轴）,按照该数据元素的关键字大小,将整个排序表划分为左右两个子表:

左侧子表中所有数据元素的关键字都小于基准数据元素的关键字,

右侧子表中所有数据元素的关键字都大于或等于基准数据元素的关键字,

基准数据元素则排在这两个子表中间(这也是该数据元素最终应安放的位置),

然后分别对这两个子表重复施行上述方法的快速排序,直到所有的子表长度为1,则排序结束。比如有结点的关键字序列F＝{k1,k2,…,kn},取k1为基准数据元素的关键字。则经过一次划分后就可以把序列F分成:

k1’,k2’,…,ks’,

k1,

k1’’,k2’’,…,kt’’,其中:s+t+1=n即:以k1为界把原序列F分成:F’,k1,F’’使得:F’中所有结点的关键字都小于k1,F’’中所有结点的关键字都大于等于k1以上把序列F以k1为界分成两部分的过程叫"一趟"。这时k1所在的位置也是该数据元素最终应安放的位置。如何做到这一点？如何把关键字序列{k1,k2,…,kn}中的k1放到它最终应安放的位置??看看是否可以这样考虑:首先把k1x,然后依次考察ki(i=2,3,…,n)若ki>x,则继续考察下一个结点ki+1,否则,把kiy;

然后把k1～ki-1这些结点依次往后移;

最后把y移到序列的第1个位置；然后继续考察下一个结点ki+1

具体举例见黑板解释。结论:如此处理不行！！！如何把关键字序列{k1,k2,…,kn}中的k1放到它最终应安放的位置??看看是否可以这样考虑:首先把k1x,然后依次考察ki(i=2,3,…,n)若ki>x,则继续考察下一个结点ki+1,否则,把kiy;

然后把k1～ki-1这些结点依次往后移;

最后把y移到序列的第1个位置；然后继续考察下一个结点ki+1

具体举例见黑板解释。结论:如此处理不行！！！?快速排序排序过程:对r[s],r[s+1],……,r[t]的记录进行快速排序。

附设两个指针:左指针i和右指针j,设r[s]为基准元素。即设:待排序记录为:r[s],r[s+1]～,….,r[t]ij初始时令i=s,j=t,且令x=r[s](1)从j所指位置向左(前)搜索,当r[j].key>=x.key时,r[j]不移动,修改j--,直到找到一个逆序的记录(r[j].key<x.key),把r[j]移到左边i所指的位置,然后修改左指针i,即i++；(2)从r[i]向右(后)搜索,直到r[i].key>x.key,把r[i]移动到右边j所指的位置;然后修改右指针j,即j--。

重复上述两步(1)和(2),直至i==j为止,此处就是基准元素x所在的位置。

再分别对两个子序列进行快速排序,直到每个子序列只含有一个记录为止。快速排序(第一趟数据移动情况)示例:设待排序记录的键值序列为{15,20,11,10,23,13}xx=15

快速排序过程示例1:[152011102313]初始第二趟排序后第三趟排序后第四趟排序后,结束。第一趟排序后[131011]15

[2320][1110]1315[2320][10]111315[2320]10111315[20]23

快速排序过程示例2:第一趟快速排序过程表示被考察的关键字表示移动后的关键字表示下标指针修改

快速排序过程示例2:各趟快速排序后的结果结束

快速排序过程示例2:快速排序算法的描述如下:template<classType>voidQuickSort(sortlist<Type>&table,intlow,inthigh){//在待排序区间lowhigh上,递归地进行快速排序

inti=low,j=high;element<Type>temp=table.Arr[low];

while(i<j){

while(i<j&&temp.GetKey()<=table.Arr[j].GetKey())j--;if(i<j){Swap(Table.Arr[i],Table.Arr[j]);i++;}

while(i<j&&temp.GetKey()>table.Arr[i].GetKey())i++;if(i<j){Swap(Table.Arr[i],Table.Arr[j]);j--;}}

}

while(i<j){}快速排序算法的描述如下:template<classType>voidQuickSort(sortlist<Type>&table,intlow,inthigh){//在待排序区间lowhigh上,递归地进行快速排序

inti=low,j=high;element<Type>temp=table.Arr[low];

while(i<j){

while(i<j&&temp.GetKey()<=table.Arr[j].GetKey())j--;if(i<j){Swap(Table.Arr[i],Table.Arr[j]);i++;}

while(i<j&&temp.GetKey()>table.Arr[i].GetKey())i++;if(i<j){Swap(Table.Arr[i],Table.Arr[j]);j--;}}

}

while(i<j){}Table.Arr[i]=temp;//将基准元素就位QuickSort(table,low,i-1);//在左子区间递归进行快速排序

QuickSort(table,i+1,high);//在右子区间递归进行快速排序这叫一趟快速排序算法的描述如下:template<classType>voidQuickSort(sortlist<Type>&table,intlow,inthigh){//在待排序区间lowhigh上,递归地进行快速排序

inti=low,j=high;element<Type>temp=table.Arr[low];

while(i<j&&temp.GetKey()<=table.Arr[j].GetKey())j--;if(i<j){Swap(Table.Arr[i],Table.Arr[j]);i++;}

while(i<j&&temp.GetKey()>table.Arr[i].GetKey())i++;if(i<j){Swap(Table.Arr[i],Table.Arr[j]);j--;}}Table.Arr[i]=temp;//将基准元素就位

QuickSort(list,low,i-1);//在左子区间递归进行快速排序

QuickSort(list,i+1,high);//在右子区间递归进行快速排序}

while(i<j){}Table.Arr[i]=temp;

//将基准元素就位QuickSort(table,low,i-1);//在左子区间递归进行快速排序

QuickSort(table,i+1,high);//在右子区间递归进行快速排序这叫一趟如果关键字序列为:11,22,33,44,55,66,77,88,会怎么样？将会造成数组下标j越界！！！因此还要补充条件。什么条件？要加上:i<j算法还有问题吗？快速排序算法的描述如下:template<classType>voidQuickSort(sortlist<Type>&table,intlow,inthigh){//在待排序区间lowhigh上,递归地进行快速排序

inti=low,j=high;element<Type>temp=table.Arr[low];

while(i<j){

while(i<j&&temp.GetKey()<=table.Arr[j].GetKey())j--;if(i<j){Swap(Table.Arr[i],Table.Arr[j]);i++;}

while(i<j&&temp.GetKey()>table.Arr[i].GetKey())i++;if(i<j){Swap(Table.Arr[i],Table.Arr[j]);j--;}}Table.Arr[i]=temp//将基准元素就位

QuickSort(list,low,i-1);//在左子区间递归进行快速排序

QuickSort(list,i+1,high);//在右子区间递归进行快速排序}

while(i<j){}i<j&&i<j&&if(i<j){}if(i<j){}Table.Arr[i]=temp;//将基准元素就位QuickSort(table,low,i-1);//在左子区间递归进行快速排序

QuickSort(table,i+1,high);//在右子区间递归进行快速排序这叫一趟例:已知关键字序列为:11,22,33,44,55,66,77请对其进行快速排序。初始:{11,22,33,44,55,66,77}第1趟11,{22,33,44,55,66,77}第2趟11,22,{33,44,55,66,77}第3趟11,22,33,{44,55,66,77}第4趟11,22,33,44,{55,66,77}第5趟11,22,33,44,55,{66,77}第6趟11,22,33,44,55,66,{77}结束结论:若初始记录序列按关键字有序或基本有序时,快速排序将蜕化为"冒泡排序"。？有这样的每一趟的排序结果的排序也可能是什么样的排序方法？为此,在这种情况下,通常依“三者取中”的法则选取基准元素,即比较:table.Arr[low].key,table.Arr[high].key,table.Arr[(low+high)/2].key,取三者中其关键字为中间值的记录为基准,只要将该记录和table.Arr[low]互换,而以上算法不变。lowhigh(low+high)/2算法评价时间复杂度最好情况(每次总是选到大小是中间值的元素为基准)T(n)=O(nlog2n)最坏情况(每次总是选到最小或最大元素为基准)T(n)=O(n²)空间复杂度:需栈空间以实现递归最坏情况:S(n)=O(n),栈的最大深度为n一般情况:S(n)=O(log2n),栈的最大深度为log2n+1

稳定性:快速排序是一种不稳定的排序方法。lowhigh快速排序算法的描述如下:template<classType>voidQuickSort(sortlist<Type>&table,intlow,inthigh){//在待排序区间lowhigh上,递归地进行快速排序

inti=low,j=high;element<Type>temp=table.Arr[low];

while(i<j){

while(i<j&&temp.GetKey()<=table.Arr[j].GetKey())j--;if(i<j){Swap(Table.Arr[i],Table.Arr[j]);i++;}

while(i<j&&temp.GetKey()>table.Arr[i].GetKey())i++;if(i<j){Swap(Table.Arr[i],Table.Arr[j]);j--;}}Table.Arr[i]=temp//将基准元素就位

QuickSort(list,low,i-1);//在左子区间递归进行快速排序

QuickSort(list,i+1,high);//在右子区间递归进行快速排序}

while(i<j){}i<j&&i<j&&if(i<j){}if(i<j){}Table.Arr[i]=temp;//将基准元素就位QuickSort(table,low,i-1);//在左子区间递归进行快速排序

QuickSort(table,i+1,high);//在右子区间递归进行快速排序为减少移动次数，还可以改为直接赋值快速排序算法的描述如下:template<classType>voidQuickSort(sortlist<Type>&table,intlow,inthigh){//在待排序区间lowhigh上,递归地进行快速排序

inti=low,j=high;element<Type>temp=table.Arr[low];while(i<j){while(i<j&&temp.GetKey()<=table.Arr[j].GetKey())j--;if(i<j){Table.Arr[i]=Table.Arr[j];i++;}while(i<j&&temp.GetKey()>table.Arr[i].GetKey())i++;if(i<j){Table.Arr[j]=Table.Arr[i];j--;}}Table.Arr[i]=temp;//将基准元素就位

QuickSort(list,low,i-1);//在左子区间递归进行快速排序

QuickSort(list,i+1,high);//在右子区间递归进行快速排序}9.3插入排序为减少移动次数，还可以改为直接赋值9.3插入排序

插入排序的基本思想是:

每一次设法把一个数据元素插入到已经排序的部分序列的合适位置,使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列,它只包含一个数据元素。然后,从这个的初始序列开始不断进行插入数据元素,直到最后一个数据元素插入到有序序列后,整个排序工作就完成了。9.3.1直接插入排序9.3.1直接插入排序

直接插入排序算法基本思想是:

开始时把第一个数据元素作为初始的有序序列,

然后依次从第二个数据元素开始把数据元素按关键字大小插入到已排序的部分排序表的适当位置。

当插入第i(1<i≤n)个数据元素时,前面的i-1个数据元素已经排好序,这时,用第i个数据元素的关键字与前面的i-1个数据元素的关键字顺序进行比较,找到插入位置后就将第i个数据元素插入,插入位置及其以后的数据元素都向后顺移一个位置。如此进行n-1次插入就完成了排序。1i-1in已经有序i=6(133849657697)

27(1)顺序表上的直接插入排序

在顺序表上进行直接插入排序过程及每趟的结果:例49386597761327i=1

(3849)6597761327i=2(384965)97761327i=3(38496597)761327i=4

(3849657697)1327i=5

(133849657697)27初始()jjjjjj7665493827(13273849657697)排序结果:temp97下标0123456直接插入排序算法的C++描述:template<classType>voidInsertionSort(sortlist<Type>&table){//从下标0开始存储element<Type>temp;

intj;

for(inti=1;i<=table.CurrentSize-1;i++){

temp=table.Arr[i];j=i-1;

while(

temp.getKey()<table.Arr[j].getKey()){table.Arr[j+1]=table.Arr[j];j--;}

table.Arr[j+1]=temp;

}}第6趟过程(133849657697)

2710第5趟结果(133849657697)2710jjjjjj7665493827temp97i下标01234567(13273849657697)10第6趟结果这叫一趟4938659776132710初始()直接插入排序算法的C++描述:template<classType>voidInsertionSort(sortlist<Type>&table){element<Type>temp;

intj;

for(inti=1;i<=table.CurrentSize-1;i++){

temp=table.Arr[i];j=i-1;

while(

temp.getKey()<table.Arr[j].getKey()){table.Arr[j+1]=table.Arr[j];j--;}

table.Arr[j+1]=temp;

}}第6趟过程(133849657697)

2710第5趟结果(133849657697)2710j7665493827temp97i下标01234567(13273849657697)10第6趟结果这叫一趟j>=0&&4938659776132710初始()如果要插入最后一个元素10会怎么样？将会造成数组下标越界,使得j=-1?直接插入排序算法的C++描述(采用监视哨技术):template<classType>voidInsertionSort(sortlist<Type>&table){

intj;

for(inti=i++){//从1单元开始存

=table.Arr[i];

j=i-1;

while(

getKey()<table.Arr[j].getKey())

{table.Arr[j+1]=table.Arr[j];j--;}

table.Arr[j+1]=

}}

2;i<=table.CurrentSize;

table.Arr[0]

table.Arr[0].

table.Arr[0];为了避免重复检测是否会数组越界,提高时间性能,还可以类似于顺序查找算法那样,采用"监视哨"技术加以改进。template<classType>voidInsertionSort(sortlist<Type>&table){//改进前算法

element<Type>temp;

intj;

for(inti=1;i<=table.CurrentSize-1;i++){

temp=table.Arr[i];j=i-1;

while(j>=0&&temp.getKey()<table.Arr[j].getKey()){table.Arr[j+1]=table.Arr[j];j--;}table.Arr[j+1]=temp;}}这叫一趟下标01234567初始()49386597761327直接插入排序算法的C++描述(采用监视哨技术):template<classType>voidInsertionSort(sortlist<Type>&table){

intj;

for(inti=i++){

=table.Arr[i];

j=i-1;

while(

getKey()<table.Arr[j].getKey())

{table.Arr[j+1]=table.Arr[j];j--;}

table.Arr[j+1]=

}}第5趟过程13(3849657697)第4趟结果76(3849657697)13jjjjjj766549381397i下标01234567

13(133849657697)

第5趟结果这叫一趟1349386597761327初始()

2;i<=table.CurrentSize;

table.Arr[0]

table.Arr[0].

table.Arr[0];作业:习题7(P246)2(1)(2)(3)(4)5710算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)关键字比较次数:记录移动次数:2(n-1)若待排序记录按关键字从大到小排列(逆序)关键字比较次数:记录移动次数:若待排序记录是随机的,取最好和最坏情况的平均值关键字比较次数(约为):记录移动次数(约为):T(n)=O(n²)空间复杂度:S(n)=O(1)稳定性:直接插入排序是一种稳定的排序方法i表示趟数9.3.1直接插入排序

直接插入排序算法基本思想是:

开始时把第1个数据元素作为初始的有序序列,

然后依次从第2个数据元素开始把数据元素按关键字大小插入到已排序的部分排序表的适当位置。

当插入第i(1<i≤n)个数据元素时,前面的i-1个数据元素已经排好序,这时,用第i个数据元素的关键字与前面的i-1个数据元素的关键字顺序进行比较,找到插入位置后就将第i个数据元素插入,原来位置及其以后的数据元素都向后顺移一个位置。如此进行n-1次插入就完成了排序。1i-1in已经有序既然1~i-1是“已经有序”的，那么查找插入位置的查找过程还可以通过折半查找方法来查找。9.3.2折半插入排序

折半插入排序算法与顺序表上进行直接插入排序的算法类似,只是在插入Arr[i]时,利用折半查找方法寻找Arr[i]的插入位置。1i-1in已经有序折半插入排序的算法可描述为:template<classType>voidBinaryInsertSort(sortlist<Type>&table){element<Type>temp;

intleft,right,mid;

for(inti=1;i<=table.CurrentSize-1;i++)

{

}//for}//BinaryInsertSort直接插入排序算法的C++描述:template<classType>voidInsertionSort(sortlist<Type>&table){element<Type>temp;intj;for(inti=1;i<=table.CurrentSize-1;i++){

temp=table.Arr[i];j=i-1;while(j>=0&&temp.getKey()<table.Arr[j].getKey()){table.Arr[j+1]=table.Arr[j];j--;}table.Arr[j+1]=temp;}}0i-1in-1已经有序折半插入排序的算法可描述为:template<classType>voidBinaryInsertSort(sortlist<Type>&table){element<Type>temp;

intleft,right,mid;

for(inti=1;i<=table.CurrentSize-1;i++)

{left=0;right=i-1;temp=table.Arr[i];

while(left<=right)

{//找插入位置

mid=(left+right)/2;if(temp.getKey()<table.Arr[mid].getKey())right=mid-1;

elseleft=mid+1;

}//while

for(intk=i-1;k>=???;k--)//向后移动

table.Arr[k+1]=table.Arr[k];table.Arr[???]=temp;

}//for}//BinaryInsertSort0i-1in-1已经有序leftright折半插入排序的算法可描述为:template<classType>voidBinaryInsertSort(sortlist<Type>&table){element<Type>temp;

intleft,right,mid;

for(inti=1;i<=table.CurrentSize-1;i++)

{left=0;right=i-1;temp=table.Arr[i];

while(left<=right){//找插入位置

mid=(left+right)/2;if(temp.getKey()<table.Arr[mid].getKey())right=mid-1;

elseleft=mid+1;}//while

for(intk=i-1;k>=???;k--)//向后移动

table.Arr[k+1]=table.Arr[k];table.Arr[???]=temp;

}//for}//BinaryInsertSort关于最后的k值的解释:找到插入位置时的最后一次循环条件是left=right,从而mid=left。此时,(1)若temp.getKey()<Arr[mid].key,则left不变(right改变为mid-1),即left=mid,这种情况下(此时temp.getKey()比Arr[mid-1].key肯定要大),待插入结点应该放在mid-1位置后面,即在mid位置上,需要把Arr[i-1]到Arr[mid]的元素依次往后移动,最后的k为mid;

midmid折半插入排序的算法可描述为:template<classType>voidBinaryInsertSort(sortlist<Type>&table){element<Type>temp;

intleft,right,mid;

for(inti=1;i<=table.CurrentSize-1;i++)

{left=0;right=i-1;temp=table.Arr[i];

while(left<=right){//找插入位置

mid=(left+right)/2;if(temp.getKey()<table.Arr[mid].getKey())right=mid-1;

elseleft=mid+1;}//while

for(intk=i-1;k>=???;k--)//向后移动

table.Arr[k+1]=table.Arr[k];table.Arr[???]=temp;

}//for}//BinaryInsertSort关于最后的k值的解释:找到插入位置时的最后一次循环条件是left=right,从而mid=left。此时,(2)若temp.getKey()>=Arr[mid].key,则left改为mid+1(right不变),即left=mid+1,这种情况下(此时temp.getKey()比Arr[mid+1].key肯定要小)

,待插入结点应该放在mid位置后面,即在mid+1位置上,需要把Arr[i-1]到Arr[mid+1]的元素依次往后移动,最后的k为mid+1;mid+1;mid+1折半插入排序的算法可描述为:template<classType>voidBinaryInsertSort(sortlist<Type>&table){element<Type>temp;

intleft,right,mid;

for(inti=1;i<=table.CurrentSize-1;i++)

{left=0;right=i-1;temp=table.Arr[i];

while(left<=right){//找插入位置

mid=(left+right)/2;if(temp.getKey()<table.Arr[mid].getKey())right=mid-1;

elseleft=mid+1;}//while

for(intk=i-1;k>=???;k--)//向后移动

table.Arr[k+1]=table.Arr[k];table.Arr[???]=temp;

}//for}//BinaryInsertSort关于最后的k值的解释:找到插入位置时的最后一次循环条件是left=right,从而mid=left。此时,(1)若temp.getKey()<Arr[mid].key,则最后的k为mid;(2)若temp.getKey()>=Arr[mid].key,则最后的k为mid+1;如何统一？实际上,第(1)种情况的left,mid都不变(只改变right),而且mid=left;

第(2)种情况的left改为mid+1(right和mid都不变),即mid+1=left。因此,不管那种情况,都需要把Arr[left]到Arr[i-1]的元素依次往后移动,最后的k为left;leftleft最后的k(???)是mid还是mid+1?折半插入排序的算法可描述为:template<classType>voidBinaryInsertSort(sortlist<Type>&table){element<Type>temp;

intleft,right,mid;

for(inti=1;i<=table.CurrentSize-1;i++)

{left=0;right=i-1;temp=table.Arr[i];

while(left<=right){//找插入位置

mid=(left+right)/2;if(temp.getKey()<table.Arr[mid].getKey())right=mid-1;

elseleft=mid+1;}//while

for(intk=i-1;k>=left;k--)//向后移动

table.Arr[k+1]=table.Arr[k];table.Arr[left]=temp;

}//for}//BinaryInsertSort

就平均性能而言,因为折半查找优于顺序查找,所以折半插入排序也优于直接插入排序。

折半插入排序的算法只能在顺序表存储结构下实现。折半插入排序是一个稳定的排序方法。9.3.3希尔排序

9.3.3希尔排序

希尔排序(ShellSort)又称为缩小增量排序,它的算法基本思想是:

设排序表中有n个数据元素,首先取一个整数d＜n作为间隔,将全部数据元素分为d个子表,所有相距为d的数据元素放在同一个子表中;

在每一个子表中分别进行直接插入排序;

然后缩小间隔d(例如取d=d/2),重复上述的子表划分和排序工作。如此循环,直到最后d＝1,将所有数据元素放在同一个序列中进行直接插入排序。9.3.3希尔排序

由于开始时d的取值比较大，每个子表里的关键字较少，排序速度较快；等到排序的后期，d的取值逐渐变小，子表中关键字个数逐渐变多，但是由于前面排序工作的基础，大多数关键字已经基本有序，所以排序速度仍然很快。（直接插入排序在关键字基本有序下效率高）。

右图给出了有6个数据元素的排序表进行希尔排序的过程。

第1趟取间隔d＝3,

第2趟将间隔缩小为d＝d/2＝2,

第3趟把间隔缩小为d＝d/2＝1,对整个序列进行直接插入排序,因为最后一趟整个排序表已经达到基本有序,所以排序的效率比较高。

希尔排序算法的C++描述:template<classType>voidShellsort(sortlist<Type>&table){element<Type>temp;intd=table.CurrentSize/2;//d是子表间隔

while(d>0){//循环直到d为