数据结构基础知识05--高考信息技术一轮，二轮复习 数据结构基础知识（浙教版2019）

数据结构基础知识（五） 【知识要点】 1、 冒泡排序（要求：熟练掌握） 1) 工作原理：每次检查相邻两个元素，如果前后元素不满足升序(降序)就将相邻两个元素交换，当没有相邻元素需要交换时，排序就完成了。经i轮排序扫描，第i大(小)的数会被冒泡到数列的前面或后面 2) 稳定性：冒泡排序是一种稳定的排序算法 3) 时间复杂度：O(n2) def bubble_sort(a): #冒泡排序(升序)     for i in range(1,len(a)):   #比较轮数=len-1         for j in range(len(a)-i): #当前比较位置             if a[j]>a[j+1]:                 a[j],a[j+1]=a[j+1],a[j]     return a a = [7, 8, 0, 1, 6, 3, 9, 4, 5, 2] print(bubble_sort(a)) 我们发现最后两轮冒泡时已经有序，可以直接退出循环以提升算法效率 def bubble_sort(a): #冒泡排序优化     for i in range(1,len(a)):      #比较轮数=len-1         flag = True #flag初始状态         for j in range(len(a)-i):  #当前比较位置             if a[j]>a[j+1]:                 a[j],a[j+1]=a[j+1],a[j]                 flag = False #发生交换则标记flag         if flag: break #若一轮都未发生交换则说明已经有序     return a a = [7, 8, 0, 1, 6, 3, 9, 4, 5, 2] print(bubble_sort(a)) 2、 选择排序（要求：熟练掌握） 1) 工作原理：每次找出第i小(大)的元素，然后将这个元素和第i个位置元素交换 2) 稳定性：一般的认为选择排序是一种不稳定的算法 3) 时间复杂度：O(n2) def selection_sort(a): #选择排序(升序)     for i in range(len(a)-1):         ith = i         for j in range(i+1,len(a)):             if a[ith]>a[j]:                 ith = j     #找到第i小的值位置         a[ith],a[i]=a[i],a[ith]     return a a = [6, 7, 5, 8, 2, 1, 4, 0, 3, 9] print(selection_sort(a)) 3、 插入排序（要求：熟练掌握） 1) 工作原理：将待排元素分为“已排序”和“未排序”两个部分，每次从未排序部分中取出一个元素放到已排序中。 2) 稳定性：插入排序是一种稳定的算法 3) 时间复杂度：最优O(n)，最差O(n2) def insertion_sort(a): # 插入排序(升序)     for i in range(1,len(a)):   #小于i的为有序部分,i~len-1为无序部分         val = a[i]         #无序部分取值         pos = i-1         while pos>=0 and a[pos]>val:   #在有序部分寻找插入位置             a[pos+1] = a[pos]       #逐位后移             pos -= 1         a[pos+1] = val     #将值插入有序部分     return a a = [6, 0, 9, 5, 8, 3, 4, 7, 1, 2] print(insertion_sort(a)) 4、 桶排序（要求：理解运行过程） 1) 工作原理：桶排序也并非常规的排序算法，它实际上是一种分治思想的实践。桶排序的过程可以分为4步：1.根据数据的特征将数据分为若干的桶，给每个桶规定可以存储的值的范围；2.将原数列的数据放入各个桶中；3.对每个桶都进行排序；4.按照桶的顺序将桶内数据重新链接。注意区分桶排序，归并排序，快速排序的区别。 2)稳定性：桶排序的稳定性取决与其内层排序的排序算法 3)时间复杂度：O(n2) # 桶排序 def bucket_sort(a):     bucke