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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
"""
排序
小 -> 大
Copyright ©conghaoyuan@gmail.comm
"""
class Sort:

    def __init__(self) -> None:
        pass

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

    def SelectionSort(self, lists):
        for i in range(0, len(lists)-1):
            for j in range(i+1, len(lists)):
                if lists[i] > lists[j]:
                    lists[i], lists[j] = lists[j], lists[i]
        return lists

    def InsertionSort(self, lists):
        for i in range(1, len(lists)):
            key = lists[i]
            j = i - 1
            while (j >= 0) and (lists[j] > key):
                lists[j+1] = lists[j]
                j -= 1
            lists[j+1] = key
        return lists

    def ShellSort(self, lists):
        n = len(lists)
        gap = n // 2
        while gap > 0:
            for i in range(gap, n):
                while i >= gap and lists[i - gap] > lists[i]:
                    lists[i - gap], lists[i] = lists[i], lists[i - gap]
                    i -= gap
            gap //= 2
        return lists

    def MergeSort(self, lists):
        if len(lists) == 1:
            return lists

        mid = len(lists) // 2
        left = lists[:mid]
        right = lists[mid:]
        left_list = self.MergeSort(left)
        right_list = self.MergeSort(right)

        return self.merge(left_list, right_list)

    def merge(self, left, right):
        result = []
        while left and right:
            if left[0] >= right[0]:
                result.append(right.pop(0))
            else:
                result.append(left.pop(0))

        if left:
            result.extend(left)
        else:
            result.extend(right)

        return result

    def QuickSort(self, lists):
        if len(lists) < 2:
            return lists
        mid = lists[len(lists) // 2]
        left, right = [], []
        lists.remove(mid)
        for num in lists:
            if num >= mid:
                right.append(num)
            else:
                left.append(num)
        return self.QuickSort(left) + [mid] + self.QuickSort(right)


if __name__ == '__main__':
    sort = Sort()
    lists = [9, 1, 3, 2, 8, 5, 6, 0, 4, 7]
    print(lists)
    # sort.BubbleSort(lists)
    # sort.SelectionSort(lists)
    # sort.InsertionSort(lists)
    # sort.ShellSort(lists)
    # list1 = sort.MergeSort(lists)
    list1 = sort.QuickSort(lists)
    print(list1)