python实现多种排序

排序

常见的时间复杂度（按效率排序）
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)

如何一眼判断时间复杂度？
循环减半的过程O(logn)
几次循环就是n的几次方的复杂度


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

冒泡排序

'''
原数据：9, 8, 7, 1, 2
第一趟：8，7，1，2，9
第二趟：7，1，2，8，9
第三趟：1，2，7，8，9
第四趟：1，2，7，8，9
'''
一趟会得到一个最大值
时间复杂度：最差的情况：O(n^2)  最好的情况：O(n)


# 1.缺点：如果已经排好序，还会一直循环比较
def bubble_sort(li):
    for i in range(len(li)-1):
        for j in range(len(li)-1-i):
            if li[j] > li[j+1]:
                li[j],li[j+1] = li[j+1],li[j]
    return li

# 2.改进版，res标示位。
    #一趟下来代码没有进入if li[j] > li[j+1],res一直为True，表示已经排好序了，直接跳出循环
def maopao(li):
    for i in range(len(li)-1):
        res = True
        for j in range(len(li)-1-i):
            if li[j] > li[j+1]:
                li[j],li[j+1] = li[j+1],li[j]
                res = False
        if res:
            return li

快速排序

# 时间复杂度是：O(nlogn)
# 最坏的情况O(n方),刚好是逆序
# 解决方法：每次取第一个p元素，改为随机取
def quick_sort(li, left, right):
    if left < right:
        mid = partition(li, left, right) # 调归位函数
        quick_sort(li, left, mid - 1) # 左边
        quick_sort(li, mid + 1, right) # 右边

    return li
def partition(li, left, right):
    temp = li[left]
    while left < right:
        while left < right and li[right] >= temp:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] <= temp:
            left += 1
        li[right] = li[left]

    li[left] = temp
    return left

# p随机取，降低最坏情况的几率
def partition2(li, left, right):
    res = random.randint(left, right)
    li[left], li[res] = li[res], li[left]
    temp = li[left]
    while left < right:
        while left < right and li[right] >= temp:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] <= temp:
            left += 1
        li[right] = li[left]
    li[left] = temp
    return left

if __name__ == '__main__':
    li = [1, 3, 4, 6, 73, 45, 6, 89, 123, 987]
    left = 0
    right = len(li) - 1
    print(quick_sort(li, left, right))

选择排序

思路：
    一趟遍历记录最小的数，放到第一个位置；
    再一趟遍历记录剩余列表中最小的数，继续放置

# 时间复杂度是：O(n^2)
def select_sort(li):
    for i in range(len(li)):
        min_loc = i
        for j in range(i+1,len(li)):
            if li[j]<li[min_loc]:
                min_loc = j
        if min_loc !=i:
            li[i],li[min_loc] = li[min_loc],li[i]
    return li
print(select_sort(li))

插入排序

# 时间复杂度：O(n2)
def insert_sort(li):
    for i in range(1,len(li)):
        tmp = li[i]
        j = i-1

        while j>=0 and li[j]>tmp:
            li[j+1] = li[j]
            j = j-1
        li[j+1] = tmp
    return li
li = [5, 1, 23, 45, 6]

希尔排序

希尔排序是一种分组插入排序算法。
首先取一个整数d1=n/2，将元素分为d1个组，每组相邻量元素之间距离为d1，在各组内进行直接插入排序；
取第二个整数d2=d1/2，重复上述分组排序过程，直到di=1，即所有元素在同一组内进行直接插入排序。
# 希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。

def shell_sort(li):
    res = len(li) // 2
    while res > 0:
        for i in range(res, len(li)):
            tmp = li[i]
            j = i - res
            while j >= 0 and tmp < li[j]:
                li[j + res] = li[j]
                j -= res
            li[j + res] = tmp
        res /= 2
    return li

li = [1,2,3,8,9,2,3,2]
print(shell_sort(li))

二分法查找

# 前提列表必须有序

def bin_search(li, value, left, right):
    if left <= right:
        mid = (left + right) // 2

        if li[mid] == value:
            return mid
        elif li[mid] > value:
            return bin_search(li, value, left, mid - 1)
        else:
            return bin_search(li, value, mid + 1, right)
    else:
        return


li = [1, 2, 3, 4, 5, 6, 7, 8]
print(bin_search(li, 8, 0, len(li) - 1))