冒泡,选择,插入
时间复杂度:O(n^2)
空间复杂度:O(1)
冒泡
相邻2个数字进行判断大小并排序
def bubble(list): for i in range(len(list)): exchange = False for j in range(len(list)-i-1): if list[j] > list[j+1]: list[j], list[j+1] = list[j+1], list[j] exchange = True if not exchange: #如果已排好序,则第1趟就能完成,无需继续判断,这样时间复杂度就是O(n) return ll = [5,2,1,6,7,8,3] print(ll) bubble(ll) print(ll)
选择
从左边开始选出一个数,然后与后面一个一个数进行判断,有点类似于冒泡,只不过冒泡是相邻2个,而选择是选出一个与其他所有进行比较
import random print("select------") def select(li): for i in range(len(li)): min1 = i #选出的数的位置 for j in range(i+1,len(li)): if li[j] < li[min1]: min1 = j #如果选出的数大于后面比较的数,则将选出的位置的数变成后面那个数的位置 li[min1], li[i] = li[i], li[min1]#将选出的数与后面那个数交换位置 lll = list(range(10)) random.shuffle(lll) print(lll) select(lll) print(lll)
插入
从第2个数字开始选出来,然后与前面的数字进行比较,前面若小于这个数字说明正常且前面的数字往右移,也就是选出的数字的位置会被前一个数字占了,前一个数字又被前前个数字占了,直到选出的这个数字大于前面比较的那个数字则位置由选出的数字来占,然后这一趟结束进行下一趟
import random def insert(list): for i in range(1,len(list)): key = list[i] #选出的数字,把它拿出来 j = i - 1 #前面的一个数字 while j >= 0 and key < list[j]: 在改变的情况下,也就是比较的数字都比选出的数字大 list[j+1] = list[j] #位置右移 j -= 1 list[j+1] = key llll = list(range(10)) random.shuffle(llll) print(llll) insert(llll) print(llll)