数据结构与算法之排序(冒泡,选择,插入)
为什么学习数据结构与算法:
计算机重要的几门课:
1.数据结构和算法
2.网络
3.操作系统
4.计算组成原理
数据结构与算法:
算法:
衡量算法的标准:
时间复杂度:就是程序代码执行的大概次数
小结:
时间复杂度是用来估计算法运行时间的一个式子(单位)
一般来说,时间复杂度高的算法比复杂度低的算法慢
-
常见的时间复杂度(按效率排序)
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)< O(n^2logn)< O(n^3)
-
不常见的时间复杂度(看看就好)
O(n!) O(2^n) O(n^n) ....
-
如何一眼判断时间复杂度
1.循环减半的过程 --> O(logn) 比如二分查找
2.几次循环就是n的几次方的复杂度
空间复杂度:用来评价算法内存占用大小的一个式子
空间换时间
二分查找: 用到递归法
def binarySearch(lis,low,high,val):
if low < high:
mid = (low+high)//2
if lis[mid] == val:
return mid
elif lis[mid] > val:
binarySearch(lis,low,mid,val)
elif lis[mid] < val:
binarySearch(lis,mid+1,high,val)
else:
return -1
数据结构
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：
Data_Structure=(D,R)
其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。
冒泡排序法
冒泡排序法就是: 首先每两个相邻的数,如果前边的比后边的大,那么交换这两个数,每一次都会把最大的数往后排
# 冒泡排序法
# 生成10个在34内的随机数,然后进行排序
import random
lis = list()
for i in range(10):
a = random.randint(1, 34)
lis.append(a)
# print(lis)
# 时间复杂度 O(n^2)
def BubbleSort(lis):
for i in range(len(lis)):
flag = False # 当接收到已经排过序,就无需再多来几次后面的循环
for j in range(len(lis)-i-1):
if lis[j] > lis[j+1]:
lis[j], lis[j+1] = lis[j+1], lis[j]
flag = True
if not flag:
return
BubbleSort(lis)
print(lis)
选择排序法
选择排序法就是:
- 一趟遍历记录最小的数放到第一个位置
- 再一趟遍历记录剩余列表中最小的 数,继续放置
# 选择排序法
# 就是把最小的数往前排
# 时间复杂度 O(n^2)
def SelectSort(lis):
for i in range(len(lis)):
for j in range(i+1, len(lis)):
if lis[j] < lis[i]:
lis[j], lis[i] = lis[i], lis[j]
SelectSort(lis)
print(lis)
插入排序法
插入排序法就是:
- 列表被分为有序区和无序区两个部分,最初有序区只有一个元素
- 每次从无序区选择一个元素,插入到有序区的位置,直到无序区变空
# 插入排序法
# 时间复杂度 O(n^2)
def insertsort(lis):
# 默认第一个数在有序区,从第二个开始找
for i in range(1, len(lis)):
j = i-1
while j >= 0 and lis[j] > lis[j+1]:
lis[j], lis[j+1] = lis[j+1], lis[j]
j -= 1
insertsort(lis)
print(lis)
# 我觉得插入排序还可以用for循环
# 时间复杂度 O(n^2)
def insertsort1(lis):
for i in range(1,len(lis)):
for j in range(i):
if lis[j]>lis[i]:
lis[i],lis[j]=lis[j],lis[i]
insertsort1(lis)
print(lis)
这些是比较常见的排序