算法NB三人组

#快速排序-除了python自带的sort排序模块之外就这个最好用，只需会这个就行，其他的排序了解就好，能用冒泡，插入。。的都可以用快排快速实现

import random

from timewrap import *

import copy

import sys

sys.setrecursionlimit(100000)             #更改最大递归深度

def partition(li, left, right):           #无序列表，最小值，最大值    ，归位

    # ri = random.randint(left, right)

    # li[left], li[ri] = li[ri], li[left]

    tmp = li[left]        #取出来了li[left]

    while left < right:  #至少有两个元素

        while left < right and li[right] >= tmp:

            right -= 1

        li[left] = li[right]

        while left < right and li[left] <= tmp:

            left += 1

        li[right] = li[left]

    li[left] = tmp    #最后还得赋值回去

    return left

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)         #递归右边的值使其归位

@cal_time

def quick_sort(li):                             #加壳处理

    return _quick_sort(li, 0, len(li)-1)

@cal_time

def sys_sort(li):                    #系统自带排序

    li.sort()

li = list(range(100000))

random.shuffle(li)          #随机产生10000个数打乱并加入到列表

#sys_sort(li1)

quick_sort(li)

# 堆排序

from timewrap import *

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

@cal_time

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(10000))

random.shuffle(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)

# 归并排序

import random

from timewrap import *

import copy

import sys

def merge(li, low, mid, high):

    i = low

    j = mid + 1

    ltmp = []

    while i <= mid and j <= high:

        if li[i] < li[j]:

            ltmp.append(li[i])

            i += 1

        else:

            ltmp.append(li[j])

            j += 1

    while i <= mid:

        ltmp.append(li[i])

        i += 1

    while j <= high:

        ltmp.append(li[j])

        j += 1

    li[low:high+1] = ltmp

def _merge_sort(li, low, high):

    if low < high:  # 至少两个元素

        mid = (low + high) // 2

        _merge_sort(li, low, mid)

        _merge_sort(li, mid+1, high)

        merge(li, low, mid, high)

        print(li[low:high+1])

def merge_sort(li):

    return _merge_sort(li, 0, len(li)-1)

li = list(range(16))

random.shuffle(li)

print(li)

merge_sort(li)

print(li)