时间复杂度:用来估计算法运行时间的一个式子。时间复杂度高的算法比时间复杂度低的算法慢
空间复杂度:用来评估算法内存占用大小的一个式子。
冒泡排序:列表每相邻的数,如果前边的比后边的大,交换两个数。
def Bubble_sort(li): for i in range(len(li)-1): for j in range(len(li)-1-i): if li[j] > li[j+1]: li[j],li[j+1] = li[j+1],li[j] li = [7,5,4,6,3,8,2,9,1] Bubble_sort(li) print(li)
时间复杂度:O(n*n)
选择排序:一趟遍历记录最小的数,放到第一个位置
def select_sort(li): for i in range(len(li)): minLoc = i for j in range(i+1, len(li)): if li[j] < li[minLoc]: li[j],li[minLoc] = li[minLoc],li[j] li = [7,5,4,6,3,8,2,9,1] select_sort(li) print(li)
时间复杂度:O(n*n)
插入排序:列表被分为有序区和无序区,最初有序区只有一个元素,每次从无序区选择一个元素,插入到有序区的位置,直到无序区变空。
def insert_sort(li): for i in range(1, len(li)): tmp = li[i] j = i - 1 while j >= 0 and li[j] > tmp: li[j+1] = li[j] j = j - 1 li[j+1] = tmp li = [7,5,4,6,3,8,2,9,1] insert_sort(li) print(li)
时间复杂度:O(n*n)
快速排序:取一个元素P,使元素P归位,列表被p分成两部分,左边都比p小,右边都比p大。
def partition(li, left, right): tmp = li[left] while left < right: while left < right and li[right] >= tmp: right = right - 1 li[left] = li[right] while left < right and li[left] <= tmp: left = left + 1 li[right] = li[left] li[left] = tmp return left def quick_sort(li, left, right): if left < right: mid = partition(li,left,right) quick_sort(li,left,mid-1) quick_sort(li,mid+1,right) li = [7,5,4,6,3,8,2,9,1] quick_sort(li,0,8) print(li)