第6讲 排序.ppt

第六讲 排序 直接插入排序 排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。 这种算法主要时间花在什么上？ 算法时间复杂度是多少？ O(n2) 算法空间复杂度是多少？ 一个数组 折半插入排序 直接插入算法简单，但数据量大时比较次数增加 可利用有序区“有序”的特点，使用折半查找法寻找插入位置 希尔排序（缩小增量排序） 直接插入排序当序列基本有序时效率较高 希尔排序是将待排序序列划分成若干组 在每个组内进行排序 经过多次分组排序后，序列基本有序 将序列进行一次直接插入排序 见课本p198例题 冒泡排序 从后向前依次比较相邻两元素，若a[i+1]a[i]则交换，使值较小的元素从下面一直往上“冒”。每一次排序都把最小的元素“冒”在最上面。 17 3 3 3 17 14 25 14 17 14 25 20 20 20 25 什么情况下算法结束？ 不再交换时 这种算法主要时间花在什么上？ 算法时间复杂度是多少？ O(n2) 算法空间复杂度是多少？ 一个数组 快速排序 取待排序列中的第一个元素做基准，通过一趟排序，将待排序记录分割成独立的两部分，左边部分均=基准，右边部分均基准。然后分别对这两部分继续进行排序，以达到整个序列有序 排序过程：对r[s..t]中记录进行一趟快速排序，附设两个指针i和j 初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于x的记录，并和r[i]交换 再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和r[j]交换 重复上述两步，直至i==j为止 再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止 有什么地方可以改进的吗？ 初始： 17 3 25 14 20 第一次：17 3 25 14 20 第二次：14 3 25 20 第三次：14 3 25 20 第四次：14 3 25 20 第五次（14 3） 17 （25 20） 对左序列和右序列继续递归排序，直到每个序列只剩下一个元素为止。 算法时间复杂度：nlog2n 算法空间复杂度：一个数组 当序列杂乱无章时，快速排序是目前为止最快的排序算法 简单选择排序 思想：首先从1~n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2 个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。 时间复杂度为O(n2)， 适用于待排序元素较少的情况。 二路归并排序 将两个或两个以上的有序表组成一个新的有序表。 把具有n个记录的表看成是n个有序的子表，每个子表的长度为1，然后两两归并，得到[n/2]个长度为2或为1的有序子表；再两两归并，如此重复，直到得到一个长度为n的有序表为止。 归并过程是二叉树从叶到根的过程，所以归并的次数就是二叉树的高度。 每趟归并后需要复制记录次数为n次 算法时间复杂度：nlog2n 算法空间复杂度：二个数组 * * 例 49 38 65 97 76 13 27 i=2 (38 49) 65 97 76 13 27 i=3 (38 49 65) 97 76 13 27 i=4 (38 49 65 97) 76 13 27 i=5 (38 49 65 76 97) 13 27 i=6 (13 38 49 65 76 97) 27 i=1 ( ) (13 27 38 49 65 76 97) 排序结果： i=7 (13 27 38 49 65 76 97) 初始 第一次 第二次 i j i j i j i j i j 下图是对下列序列实现二路归并的过程实例。 ??42 20 17 13 28 14 23 15 50 3