Κοινή χρήση τεχνολογίας

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

1. Ταξινόμηση με φυσαλίδες

'''冒泡排序'''

"""
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. Γρήγορη ταξινόμηση

'''快速排序'''

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. Ταξινόμηση εισαγωγής

'''插入排序'''

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. Διαλογή λόφων

'''希尔排序'''
#①第一层循环 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.Επιλέξτε ταξινόμηση

'''选择排序'''
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. Ταξινόμηση σωρών

Το Max heap αποθηκεύει πάντα τη μέγιστη τιμή στον ριζικό κόμβο του δέντρου.
Για ένα min-heap, το στοιχείο στον ριζικό κόμβο είναι πάντα η μικρότερη τιμή στο δέντρο.
Σενάρια εφαρμογής
Για παράδειγμα, για να βρείτε τους 10 μεγαλύτερους αριθμούς ανάμεσα σε 1 δισεκατομμύριο αριθμούς, να δημιουργείτε πάντα έναν μικρό κορυφαίο σωρό με μόνο 10 στοιχεία, εάν είναι μικρότερος από την κορυφή του σωρού, δεν θα υποστεί επεξεργασία εάν είναι μεγαλύτερος του σωρού, τοποθετήστε το επάνω μέρος του σωρού και, στη συνέχεια, προχωρήστε στη σειρά.
Για παράδειγμα, για να βρείτε τους μικρότερους πρώτους 10 αριθμούς μεταξύ 1 δισεκατομμυρίου αριθμών, να δημιουργείτε πάντα έναν μεγάλο σωρό με μόνο 10 στοιχεία, εάν είναι μεγαλύτερος από την κορυφή του σωρού, δεν θα υποβληθεί σε επεξεργασία εάν είναι μικρότερος του σωρού, τοποθετήστε το επάνω μέρος του σωρού και, στη συνέχεια, προχωρήστε στη σειρά.
Γενικά, ο μεγάλος επάνω σωρός χρησιμοποιείται με αύξουσα σειρά και ο μικρός κορυφαίος σωρός χρησιμοποιείται με φθίνουσα σειρά.

'''构造大顶堆'''
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. Συγχώνευση ταξινόμησης

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. Δυαδική αναζήτηση

'''二分查找'''
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