数据结构与算法--排序
2021/9/13 22:37:12
本文主要是介绍数据结构与算法--排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
常见排序算法效率
冒泡排序
def bubble_sort(alist): """冒泡排序""" n = len(alist) for j in range(n-1): count = 0 for i in range(0, n-1-j): # 班长从头走到尾 if alist[i] > alist[i+1]: alist[i],alist[i+1] = alist[i+1], alist[i] count += 1 if 0 == count: return # [1, 2,3 ,4 ,5, 6] # i 0 ~ n-2 range(0, n-1) j=0 # i 0 ~ n-3 range(0, n-1-1) j=1 # i 0 ~ n-4 range(0, n-1-2) j=2 # j=n i range(0, n-1-j) if __name__ == "__main__": li = [54, 26, 93, 17, 77, 31, 44, 55, 20] print(li) bubble_sort(li) print(li) # for j in range(len(alist)-1,0,-1) # # [n-1, n-2, n-3, n-4,..., 1] # for i in range(j) # # [0, 1, 2, 3,...,n-2] # for i in range(n-1-j)
快速排序
def quick_sort(alist, first, last): """快速排序""" if first >= last: return mid_value = alist[first] low = first high = last while low < high: # high 左移 while low < high and alist[high] >= mid_value: high -= 1 alist[low] = alist[high] while low <high and alist[low] < mid_value: low += 1 alist[high] = alist[low] # 从循环退出时,low==high alist[low] = mid_value # 对low左边的列表执行快速排序 quick_sort(alist, first, low-1) # 对low右边的列表排序 quick_sort(alist, low+1, last) if __name__ == "__main__": li = [54, 26, 93, 17, 77, 31, 44, 55, 20] print(li) quick_sort(li, 0, len(li)-1) print(li) ``` # 二分查找法 # [17, 20, 26, 31, 44, 54, 55, 77, 93] # mid = n/2 # # [17, 20, 26, 31] # mid = n/2
二分查找法
def binary_search(alist, item): """二分查找,递归""" n = len(alist) if n > 0: mid = n//2 if alist[mid] == item: return True elif item < alist[mid]: return binary_search(alist[:mid], item) else: return binary_search(alist[mid+1:], item) return False def binary_search_2(alist, item): """二分查找, 非递归""" n = len(alist) first = 0 last = n-1 while first <= last: mid = (first + last)//2 if alist[mid] == item: return True elif item < alist[mid]: last = mid - 1 else: first = mid + 1 return False if __name__ == "__main__": li = [17, 20, 26, 31, 44, 54, 55, 77, 93] print(binary_search(li, 55)) print(binary_search(li, 100)) print(binary_search_2(li, 55)) print(binary_search_2(li, 100))
这篇关于数据结构与算法--排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?