'''
常见的排序算法
插入排序，希尔排序，直接排序，堆排序
冒泡排序，快速排序，归并排序，基数排序

给定一个列表，将列表进行排序，时间复杂度小于 O(n^2)
复杂度
1，时间复杂度：指算法在计算过程中所需要的计算工作量
2，空间复杂度：指算法在计算过程中所需要的内存空间

常见的时间复杂度
常数阶 O(1)，对数阶O(log2n)，线性阶O(n)
线性对数阶O(nlog2n),平方阶O(n^{2),立方阶O(n}3)
随着问题的规模n不断的增大，上述的时间复杂度就不断地增大，
意味着算法的执行效率越低
'''

冒泡排序的实现 时间复杂度O(n^2)

相邻的两个数字进行比较，大的向下沉，最后一个元素是最大的

def bubble_sort(l):
    count=len(l)
    for i in range(0,count):
        for j in range(i+1,count):
            if l[i]>l[j]:
                #使用python特有的方法进行两数排序
                l[i],l[j]=l[j],l[i]
    return l

alist=[34,435,65,73,74,1,334]
bubble_sort(alist)
print(alist)

快速排序 时间复杂度O(nlog2n)

递归 列表取出第一个元素作为标准，把比第一个元素小的都放在左侧，大的方右侧

递归完成，排序结束

def quick_sort(qlist):
    if qlist==[]:
        return []
    else:
        first=qlist[0]
        #print(first)
        less=quick_sort([l for l in qlist[1:] if l<first])
        more=quick_sort([m for m in qlist[1:] if m>=first])
        return less + [first] +more
blist=quick_sort([23,46,75,14,32,67,99,58])
print(blist)