資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法律學Python 二分插入排序程式
本文將介紹針對以下問題陳述提出的解決方案。
問題陳述 − 已有一個數組，我們需要使用二分插入排序的概念對其進行排序。
正如名稱所示，我們結合了二分搜尋和插入排序演算法的概念。
下面讓我們觀察一下實現中的解決方案 −
示例
# sort
def insertion_sort(arr):
for i in range(1, len(arr)):
temp = arr[i]
pos = binary_search(arr, temp, 0, i) + 1
for k in range(i, pos, -1):
arr[k] = arr[k - 1]
arr[pos] = temp
def binary_search(arr, key, start, end):
#key
if end - start <= 1:
if key < arr[start]:
return start - 1
else:
return start
mid = (start + end)//2
if arr[mid] < key:
return binary_search(arr, key, mid, end)
elif arr[mid] > key:
return binary_search(arr, key, start, mid)
else:
return mid
# main
arr = [1,5,3,4,8,6,3,4]
n = len(arr)
insertion_sort(arr)
print("Sorted array is:")
for i in range(n):
print(arr[i],end=" ")輸出
Sorted array is : 1 3 3 4 4 5 5 6 8
所有的變數都在本地範圍內宣告，其引用在上圖中可以看到。
結論
本文介紹瞭如何編寫 Python 二分插入排序程式。
更新於： 2019年12月20日
1K+ 次瀏覽
廣告