冒泡算法
冒泡算法 简介
冒泡算法是种直观而又简单的算法,给定一组共有n个元素的序列,对序列中的每个相邻元素进行比较,若右边的大于左边则进行交换。在第一轮遍历后,序列中最大的元素会被置于末尾。总共遍历n-1轮。
对于有n个元素的序列,冒泡算法总共需要进行遍历序列:n + n-1 + n-2 + …. + 1 = \(\frac{(n+1)n}{2}\)
对于最好的情况,当序列都为正序:此时需要做0次交换
对于最差的情况,当序列都为逆序:此时需要做 n-1 + n-2 + …+ 1 = \(\frac{n(n-1)}{2}\) 次交换。
平均交换次数为:\(\frac{n(n-1)}{4}\)
显然时间复杂度为:O(\(n^2\))
空间复杂度:O(1)
冒泡排序代码
def buble_sort(unsorted_list):
for i in range(len(unsorted_list)):
#注意序列长度,此时索引j的范围需要-1
for j in range(0,len(unsorted_list)-i-1):
if(unsorted_list[j] > unsorted_list[j+1]):
unsorted_list[j],unsorted_list[j+1] = unsorted_list[j+1],unsorted_list[j]
return unsorted_list
选择排序
选择排序 简介
选择排序是在每轮遍历序列中找出它们当中最小的元素,然后与首位的元素进行交换。当一轮遍历完后,将指向首位的指针向后移动。与冒泡排序相似的是,选择排序同样会重复n-1轮遍历。每次遍历的元素个数从n开始递减。但与冒泡排序不同的是,在每轮遍历中选择排序会找到最小的数,而冒泡排序会找到最大的。
总共遍历次数,最好、最差情况时交换次数都于冒泡排序相同。
平均交换次数同样为:\(\frac{n(n-1)}{4}\)
时间复杂度:O(\(n^2\))
空间复杂度:O(1)
选择排序代码
def full_select(unsorted_list):
length = len(unsorted_list)
for i in range(0,length):
#初始时最小元素为首位元素
min_index = i
min_num = unsorted_list[min_index]
for j in range(i + 1, length):
#每轮遍历找到最小元素并暂存
if (min_num > unsorted_list[j]):
min_index = j
min_num = unsorted_list[min_index]
unsorted_list[i],unsorted_list[min_index] = unsorted_list[min_index],unsorted_list[i]
return unsorted_list
插入排序
插入排序 简介
插入排序与斗地主排序扑克牌类似。它优先构建一个有序序列,当新的元素增加时,从后向前扫描有序序列找到新元素所在位置并将其插入。它虽比冒泡排序和选择排序更抽象一点,但原理仍然直观。
对于最好的情况,当序列都为正序:此时需要做0次操作
对于最差的情况,当序列都为逆序:此时需要做1+2+3+…+n-1 = \(\frac{n(n-1)}{2}\) 次操作。
平均操作仍为:\(\frac{n(n-1)}{4}\) 次
这里的操作包含了寻找合适位置时的遍历以及后续的插入。
所以插入排序的时间复杂度为:O(\(n^2\)) 空间复杂度为:O(1)
插入排序代码
def insert_sort(input_list):
input_length = len(input_list)
for i in range(input_length-1):
j=i+1
#从有序序列中查找位置
for k in range(j):
if(input_list[k]<input_list[j]):continue
#插入操作
else:
tmp = input_list[j]
input_list.pop(j)
input_list.insert(k,tmp)
return input_list