Berbagi teknologi

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

1. Penyortiran gelembung

'''冒泡排序'''

"""
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. Penyortiran cepat

'''快速排序'''

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. Sortir penyisipan

'''插入排序'''

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. Penyortiran bukit

'''希尔排序'''
#①第一层循环 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.Pilih pengurutan

'''选择排序'''
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. Sortir tumpukan

Max heap selalu menyimpan nilai maksimum pada simpul akar pohon.
Untuk min-heap, elemen di simpul akar selalu merupakan nilai terkecil di pohon.
Skenario aplikasi
Misalnya, untuk mencari 10 bilangan terbesar teratas di antara 1 miliar bilangan, selalu buat tumpukan teratas kecil yang hanya berisi 10 elemen. Jika lebih kecil dari tumpukan teratas, maka tidak akan diproses jika lebih besar dari tumpukan teratas tumpukan, ganti bagian atas tumpukan, lalu lanjutkan secara berurutan.
Misalnya, untuk mencari 10 angka pertama terkecil di antara 1 miliar angka, selalu buat tumpukan teratas yang besar dengan hanya 10 elemen. Jika lebih besar dari tumpukan teratas, maka tidak akan diproses jika lebih kecil dari tumpukan teratas tumpukan, ganti bagian atas tumpukan, lalu lanjutkan secara berurutan.
Umumnya, tumpukan atas yang besar digunakan dalam urutan menaik, dan tumpukan atas kecil digunakan dalam urutan menurun.

'''构造大顶堆'''
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. Gabungkan pengurutan

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. Pencarian biner

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