Compartir tecnología

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Clasificación de burbujas

'''冒泡排序'''

"""
def BubbleSort(nums):
    listLength = len(nums)
    while listLength > 0:
        for i in range(listLength - 1):
            if nums[i] > nums[i+1]:
                nums[i], nums[i+1] = nums[i+1], nums[i]
        listLength -= 1
    return nums
"""

def BubbleSort(nums):
    for i in range(len(nums)):
        for j in range(len(nums) - i - 1):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

nums = [5, 2, 8, 4, 7, 4, 3, 9, 2, 0, 16,1]
print(BubbleSort(nums))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.Clasificación rápida

'''快速排序'''

def QuickSort(nums, start, end):
    if start < end:
        i, j = start, end
        base = nums[i]
        while i < j:
            while i < j and nums[j] >= base:
                j -= 1
            nums[i] = nums[j]
            while i < j and nums[i] <= base:
                i += 1
            nums[j] = nums[i]
        nums[i] = base
        QuickSort(nums, start, i - 1)
        QuickSort(nums, i+1, end)

nums = [9,4,10,8,13,2,15,7]
QuickSort(nums, 0, len(nums)-1)
print(nums)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3. Ordenación por inserción

'''插入排序'''

def InsertSort(nums):
    for i in range(len(nums)-1):
        if nums[i] > nums[i+1]:
            while i>=0 and nums[i] > nums[i+1]:
                nums[i], nums[i+1] = nums[i+1], nums[i]
                i -= 1
    return nums
nums = [9,4,10,8,13,2,15,7]
print(InsertSort(nums))

1
2
3
4
5
6
7
8
9
10
11
12
13

4. Clasificación de colinas

'''希尔排序'''
#①第一层循环 gap折半 直到gap=1
#②二层三层循环直接插入排序
def ShellSort(nums):
    gap = len(nums) // 2
    while gap >= 1:
        for i in range(gap, len(nums)):
            for j in range(i-gap, -1, -gap):
                if nums[j] > nums[j+gap]:
                    nums[j], nums[j+gap] = nums[j+gap], nums[j]
        gap = gap // 2
    return nums
nums = [9,4,10,8,13,2,15,7]
print(ShellSort(nums))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5.Seleccione ordenar

'''选择排序'''
def SelectSort(nums):

    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[j] < nums[i]:
                nums[j], nums[i] = nums[i], nums[j]
    return nums
nums = [5, 2, 8, 4, 7, 4, 3, 9, 2, 0, 1,16]
print(SelectSort(nums))
1
2
3
4
5
6
7
8
9
10

6. Ordenación del montón

El montón máximo siempre almacena el valor máximo en el nodo raíz del árbol.
Para un montón mínimo, el elemento en el nodo raíz es siempre el valor más pequeño del árbol.
Escenarios de aplicación
Por ejemplo, para encontrar los 10 números más grandes entre mil millones de números, siempre cree un montón superior pequeño con solo 10 elementos. Si es más pequeño que la parte superior del montón, no se procesará; del montón, reemplace la parte superior del montón y luego proceda en secuencia.
Por ejemplo, para encontrar los primeros 10 números más pequeños entre mil millones de números, siempre cree un montón superior grande con solo 10 elementos. Si es más grande que la parte superior del montón, si es más pequeño que la parte superior, no se procesará. del montón, reemplace la parte superior del montón y luego proceda en secuencia.
Generalmente, el montón superior grande se usa en orden ascendente y el montón superior pequeño se usa en orden descendente.

'''构造大顶堆'''
def HeapBuild(nums):
    l = len(nums) - 1
    # 构造大顶堆，从非叶子节点开始倒序遍历，因此是l//2 -1 就是最后一个非叶子节点
    for i in range(len(nums)//2 - 1, -1, -1):
        HeapSort(nums, i, l)

    # 上面的循环完成了大顶堆的构造，那么就开始把根节点跟末尾节点交换，然后重新调整大顶堆
    for j in range(l, -1, -1):
        nums[0], nums[j] = nums[j], nums[0]
        HeapSort(nums, 0, j-1)
    return nums

def HeapSort(nums, i, l):
    left, right = 2 * i + 1, 2 * i + 2  # 左右子节点的下标
    index = i
    # 构造大顶推
    if left <= l and nums[i] < nums[left]:
        index = left

    if right <= l and nums[left] < nums[right] and nums[i] < nums[right]:
        index = right

    if index != i:
        nums[i], nums[index] = nums[index], nums[i]
        HeapSort(nums, index, l)

nums = [17, 13, 40 , 22, 31, 14, 33, 56, 24, 19 ,10, 41, 51, 42, 26]
print('使用大顶堆排序：', HeapBuild(nums))

'''构造小顶堆'''
def SmallHeapBuild(nums):
    l = len(nums) - 1
    # 从非叶子节点开始倒序遍历，因此是l//2 -1 就是最后一个非叶子节点
    for i in range(len(nums)//2 - 1, -1, -1):
        SmallHeapSort(nums, i, l) # 小顶堆构造函数

    # 上面的循环完成了小顶堆的构造，那么就开始把根节点跟末尾节点交换，然后重新调整大顶堆
    # 使用小顶堆进行降序，nums[0]是最小的，放到最后
    for j in range(l, -1 ,-1):
        nums[0], nums[j] = nums[j], nums[0]
        SmallHeapSort(nums, 0, j-1)
    return nums

def SmallHeapSort(nums, i, l):
    left, right = 2 * i + 1, 2 * i + 2  # 左右子节点的下标
    index = i
    # 构建小顶堆
    if left <= l and nums[i] > nums[left]:
        index = left

    if right <= l and nums[left] > nums[right] and nums[i] > nums[right]:
        index = right

    if index != i:
        nums[i], nums[index] = nums[index], nums[i]
        SmallHeapSort(nums, index, l)

nums = [17, 13, 40 , 22, 31, 14, 33, 56, 24, 19 ,10, 41, 51, 42, 26]
print('使用小顶堆倒排序', SmallHeapBuild(nums))


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

7. Combinar clasificación

def MergeBuild(nums):
    if len(nums) == 1:
        return nums
    mid = len(nums) // 2

    left = nums[:mid]
    right = nums[mid:]

    l1 = MergeBuild(left)
    l2 = MergeBuild(right)

    return MergeSort(l1, l2)

def MergeSort(left, right):
    res = []
    while len(left) and len(right):
        if left[0] < right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))
    res += left
    res += right
    return res

if __name__ == '__main__':
    nums = [5, 2, 8, 4, 7, 4, 3, 9, 2, 0, 1,16]
    res = MergeBuild(nums)
    print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

8. Búsqueda binaria

'''二分查找'''
def BinarySearch(target, nums):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return 'target in nums'
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return 'target not in nums'
nums = [2, 4, 7, 8, 9, 10, 13, 15, 19]
print(BinarySearch(13, nums))
print(BinarySearch(20, nums))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16