算法

冒泡排序

1，思路首先列表每两个相邻的数比较大小，如果前面比后面的大，那么这两个数就互换位置，就像冒泡一样
2代码关键：趟数：n-1趟 无序区

def bubblr_sort(li):
    for i in range(1,len(li)-1):#表示趟数
        change = True
        for j in range(len(li)-i):  #表示无序区，无序区的范围为0,len(li)-i
            if li[j] > li[j+1]:
                li[j],li[j+1] = li[j+1],li[j]
                change = True
        if not change:
            return

li = list(range(10))
import random
random.shuffle(li)
print(li)
bubblr_sort(li)
print(li)

快速排序

1思路：取一个元素p(第一个元素），是元素p归位（去他该去的地方）
列表被p分成两部分，左边都比p小，右边的都比p大
递归完成排序
2，算法的关键点：归位，递归
3，图示说明

import time
def wrapper(func):
    def inner(*args,**kwargs):
        start = time.time()
        ret = func(*args,**kwargs)
        end = time.time()
        print('%s running time :%s'%(func.__name__,start-end))
        return ret
    return inner


def partition(li,left,right):
    '''归位函数'''
    tmp = li[left]  #先把5取出来
    while left < right:
        while left < right and li[right] >= tmp:  #如果降序排列修改li[right] <= tmp
                right -= 1 #从右边找比5小的数，填充到5的位置
        li[left] = li[right]
        while left < right and li[left] <= tmp:  #如果降序排列修改li[right] >= tmp
                left += 1# 从左边找比5大的数字放在右边的空位
        li[right] = li[left]
    li[left] = tmp  #当跳出循环条件的时候说明找到了，并且把拿出来的5在放进去
    return left


def _quick_sort(li,left,right):
    '''快速排序的两个关键点：归位，递归'''
    if left < right:  #至少有两个元素，才能进行递归
        mid = partition(li,left,right)  #找到归位的位置
        _quick_sort(li,left,mid-1)  #递归，右边的-1
        _quick_sort(li,mid+1,right) #递归，左边的+1

@wrapper
def quick_sort(li):
    return _quick_sort(li, 0, len(li)-1)

@wrapper
def sys_sort(li):
    '''系统排序'''
    li.sort()

import random
li = list(range(100000))
random.shuffle(li)
# print(li)
quick_sort(li)
# print(li)

sys_sort(li)  

#结论：系统的排序要比快排的时间快的多
# quick_sort running time :-0.6240355968475342
# sys_sort running time :-0.002000093460083008

快速排序算法

堆排序

1，堆排序过程
建立堆
得到堆顶元素
去掉堆顶，将堆最后一个元素放在堆顶，此时可通过一次调整重新使堆有序
堆顶元素为第二大元素
重复步骤三，直到堆变空

import random

def _sift(li, low, high):
    """
    :param li:
    :param low: 堆根节点的位置
    :param high: 堆最有一个节点的位置
    :return:
    """
    i = low  # 父亲的位置
    j = 2 * i + 1  # 孩子的位置
    tmp = li[low]  # 原省长
    while j <= high:
        if j + 1 <= high and li[j + 1] > li[j]:  # 如果右孩子存在并且右孩子更大
            j += 1
        if tmp < li[j]:  # 如果原省长比孩子小
            li[i] = li[j]  # 把孩子向上移动一层
            i = j
            j = 2 * i + 1
        else:
            li[i] = tmp  # 省长放到对应的位置上(干部)
            break
    else:
        li[i] = tmp  # 省长放到对应的位置上(村民/叶子节点)


def sift(li, low, high):
    """
    :param li:
    :param low: 堆根节点的位置
    :param high: 堆最有一个节点的位置
    :return:
    """
    i = low         # 父亲的位置
    j = 2 * i + 1   # 孩子的位置
    tmp = li[low]   # 原省长
    while j <= high:
        if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子存在并且右孩子更大
            j += 1
        if tmp < li[j]: # 如果原省长比孩子小
            li[i] = li[j]  # 把孩子向上移动一层
            i = j
            j = 2 * i + 1
        else:
            break
    li[i] = tmp



def heap_sort(li):
    n = len(li)
    # 1. 建堆
    for i in range(n//2-1, -1, -1):
        sift(li, i, n-1)
    # 2. 挨个出数
    for j in range(n-1, -1, -1):    # j表示堆最后一个元素的位置
        li[0], li[j] = li[j], li[0]
        # 堆的大小少了一个元素 （j-1）
        sift(li, 0, j-1)


li = list(range(10))
random.shuffle(li)
print(li)
heap_sort(li)
print(li)

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

希尔排序

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

def insert_sort(li):#插入排序
    for i in range(1, len(li)):
        # i 表示无序区第一个数
        tmp = li[i] # 摸到的牌
        j = i - 1 # j 指向有序区最后位置
        while li[j] > tmp and j >= 0:
            #循环终止条件： 1. li[j] <= tmp; 2. j == -1
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp

def shell_sort(li):#希尔排序  与插入排序区别就是把1变成d
    d = len(li) // 2
    while d > 0:
        for i in range(d, len(li)):
            tmp = li[i]
            j = i - d
            while li[j] > tmp and j >= 0:
                li[j+d] = li[j]
                j -= d
            li[j+d] = tmp
        d = d >> 1




li=[5,2,1,4,5,69,20,11]
shell_sort(li)
print(li)

算法