《算法设计与分析》课件 第2章 排序

算法设计与分析排序排序比较排序冒泡排序堆排序插入排序归并排序线性排序桶排序计数排序基数排序1.1冒泡排序冒泡排序和选择排序很相似，但冒泡排序是每次都选择一个最大的元素，在第i次循环中，冒泡排序从未排序的元素中选择一个最大的元素，并将其放在倒数第i个位置。比较：通过依次对两两相邻的元素进行比较1.1冒泡排序一次冒泡过程1.1冒泡排序1.1冒泡排序和选择排序比较1.2堆排序将元素组织成堆结构，然后每次取堆顶元素1.2堆排序将元素组织成堆结构，然后每次取堆顶元素1.2堆排序将元素组织成堆结构，然后每次取堆顶元素1.2堆排序1.2堆排序是否稳定排序？1.3插入排序每次都从剩余的元素中取第一个元素，将其插入到前面已经排序好的序列中，使得插入后的序列依然是排序好的序列1.3插入排序1.3插入排序复杂度计算：插入排序是稳定排序1.3插入排序平均复杂度：有没有可能将插入排序的复杂度降低?1.3插入排序：希尔排序为了减少比较次数，可以跳着比，比如每隔4个元素比较一次1.3插入排序：希尔排序1.3插入排序：希尔排序1.3插入排序：希尔排序1.3插入排序：希尔排序1.3插入排序：希尔排序1.3插入排序：希尔排序1.4归并排序（合并排序）二路归并将两个已经排序好的数组(如数组A和数组B)进行合并，合并后的数组依然是排序好的1.4归并排序二路归并1.4归并排序归并排序1.4归并排序多路归并排序如4路归并算法，和2路归并比较1.4归并排序多路归并排序如4路归并算法，和2路归并比较1.4归并排序多路归并排序如4路归并算法，和2路归并比较1.4归并排序多路归并排序如4路归并算法，和2路归并比较1.4归并排序多路归并排序如4路归并算法，和2路归并比较有没有可能降低比较次数?1.4归并排序多路归并排序如4路归并算法，和2路归并比较1.4归并排序多路归并排序1.4归并排序多路归并排序1.4归并排序多路归并排序1.4归并排序基于锦标赛的多路合并在对k个排序好的子数组进行合并时，利用了一种联赛的机制来选取最小值。1.4归并排序胜者树1.4归并排序基于胜者树的合并算法1.4归并排序败者树1.4归并排序基于败者树的合并算法1.4归并排序基于败者树的合并算法2线性排序比较排序所能达到的最优复杂度为O(nlog

n)能进一步降低排序的复杂度吗？非比较排序只适合特定的场景2.1桶排序桶排序的基本步骤2.1桶排序几个问题2.1桶排序几个问题如果去比较一个元素是否属于某个桶，则分发的复杂度为O(mn)。为了直接得出一个元素属于哪个桶，需要计算元素所对应桶的下标。这个可以用前面任一复杂度为O(nlogn)的比较排序2.1桶排序算法2.1桶排序例子2.1桶排序2.2计数排序基本思想2.2计数排序问题2.2计数排序算法设置两个数组B和C，其中B用于存放排序好的数组，而C起着计数的作用(也就是‘桶’的作用)。第一个for循环(语句4-6)对C进行初始化第二个for循环(语句7-9)统计每个元素的个数第三个for循环(语句10-12)就是依次对数组C中第1个元素开始到最后一个进行累加，其作用是统计某个元素前共有多少个元素。第四个for循环(语句13-16)从A数组的最后一个元素开始，通过C数组中对应的值确定其在B数组中的位置。2.2计数排序算法2.2计数排序2.3基数排序基本思想2.3基数排序流程2.3基数排序例子2.3基数排序问题：需要对‘位’上的数据进行排序，