做网站准备什么软件,wordpress网店模板制作,军事新闻头条最新消息,上海城乡住房建设部网站1.顺序查找当数据存储在诸如列表的集合中时#xff0c;我们说这些数据具有线性或顺序关系。 每个数据元素都存储在相对于其他数据元素的位置。 由于这些索引值是有序的#xff0c;我们可以按顺序访问它们。 这个过程产实现的搜索即为顺序查找。顺序查找原理剖析#xff1a;从…1.顺序查找当数据存储在诸如列表的集合中时我们说这些数据具有线性或顺序关系。 每个数据元素都存储在相对于其他数据元素的位置。 由于这些索引值是有序的我们可以按顺序访问它们。 这个过程产实现的搜索即为顺序查找。顺序查找原理剖析从列表中的第一个元素开始我们按照基本的顺序排序简单地从一个元素移动到另一个元素直到找到我们正在寻找的元素或遍历完整个列表。如果我们遍历完整个列表则说明正在搜索的元素不存在。代码实现该函数需要一个列表和我们正在寻找的元素作为参数并返回一个是否存在的布尔值。found 布尔变量初始化为 False如果我们发现列表中的元素则赋值为 True。def search(alist,item):find Falsecur 0while cur len(alist):if alist[cur] item:find Truebreakelse:cur 1return find2.二分查找有序列表对于我们的实现搜索是很有用的。在顺序查找中当我们与第一个元素进行比较时如果第一个元素不是我们要查找的则最多还有 n-1 个元素需要进行比较。二分查找则是从中间元素开始而不是按顺序查找列表。 如果该元素是我们正在寻找的元素我们就完成了查找。 如果它不是我们可以使用列表的有序性质来消除剩余元素的一半。如果我们正在查找的元素大于中间元素就可以消除中间元素以及比中间元素小的一半元素。如果该元素在列表中肯定在大的那半部分。然后我们可以用大的半部分重复该过程继续从中间元素开始将其与我们正在寻找的内容进行比较。#Python学习交流群778463939def search(alist,item):left 0right len(alist) - 1find Falsewhile left right:mid_index (left right)//2if item alist[mid_index]:find Truebreakelse:if item alist[mid_index]:left mid_index 1else:right mid_index -1return find3.冒泡排序原理比较相邻的元素。如果第一个比第二个大就交换他们两个。对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。def sort(alist):length len(alist)for i in range(0,length-1):for j in range(0,length-1-i):if alist[i] alist[i1]:alist[i],alist[i1] alist[i1],alist[i]4.选择排序工作原理第一次从待排序的数据元素中选出最小(或最大)的一个元素存放在序列的起始位置然后再从剩余的未排序元素中寻找到最小(大)元素然后放到已排序的序列的末尾。以此类推直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。#Python学习交流群778463939def sort(alist):length len(alist)for j in range(length-1,0,-1):max_index 0for i in range(1,j1):if alist[max_index] alist[i]:max_index ialist[max_index],alist[j] alist[j],alist[max_index]5.插入排序原理基本思想是每步将一个待排序的记录按其关键码值的大小插入前面已经排序的文件中适当位置上直到全部插入完为止。关键码是数据元素中某个数据项的值用它可以标示一个数据元素。def sort(alist):length len(alist)for j in range(1,length):i jwhile i 0:if alist[i] alist[i-1]:alist[i],alist[i-1] alist[i-1],alist[i]i - 1else:break希尔排序(Shells Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort)是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法的基本思想是先将整个待排元素序列分割成若干个子序列(由相隔某个“增量(gap)”的元素组成的)分别进行直接插入排序然后依次缩减增量再进行排序待整个序列中的元素基本有序(增量足够小)时再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况)效率是很高的因此希尔排序在时间效率比直接插入排序有较大提高。def sort(alist):gap len(alist)//2while gap 1:for j in range(gap,len(alist)):i jwhile i 0:if alist[i] alist[i-gap]:alist[i],alist[i-gap] alist[i-gap],alist[i]i - gapelse:breakgap gap // 26.快速排序基本思想是通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。#Python学习交流群778463939def sort(alist,start,end):low starthigh endif low high:returnmid alist[low]while low high:while low high:if alist[high] mid:high - 1else:alist[low] alist[high]breakwhile low high:if alist[low] mid:low 1else:alist[high] alist[low]breakalist[low] midsort(alist,start,low-1)sort(alist,high1,end)7.归并排序归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。def merge_sort(alist):n len(alist)#结束递归的条件if n 1:return alist#中间索引mid n//2left_li merge_sort(alist[:mid])right_li merge_sort(alist[mid:])#指向左右表中第一个元素的指针left_pointer,right_pointer 0,0#合并数据对应的列表该表中存储的为排序后的数据result []while left_pointer len(left_li) and right_pointer len(right_li):#比较最小集合中的元素将最小元素添加到result列表中if left_li[left_pointer] right_li[right_pointer]:result.append(left_li[left_pointer])left_pointer 1else:result.append(right_li[right_pointer])right_pointer 1#当左右表的某一个表的指针偏移到末尾的时候比较大小结束将另一张表中的数据(有序)添加到result中result left_li[left_pointer:]result right_li[right_pointer:]return resultalist [3,8,5,7,6]print(merge_sort(alist))8.各个算法的时间复杂度
