Python 插入法是一種常見的算法排序方法,該方法可以將一個數組或列表按照大小順序排列。該算法的基本思想是將未排序的元素從未排序的部分中取出一個值,然后插入到已排序的部分中的適當位置。
算法實現如下:
def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i-1 while j >=0 and key< arr[j] : arr[j+1] = arr[j] j -= 1 arr[j+1] = key arr = [12, 11, 13, 5, 6] insertion_sort(arr) print ("排序后的數組:") for i in range(len(arr)): print ("%d" %arr[i])
在該算法的實現中,使用兩個嵌套循環,一個循環從1開始到n-1,另一個循環是在排序好的區間中,將比新元素大的元素右移一個位置,直到找到合適的位置插入新元素。
該算法的優缺點:
優點:該算法的時間復雜度為O(n^2),空間復雜度為O(1),插入排序算法的空間復雜度較低, 對于小規模數據排序效率較高。
缺點:對于大規模或已經有序的數據集合,排序效率不高,需要大量移動元素。
上一篇html常見代碼