算法的简单的概念

算法的概念：

O()大O表示法

O(): 程序大概运行的次数

1，时间复杂度：

时间复杂度是用来估计算法运行时间的一个式子（单位）。

常见的时间复杂度（按效率排序）

O(1)<O(logn)<O(n)<O(nlogn)<O(n**2)<O(n**2logn)<O(n**3)

前四种较重要。

2，空间复杂度：

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

列表排序：

排序low b三人组：

冒泡排序

每两个相邻的数比较，如果对比一个数比一个大，交换位置。

def Bubble_Sort(li):

for i in range(len(li)):

for j in range(len(li)- i - 1):

if li[j] > li[j+1]:

li[j], li [j+1] = li[j+1], li[j]

li = [7,2,4,5,2,1,8,9]

Bubble_Sort(li)

print(li)

选择排序:

拿出一个数假设为最小的数，再随机选一个数，大的就放在后面，小的就交换位置。

def select_sort(li):

for i in range(len(li)-1):

minLoc = i

for j in range(i+1, len(li)-1)

if li[j] < li[minLoc]:

li[j], li[minLoc] = li[minLoc] ,li[j]

插入排序:

列表被分为有序区和无序区两个部分，最初有序区室友只有一个元素

每次从无序区选择一个元素， 插入到有序区的位置，直到无序区变空

def insert_sort(li):

for i in range(1, len(li)):

tmp = li[i]

j = i-1

while i >= 0 and tmp <li[j]:

li[j+1] = li[j]

j = j-1

li[j+1] = tmp

快速排序：*******

取一个元素p（第一个元素），使元素p归为；

列表被p分成两个部分，左边都比p小，右边都比p大；

递归完成排序

def partition():

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):

if left < right:

mid = partition(li, left, right)

quick_sort(li , left, mid -1)

quick_sort(li, mid+1, right)

排序NB二人组：

堆排序

归并排序

没什么人用的排序：

基本排序

希尔排序

桶排序