数据结构排序PPT课件教学内容.ppt

《数据结构排序PPT课件教学内容.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构排序PPT课件9.1插入排序9.1.1直接插入排序它的基本操作是在处理第i个记录时，前面1到i-1记录已排成有序，将第i个记录插入有序表中，得到一个新的有序表，表的长度加1。当表中只有一个记录时，该表已是有序表，所以，可以从第二个记录开始，逐个插入记录，直至处理完待排序序列的所有记录。直接插入排序的时间复杂度为O(n2)，并且是一种稳定排序。当n较小时，排序的效率较高，是一种常用的排序方法处理记录号插入位置下标0123456i=1j=0[91]673562297246i=2j=0[6791]3562297246i=3j=0[356791]62297246i=4j=1[3562

2、6791]297246i=5j=0[2935626791]7246i=6j=4[293562677291]46i=7j=2[29354662677291]图9.1直接插入排序示例例如，有一组关键字序列为{91,67,35,62,29,72,46}，直接插入排序过程如图9.1所示。用C语言描述的直接插入排序算法如下：typedefstruct{intkey;…/*其他域*/}NODE;算法9.1直接插入排序算法。voidInsertSort(NODEarray[],intn)/*对存放在数组array[]中，长度为n的序列排序*/{inti,j;NODEx;for(i=1;i

3、+){x=array[i];j=i-1;while(j>=0&&x.key

4、，这样，在排序中记录移动的次数就少，排序的效率也就高。最后一趟是步长为1，即：对整个序列直接插入排序，但这时整个序列已基本有序，只要做少量记录移动，就可将该序列排成有序。图9.2希尔排序示例例如，有8个关键字序列为{91,67,35,62,29,72,46,57}，插入排序的步长序列为4,2,1。希尔插入排序过程如图9.2。步长序列的选择没有严格的规定，只要该序列{d1,d2,…,dt}满足d1>d2>…>dt，并且当t≥1时，d1=1，该序列都可选作步长序列。一般采用步长序列为d1=n/2，di+1=di/2(n为待排序序列的长度)。用C语言描述的希尔排序算法如下：算法9.2希尔排

5、序算法。voidShellSort(NODEarray[],intn)/*对存放在数组array[]中，长度为n的序列希尔排序*/{inti,j,step;NODEx;for(step=n/2;step>0;step=step/2)/*step不断变小，直至为1*/{for(i=step;i=0&&x.key

6、是一种不稳定排序9.2交换排序交换排序基本思想：比较二个待排序记录的关键字，若为逆序，则交换位置，反之，保持原序。9.2.1冒泡(简单交换排序)冒泡排序的方法是：首先比较array[n-1].key和array[n-2].key，若为逆序则交换之，然后比较array[n-2].key和array[n-3].key，依此类推，直到比较array[1].key和array[0].key，称为一趟“冒泡”，其结果是将具有最小关键字的记录排到序列的第1个位置上。然后再array[n-1]到array[1]之间进行一趟“冒泡”，将具有次小关键字的记录排到序列的第2个位置上。依此类推，直到第n-

7、1趟，在array[n-1]和array[n-2]之间进行“冒泡”后，待排序序列已排成有序。下一趟区间下标0123456初始关键字[6，0][91673562297246]第一趟冒泡后[6，1]29[916735624672]第二趟冒泡后[6，2]2935[9167466272]第三趟冒泡后[6，3]293546[91676272]第四趟冒泡后[6，4]29354662[916772]第五趟冒泡后[6，5]2935466267[9172]第六趟冒泡后序列有