查找排序算法
2021/12/25 14:37:05
本文主要是介绍查找排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#无序表查找 def sequentialSearch(alist , item): pos = 0 found =False while pos < len(alist) and not found : if alist[pos] == item: found = True else: pos = pos+1 return found #有序表查找 def orderSequentialSearch(alist,item): pos =0 found =False stop = False while pos < len(alist) and not found and not stop: if alist[pos] ==item : found =True else: if alist[pos] > item : stop =True else: pos =pos+1 return found #有序表二分查找(循环) def binarySearch_1(alist,item): first =0 last = len(alist) -1 found = False while first <= last and not found : midpoint = (first +last)//2 if alist[midpoint] == item : found = True else: if item < alist[midpoint]: last = midpoint - 1 else: first = midpoint + 1 return found #有序表二分查找(递归) def binarySearch_2(alist ,item): if len(alist) == 0: return False else: midpoint = len(alist)//2 if alist[midpoint] == item: return True else: if item < alist[midpoint]: return binarySearch_2(alist[:midpoint],item) else: return binarySearch_2(alist[midpoint+1:],item) #冒泡排序 def bubbleSort(alist): for passnum in range(len(alist) - 1, 0 , -1 ): for i in range(passnum): if alist[i] > alist[i + 1]: alist[i],alist[i + 1] = alist[i + 1],alist[i] return alist # print(bubbleSort([1,4,2,6,8,44,12])) #冒泡改进 def shortBubbleSort(alist): exhanges = True passnum = len(alist) - 1 while passnum > 0 and exhanges: exhanges = False for i in range(passnum): if alist[i] > alist[i + 1]: exhanges = True alist[i],alist[i + 1] = alist[i + 1],alist[i] return alist # print(shortBubbleSort([1,4,2,6,8,44,12])) #选择排序 def selectionSort(alist): for fillslot in range(len(alist) - 1,0,-1): pasitionOfMax = 0 for location in range(1,fillslot +1): if alist[location] > alist[pasitionOfMax]: pasitionOfMax = location temp = alist[fillslot] alist[fillslot] = alist[pasitionOfMax] alist[pasitionOfMax] = temp return alist # # print( selectionSort([1,4,2,6,8,44,12])) #插入排序 def insertionSort(alist): for index in range(1,len(alist)): currentvalue = alist[index] position =index while position > 0 and alist[position - 1 ] > currentvalue : alist[position] = alist[position - 1] position = position -1 alist[position] = currentvalue return alist # print(insertionSort([1,4,2,6,8,44,12])) #希尔排序 def shellSort(alist): sublistcount = len(alist)//2 while sublistcount > 0: for startposition in range(sublistcount): gapInsertionSort(alist,startposition,startposition) print("After increments of size",sublistcount,"The list is",alist) sublistcount =sublistcount//2 def gapInsertionSort(alist,sart,gap): for i in range(sart + gap,len(alist),gap): currentvalue = alist[i] position = i while position >= gap and alist[position -gap] > concurrent: alist[position] =alist[position - gap] position = position - gap alist[position] = currentvalue #归并排序 def mergeSort(alist): if len(alist) > 1: mid = len(alist)//2 lefthalf = alist[:mid] righthalf = alist[mid:] mergeSort(lefthalf) mergeSort(righthalf) i = j = k = 0 while i < len(lefthalf) and j < len(righthalf): if lefthalf[i] < righthalf[j]: alist[k] = lefthalf[i] i = i + 1 else: alist[k] = righthalf[j] j = j + 1 k = k +1 while i < len(lefthalf): i = i + 1 k = k + 1 while j < len(righthalf): alist[k] = righthalf[j] j = j + 1 k = k + 1 #归并排序,python特性 def merge_sort(lst): if len(lst) <= 1: return lst middle = len(lst) // 2 left = merge_sort(lst[ : middle]) right = merge_sort(lst[middle :]) merged = [] while left and right: if left[0] <= right[0]: merged.append(left.pop(0)) else: merged.append(right.pop(0)) merged.extend(right if right else left) return merged #快排 def quickSort(alist): quickSortHelper(alist,0,len(alist) - 1) def quickSortHelper(alist,first,last): if first < last: splitpoint =partition(alist,first,last) quickSortHelper(alist,first,splitpoint - 1) quickSortHelper(alist,splitpoint + 1,last) def partition(alist,first,last): pivotvalue = alist[first] leftmark = first + 1 rightmark = last done = False while not done: while leftmark <= rightmark and alist[leftmark] <= pivotvalue: leftmark = leftmark + 1 while alist[rightmark] >= pivotvalue and rightmark >= leftmark: rightmark =rightmark - 1 if rightmark < leftmark: done = True else: temp = alist[leftmark] alist[leftmark] = alist[rightmark] alist[rightmark] = temp temp = alist[first] alist[first] = alist[rightmark] alist[rightmark] = temp return rightmark
这篇关于查找排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署