45简单排序

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
'''
简单排序统一接下来的格式
def X_Sort( ElementType A[], int N )
    默认从小到大的整数排序。

    只讨论基于 比较 的排序。
    只讨论内部排序。假定内存空间无限大，一次性在内存中解决。

稳定性：任意两个相等的数据，排序前后的相对位置不发生改变。

没有一种排序是任何情况下都表现最好的。

'''

'''
冒泡排序算法：
    步骤一： 让一个指针从上到下，依次比较两个相邻的泡泡。
            如果大小不对，就交换两个泡泡的位置。
    补充说明：
        第一个循环（也就是第一趟冒泡）完毕时（指针从头走到 N-1位置），
        此时最大的值已经找到，但是前面的N-1个位置的排序不确定。
    步骤二： 在前面 N-1 个数组中 ，重复步骤一，找出第二大的数。
    ...
    不断重复，直到前面没定顺序的数组中只剩2个数,(足够完成最后一次交换)。 # 其实这个比较的区间就是原数组去头去尾的。
    （其实我们在最小堆那节已经用过类似的思想了。）
'''

# 冒泡排序代码

def Bubble_Sort(A):
    for p in range(len(A)-1,0,-1):   # 比较区间的变化其实就是原数组去头去尾的部分，因为这已经足够Swap了。
        flag = 0                     # 用标识看是否发生了交换。可以降低最好的情况下时间复杂度。
        for i in range(p):
            if A[i] > A[i+1]:
                Swap(A,i)
                flag = 1             # 发生了交换。
        if flag == 0:
            return '冒泡排序第一遍冒泡就发现顺序已经没问题了。'
def Swap(A,i):   # 对可变对象本体操作才能 达到修改目的。
    temp = A[i]
    A[i] = A[i+1]
    A[i+1] = temp

# 以下写法对于可变对象达不到效果。

# def Swap(a,b):

#     temp = a

#     a = b

#     b = temp

# 冒泡排序最好的时间复杂度是 O(N) 一遍冒泡就发现根本不需要交换，原本已经是排好的了。

# 最坏的时间复杂度是 O(N**2)  完全是逆序的，每一对相邻的元素都要交换。

# 冒泡排序有一个优点别的 排序没有，

# 一是在非数组的链表情况下，冒泡排序依然可用。

# 因为这个交换发生在相邻两个元素间，在链表一样可以完成。

# 二是，比较中，如果相等是不改变位置的，也就是 "稳定" 的。

'''
插入排序算法：
    类似于打牌里的 "插牌"。
    假定手里本来就有一张牌，是数组的第一张牌，
    从数组抓第二张牌，
    和手中第一张牌比大小，决定是否交换位置，
    从手里抓第三张牌，和前一张牌比大小，看看是否交换位置，...再看看和第一张牌是否要交换。
    ...
    直到抓完N-1张牌。
'''

# 插入排序代码

def Insert_Sort(A):  #     下面一种写法会更加好理解一些。

#     for p in range(1,len(A)):    # 抓牌

#         temp = A[p]              # 这次抓到的牌

        # for i in range(p,-1,-1): # 一直回头比,注意比到第一个数，腾出适合的插入位置。
        #     if i-1 >=0 and A[i-1] > temp:  # 其实是比到i=1的位置，但是i会循环到0，以便后序方便赋值。这里老师伪代码其实看的更加清晰一些。
        #         A[i] = A[i-1]
        #         # print(i)
        #     else:
        #         break            # 找到适合的插入位置 i。
        # A[i] = temp              # 新牌落位。
    for p in range(1, len(A)):     # 抓牌
        temp = A[p]                # 这次抓到的牌
        preIndex = p-1
        current = p
        while A[preIndex] > temp and preIndex >= 0 :  # 找插入位置。python找插入位置用while写方便一些。
            A[current] = A[preIndex]
            current = preIndex
            preIndex = current - 1
            # print(A)
        A[current] = temp
        # print(A)

# 因为比较中如果等值，位置不会变化，所以插入排序也是 "稳定" 的。

# 最好的时间复杂度 O(N)，和冒泡一样，一遍以后发现顺序是对的。

# 最坏的时间复杂度 O(N**2) 也和冒泡一样，全部重排一遍。


if __name__ == '__main__':
    a = [1,5,6,2,4,3,8,9,7]
    Bubble_Sort(a)
    print(a)
    b = [1,2,3,4,5,6,7,8,9]
    # b = [3,1,9,8,28,36,44,35,0,100]
    print('\n',Bubble_Sort(b))
    print(b,'\n')
    c = [3,1,9,8,28,36,44,35,0,100]
    Insert_Sort(c)
    print(c)
'''
时间复杂度下界讲解/
    "逆序对"inversion：下标i < j,但是 A[i] > A[j],则（i，j）是一对逆序对。
    {34,8,64,51,32,21} 中有多少逆序对呢？ I = 9 个。
    无论是冒泡还是插入排序，交换次数都是9次，消去了9个逆序对。
    插入排序 T(N,I) = O(N+I) 。
    如果序列基本有序，则插入排序简单且高效。
    

    定理： 
        N个不同元素组成的序列，平均有 N(N-1)/4个 逆序对。
    定理：
        任何仅以交换相邻两个元素来排序的算法，其平均时间复杂度为 Ω(N**2)。
        Ω 是时间复杂度下界。   # 最好的情况下T 和平均时间复杂度下界不是一个意思。
    
    根据以上分析，要提高算法效率，需要一次交换消除尽可能多的逆序对。 
        所以我们在接下来的尝试中，跳着交换相隔较远的2个元素。

'''