算法 - 亿夏网

时间复杂度：用来估计算法运行时间的一个式子。时间复杂度高的算法比时间复杂度低的算法慢

空间复杂度：用来评估算法内存占用大小的一个式子。

n位数的水仙花数

list2=[]
for i in range(10**(n-1),10**n):
  str1=str(i)
  sum1=0
  for j in str1:
    num=int(j)
    sum1+=num**n
  if i==sum1:
    list2.append(i)
print(list2)

冒泡排序:列表每相邻的数，如果前边的比后边的大，交换两个数。

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)

算法

相关推荐