数据结构排序讲解.ppt

8.3交换排序冒泡排序排序过程：将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].keyr[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被放在最后。对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被放在第n-1个位置。重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。0102例3849657613273097第一趟38496513273076第二趟384913273065第三趟3813273049第四趟13273038第五趟132730第六趟4938659776132730初始关键字n=8384976971397279730971376767627301365276530651313494930492738273830381327第七趟排序后序列为：1327303849657697排序过程：首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换。再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换。重复上述两步，直至i=j为止。基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设rp=r[s]，x=rp.key。初始时令i=s,j=t。再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止。快速排序例：初始关键字：4938659776132750ijji完成一趟排序：(273813)49(76976550)分别进行快速排序：(13)27(38)49(5065)76(97)快速排序结束：13273849506576974927ijijij4965ji1349ij4997ijx=498.4选择排序简单选择排序首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换。

再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换。

重复上述操作，共进行n-1趟排序后，排序结束。排序过程：例：初始：[49386597761327]kjjjjjjkki=11349三趟：1327[6597764938]四趟：132738[97764965]五趟：13273849[769765]六趟：1327384965[9776]132738496576[97]排序结束：13273849657697二趟：13[386597764927]i=2kkjjjjj2738或(i=1,2,…...?n/2?)ki?k2iki?k2i+1ki?k2iki?k2i+1例：

（96，83，27，38，11，9）例：

（13，38，27，50，76，65，49，9