技术

python选择排序

OnlyCEC · 3月16日 · 2020年 67次已读

简单讲讲:我估计能打开我这篇文章的朋友都应该知道选择排序吧。我就不那么系统官方的定义了。我喜欢用实例说明,比如给你一个列表L,如下:

[2, 4, 3, 9, 7, 5, 1, 8, 6]

首先第1轮,我们假设这个列表的最小值为第一个元素2,然后拿2和4比,发现2小于4,那接着往下比,一直到2和1比,发现2大于1,那么我们把这个列表的最小值设为1,然后拿1往下比,发现没有比1更小的了,那么我们就把第一个元素2和1交换,变成如下

[1, 4, 3, 9, 7, 5, 2, 8, 6]

这就进入了第2轮,我们从4开始(因为前面1已经是排好序的了)和后面的数逐一比较,比到2时发现2是最小的,然后我们就把4和2就交换,变成如下

[1, 2, 3, 9, 7, 5, 4, 8, 6]

进入第3轮,发现3已经是最小的了,不需要任何交换,保持如下

[1, 2, 3, 9, 7, 5, 4, 8, 6]

进入第4轮,发现4最小,将9和4交换,变成如下

[1, 2, 3, 4, 7, 5, 9, 8, 6]

进入第5轮,发现5最小,7和5交换,变成如下

[1, 2, 3, 4, 5, 7, 9, 8, 6]

进入第6轮,发现6最小,7和6交换,变成如下

[1, 2, 3, 4, 5, 6, 9, 8, 7]

进入第7轮,发现7最小,9和7交换,变成如下

[1, 2, 3, 4, 5, 6, 7, 8, 9]

进入第8轮,发现8已经是最小的了,保持不变

至此,9个元素的列表经过8轮比较交换,已经井然有序了。我们发现N个元素的列表需要经过N-1轮比较交换,于是选择排序的第一行代码依旧是:

for i in range(len(L)-1): 

我们的i不仅可以表示轮数,还可以表示元素的每个索引,我们每轮在比较时,都假设第一个元素为最小的元素,所以这行代码要写在这个的下面,所以第二行代码:

    min_index = i

在第 1 轮中,我们只需要和 2 to N 的元素比较;

在第 2 轮中,我们只需要和 3 to N 的元素比较;

在第 3 轮中,我们只需要和 4 to N 的元素比较;

。。。

在第i轮中,我们只需要和 i+1 to N 的元素比较,于是第三行代码:

        for j in range(i+1,len(L)):

索引都准备稳妥,下面开始比较了,我们用最小索引对应的元素依次和后面的元素比较,只要发现后面元素比较小,就把小的那个元素的索引赋值给最小索引min_index,直到最后遍历结束,所以第四五行代码如下:

            if L[min_index] > L[j]:
                min_index = j

最后判断,如果最小索引min_index已经不是初始值i了,那么我们就把i所对应的元素和最小索引min_index对应的元素互换,最后六七行代码如下:

        if min_index != i:
            L[min_index], L[i]= L[i], L[min_index]

综上所述,选择排序的代码就写完了。主要逻辑代码一共7行。

标配代码:

L = [2, 4, 3, 9, 7, 5, 1, 8, 6]

for i in range(len(L)-1):
    min_index = i
    for j in range(i+1, len(L)):
        if L[min_index] > L[j]:
            min_index = j
    if min_index != i:
        L[min_index], L[i] = L[i], L[min_index]

print(L)
 

突然意识到,这次写的比上次冒泡排序糙了一些- -不过应该也能看明白吧。

那么我们想想选择排序有没有什么可优化的地方?下面这种方法可以吗?网上可见的唯一的选择排序优化:利用每次比较时,不光得出一个最小值,再反向得出一个最大值,这样就可以减少一半的循环次数。如下代码所示:

L = [2, 4, 3, 9, 7, 5, 1, 8, 6]

