数据结构课件

数据结构课件内部排序第一讲2004年12月第十章内部排序插入排序:直插入排序,希尔排序交换排序:冒泡排序，霍尔快速排序选择排序:简洁选择排序，堆排序归并排序基数排序§10-1排序的基本概念一、排序：将若干数据元素构成的一个随意序列，重新排成按关键字有序序列的过程。二、关于排序的稳定性：若排序之前Ki=Kj,并且Ri领先Rj（i<j），排序后仍Ri领先于Rj，则排序是稳定的，否则排序是不稳定的。三、排序方法分类：1内排序:在内存进行;2外排序:在内存进行，同时访问外存;§10-1排序的基本概念四、存储结构：依次存储结构,常称为表。#defineMAXSIZE30;/*表中记录的个数*/Typedefstruct{intkey；/*或其他类型*/.../*其他次关键字域*/}ElemType;typedefElemTypelisttp[MAXSIZE]；§10-2插入排序一、干脆插入排序：思路:通过不断的将某记录插入到一个已经有序的表中来实现。有一组关键字{49，38，76，27，49};

i=2(49)38,76,27,49┏━┛

i=3(38,49),76,27,49

i=4(38,49,76),27,49┏━━━━━┛i=5(27,38,49,76),49┏━┛

end.(27,38,49,49,76)-干脆插入排序算法voidstraisort(listtpr);{for(i=2;i<=n;i++)

{r[0]=r[i];/*设置监视哨*/

j=i-1;k=r[i].key;while(r[j].key>k)/*大值的记录后移*/

{

r[j+1]=r[j];j--;

}

r[j+1]=r[0];/*插入位置*/

}

}/*straisort*/

-干脆插入排序算法算法分析：排序是稳定的;原来：（49，38，76，27，49）排序后：(27,38,49,49,76)

排时间困难度为：T(n)=O(n2)§10-3交换排序一、起泡排序(由小到大）思路:第1趟aj与aj+1比,较大数=>aj+1(j=1,...n-1）

第2趟aj与aj+1比,较大数=>aj+1(j=1,...n-2)

第n-1趟a1与a2比,较大数=>a2(j=1,n-(n-1))一、起泡排序(由小到大）算法描述：（1）voidbuble_sort(listtpr){for(i=1;i<=n-1;i++)

/*共计n-1趟*/

for(j=1;j<=n-i;j++)if(r[j].key>r[j+1].key)

{

x=r[j];r[j]=r[j+1]r[j+1]=x;}

}/*bubble_sort*/

起泡排序实例图示：

排序表长度n=8初始状态第1趟后第2趟后第3趟后第4趟后第5趟后第6趟后4938383838131338494949132727

656565132738389776132749

4949

76132749

49

49

49132749

65656565

2749

7676767676

49

97

9797979797起泡排序改进方法（2）Voidbubble_sort2(listtpr){i=1;

do{

bool=1;

for(j=1;j<=n-i;j++)if(r[j].key>r[j+1].key)

{

x=r[j];r[j]=r[j+1];r[j+1]=x;bool=0;

}

i++;

}while(bool==0&&i<=n-1);

}/*bubble_sort2*/当某一趟仅有比较而多数据交换，表明序列已经有序。可以结束排序过程。起泡排序算法分析时间困难度：一般状况下：T(n)=0(n2)当原始序列有序是：T(n)=0(n)起泡排序算法是稳定的。

排序算法小结:干脆插入排序稳定，时间困难度为：0(n2)

交换排序的起泡排序是稳定，一般，时间困难度为：0(n2)当原始序列有序，时间困难度为：0(n)上一讲内容回顾

排序基本概念插入排序干脆插入排序稳定T(n)=O(n2)希尔排序不稳定T(n)=n1.3交换排序起泡排序稳定T(n)=O(n2)原表有序时T(n)=O(n)本讲内容交换排序起泡排序稳定T(n)=O(n2)快速排序不稳定T(n)=O(n.log2n)选择排序简洁选择排序稳定T(n)=O(n2)堆排序不稳定T(n)=O(n.log2n)§10.3交换排序二、霍尔快速排序

存储结构：依次存储结构,常称为表。#defineMAXSIZE30;/*表中记录的个数*/Typedefstruct{intkey；/*或其他类型*/.../*其他次关键字域*/}ElemType;typedefElemTypelisttp[MAXSIZE]；1.霍尔快速排序思路（1）以r[1].key为枢轴，经过比较将:

r[1]，r[2],………,r[n]分成两个子表：

[.....ki.....]k1[.....kj.....],左子表关键字<k1