def BubbleSort(li):
    # 每一次生成一个最大值
    for i in range(len(li)):
        #### i = 0 i = 1  --- 8
        flag = False
        # 已生成最大值的便不用再遍历，且每次最后一个数不用
        for j in range(len(li)-i-1):  ### j = 0, 1, 2, 3, 7
            if li[j] > li[j+1]: ### li[0] > li[1] | li[1] > li[2] | li[2] > li[3]
                li[j], li[j+1] = li[j+1], li[j]   #### [5,4,6,7,3,8,2,1,9]
                flag = True
        if not flag:
            return

def selectSort(li):
    # 每次循环得到一个最小的数
    for i in range(len(li)):
         # minLoc = i = 0
        for j in range(i+1, len(li)):  # j = 1, j = 2
            if li[j] < li[i]:   ### li[2] < li[minLoc]  4 < 5
                li[j], li[i] = li[i], li[j] ## [5,7,4,6,3,8,2,9,1]

def insertSort(li):
    for i in range(1, len(li)):
        tmp = li[i]  ## tmp = li[1] = 5
        j = i - 1    ## j = 1 - 1 = 0
        while j >= 0 and li[j] > tmp:  ## li[0] = 7 > 5:
            li[j+1] = li[j]   ## li[1] = li[0] = 7 ==> [7,7,4,6,3,8,2,9,1]
            j = j - 1       ## j = -1
        li[j+1] = tmp   ### li[0] = tmp = 5  ==> [5,7,4,6,3,8,2,9,1]

### 快排：O(n)
def partition(li, left, right):
    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]
    # 指针重合，left，right均可以，为对称使用left
    li[left] = tmp
    return left

## 时间复杂度: O(nlogn)
def _quickSort(li, left, right):
    if left < right:
        mid = partition(li, left, right) ### O(n)
        _quickSort(li, left, mid - 1)   ### O(logn)
        _quickSort(li, mid + 1, right)

###  时间复杂度: O(nlogn)
def merge(li, low, mid, right):
    i = low
    j = mid + 1
    ltmp = []
    while i <= mid and j <= right:
        if li[i] < li[j]:
            ltmp.append(li[i])
            i = i + 1
        else:
            ltmp.append(li[j])
            j = j + 1

    while i <= mid:
        ltmp.append(li[i])
        i = i + 1

    while j <= right:
        ltmp.append(li[j])
        j = j + 1

    li[low:right+1] = ltmp

def mergeSort(li, low, high):
    if low < high:
        mid = (low + high) // 2
        mergeSort(li, low, mid)
        mergeSort(li, mid + 1, high)
        print(‘归并之前:‘, li[low:high+1])
        merge(li, low, mid, high)
        print(‘归并之后:‘, li[low:high + 1])

def countSort(li):
    count = [0 for i in range(11)]

    for index in li:
        count[index] += 1

    li.clear()

    for index, val in enumerate(count):
        print(index, val)
        for i in range(val):
            li.append(index)


li = [10,4,6,3,8,4,5,7]
countSort(li)
print(li)

# 分糖果原则：贪婪算法
‘‘‘贪心规律 
（1）某个糖果不能满足某个孩子，那么，该糖果一定不能满足更大需求因子的孩子。 
（2）某个孩子可以用更小的糖果满足，则没必要用更大的糖果，留着更大的糖果去满足需求因子更大的孩子。（贪心！！） 
（3）孩子的需求因子更小则其更容易被满足，故优先从需求因子小的孩子开始，因为用一个糖果满足一个较大需求因子的孩子或满足较小需求因子的孩子效果一样。（最终总量不变）（贪心！！）

算法思路 
（1）对需求因子数组g和糖果大小数组s进行从小到大排序； 
（2）按照从小到大的顺序使用各糖果，尝试是否可以满足某个孩子，每个糖果只尝试一次；若成功，则换下一个糖果尝试；直到发现没有孩子或者没有糖果，循环结束。 
--------------------- 
‘‘‘
def candygivechildren(g, s):
    g = sorted(g)
    s = sorted(s)

    child = 0
    cookie = 0

    while child < len(g) and cookie < len(s):
        if g[child] < s[cookie]:
            child += 1
        cookie += 1
    return child

g = [5,10,2,9,15,9]
s = [1,3,6,8,20]
res = candygivechildren(g,s)
print(res)

class Hero(object):
    def __init__(self, no=None, name=None, nickname=None, pNext=None):
        self.no = no
        self.name = name
        self.nickname = nickname
        self.pNext = pNext

def add(head, hero):
    ### 后面添加
    # head.pNext = hero

    # 将指针赋值给一个变量
    cur = head
    # print(id(cur), id(head))
    while cur.pNext != None:
        if cur.pNext.no > hero.no:
           break
        cur = cur.pNext
    hero.pNext = cur.pNext
    cur.pNext = hero
    # print(id(cur), id(head))

def showAll(head):
    cur = head
    while cur.pNext != None:
        cur = cur.pNext
        print(cur.no, cur.name)


def delHero(head, no):
    cur = head

    while cur.pNext != None:
        if cur.pNext.no == no:
            break
        cur = cur.pNext   ### cur += 1

    cur.pNext = cur.pNext.pNext

head = Hero()
h1 = Hero(1, ‘宋江‘, ‘及时雨‘)
add(head, h1)

h2 = Hero(2, ‘卢俊义‘, ‘玉麒麟‘)
add(head, h2)

h4 = Hero(4, ‘鲁智深‘, ‘花和尚‘)
add(head, h4)

h3 = Hero(3, ‘林冲‘, ‘豹子头‘)
add(head, h3)

showAll(head)