for i in range(len(L)//2): #减少一半的循环次数
    min_index = i
    max_index = -(i+1)
    for j in range(i+1, len(L)-i):
        count = count + 2
        if L[min_index] > L[j]:
            min_index = j
        if L[max_index] < L[-j-1]: #反向比较最大值
            max_index = -j-1
    if L[min_index] == L[max_index]:
        break 
    if min_index != i:
        L[min_index], L[i] = L[i], L[min_index] 
        if max_index == -(len(L) - i):   #如果i恰好为最大值
            max_index = min_index
    if max_index != -(i+1):
        L[max_index], L[-(i+1)] = L[-(i+1)], L[max_inde]

print(L)

然而事实是在我看来以上代码并没有起到优化作用,相反随着代码复杂度增加,比较次数的增加而导致性能更逊于原来的代码。下面我做一个测试来证明“优化”后的代码是不是比之前更快了,以及对优化后的代码解析并解释为什么这个看起来被优化的代码事实上并不是优化。

“优化”对比测试:

import timeit
import random


def nom_sort(L):
    for i in range(len(L)-1):
        min_index = i
        for j in range(i+1, len(L)):
            if L[min_index] > L[j]:
                min_index = j
        if min_index != i:
            L[min_index], L[i] = L[i], L[min_index]
    return L
 

def opt_sort(L):
    for i in range(len(L)//2):
        min_index = i
        max_index = -(i+1)
        for j in range(i+1, len(L)-i):
            if L[min_index] > L[j]:
                min_index = j
            if L[max_index] < L[-j-1]:
                max_index = -j-1
        if min_index != i:
            L[min_index], L[i] = L[i], L[min_index] 
            if max_index == -(len(L) - i):
                max_index = min_index
        if max_index != -(i+1):
            L[max_index], L[-(i+1)] = L[-(i+1)], L[max_index]
    return L

res = []
number = 20  # 20, 200, 2000
M = list(range(0,number))
for i in range(10000): #循环次数 10000 1000 100
    random.shuffle(M) #随机打散
    N = M[:]
    res.append([timeit.timeit('nom_sort(M)', number=1, globals=globals()),
                timeit.timeit('opt_sort(N)', number=1, globals=globals())]  )
    #分别执行两个函数,计算执行number次的总时间,为保证稳定性和公平性用for循环测试多次
print('%.8f %.8f' % tuple([sum([i[j] for i in res])/len(res) for j in range(2)]))
    #计算两个函数的各自平均秒数

### optput ###
元素数  循环次数    标配版      "优化"版     提高效率
20       10000    0.00002935  0.00003818    -30.1 %
200      1000     0.00162534  0.00222522    -36.9 %
2000     100      0.46240990  0.40061400    -24.2 % #后续测试最终趋向于0
[公式]
[公式]

通过以上测试,得知上面的代码并不是对选择排序的优化,原因在于虽然减少了循环次数,但是循环里面的比较却增多了。拿一个含有9个元素的列表举例[2 ,4, 3, 9, 7, 5, 1, 8, 6],普通选择排序第1轮比较8次,第2轮比较7次,一直到最后第8轮比较1次,最终N个元素比较  次;而后面的排序算法第1轮比较2*8次,第2轮比较2*6次,第3轮比较2*4次,第4轮比较2*2次,一共16+12+8+4=40次,最终推导N个元素比较  次。因为多了N//2次比较,这也就是为什么后面的算法反倒不如之前的算法了。而之所以会多N//2,是因为普通算法第1轮比较8次,下1轮只需要比较7次就好了,因为第一个元素已经是最小的,不需要比较了,而后面的算法第1轮要比较2个8次,因为在比较第二个8次时,他不知道最大值是哪个,所以连最小的那个索引也一起比较了,这就比普通的排序算法多比较了1次,也就是每2次多比较1次,即这个算法每轮多比较1次,那么一共有N//2轮,所以就多出了N//2次。

[公式]

总结:从表面看选择排序和冒泡排序比较次数一样,但减少了交换次数,理论上应该比冒泡排序更好一些,但是选择排序基本上没有什么优化的地方,而冒泡排序可以优化并提前退出,所以在实际性能上选择排序并不一定就会比冒泡好,具体的性能差距,我会在下一章插入排序之后做一个对比测试。选择排序的时间复杂度为O(n²),也就是从上面  得到的,空间复杂度O(1)不稳定的排序,因为在交换过程中,每个元素都有可能被换到任意的位置,如[4, 3, 4, 1],第一个元素4和1交换后,两个相同数值4的前后顺序发生了改变。反正,目前没有发现选择排序比较有效实际的优化方式,以后找到或想到了再来补充。那么,我们下一篇讲:插入排序。

0 条回应