Python十大经典算法之选择排序

本文主要是介绍Python十大经典算法之选择排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

选择排序算法：

a=[6,5,4,3,2,1]

算法思路：

第一步：在列表的第一个位置存放此队列的最小值

声明一个变量min_index等于列表的第一个坐标值0

从第一个位置0坐标开始，和它后边所有的元素一一比对，如果发生了后边的值min_index坐标的对应的值更小，则min_index值改为后边那个数的坐标，然后用min_index坐标对应的值再跟后边的数比较，完成全部比对以后，将列表的第一个数和min_index坐标对应的数做一个交换

 

第一次用6和5比较，5小，min_index改为1，用5和后边的4比，4小，min_index改为2，用4跟3比，3小，min_index改为3，用3跟2比较，2小，min_index改为4，用2和1比较，1小，min_index改为5，比完了，把坐标5对应的值和第一个值交换

min_index=5

a=[1, 5, 4, 3, 2, 6]，最小的1放到最前边，

第二步：从坐标1开始，把刚才的逻辑再来一遍：

a=[1, 2, 4, 3, 5, 6]

第三步：从坐标2开始，把刚才的逻辑再来一遍

a=[1, 2, 3, 4, 5, 6]

第四步：从坐标3开始，把刚才的逻辑再来一遍

a=[1, 2, 3, 4, 5, 6]

第五步：从坐标4开始，把刚才的逻辑再来一遍

 a=[1, 2, 3, 4, 5, 6]

 

代码实：第一步找最小的值

#encoding=utf-8

a=[6,5,4,3,2,1]

min_index=0

for i in range(1,len(a)):

    if a[min_index]>a[i]:

        min_index=i

print min_index

a[0],a[min_index]=a[min_index],a[0]

print a

 

D:\测试资料\python课件\Python笔记>python task_test.py

5

[1, 4, 3, 2, 5,6]

 

接下来：加一个循环

#encoding=utf-8

a=[6,5,4,3,2,1]

min_index=0

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

    min_index=i    #每次i变化时，将最小下标值改为i，将本次循环第一个位置的值

    for j in range(i+1,len(a)):#和当前i元素之后的所有值进行比对

        if a[min_index]>a[j]:

            min_index=j#如果发生小于的情况，则把此数的坐标赋值于min_index

    print min_index

    #当所有数比较完毕之后，将i坐标值和当前循环找到的最小值进行交换

    a[i],a[min_index]=a[min_index],a[i]

print a

 结果：ok

D:\test_python>python test.py

i: 0

min_index: 1

min_index: 2

min_index: 3

min_index: 4

min_index: 5

a: [1, 5, 4, 3, 2, 6]

i: 1

min_index: 2

min_index: 3

min_index: 4

a: [1, 2, 4, 3, 5, 6]

i: 2

min_index: 3

a: [1, 2, 3, 4, 5, 6]

i: 3

a: [1, 2, 3, 4, 5, 6]

i: 4

a: [1, 2, 3, 4, 5, 6]

 思路：

第一次：找到最小值，存到列表的0坐标位置

第二次：找到次小值，存到列表的1坐标位置

第三次：找到第三小的值，存到列表的2坐标位置

第四次：找到第四小的值，存到列表的3坐标位置

第五次：找到第五小的值，存到列表的4坐标位置

剩下的最后一个位置的数，就是最大值

 

时间复杂度是n^2，因为有两个循环

 

选择排序总结：

选择排序的思路是固定位置，选择排序，即：先从序列中，找到最小的元素，放到第一个位置，然后找到第二小的元素，放到第二个位置，以此类推，直到排好所有的值。

 

那么代码无论怎么写，只要是按照先找到最小的放到第一个位置，然后找第二个最小的值放到第二个位置这种思路，就是选择排序算法的实现方式。

 

首先：实现找到最小的元素放到第一个位置

声明一个变量min_index等于列表的第一个坐标值0

因为min_index是第一个位置，你么从第二个位置（1坐标）开始，和它后边所有的元素一一比对，如果发生了后边的值min_index坐标的对应值更小，则min_index坐标改为后边那个数的坐标，

完成全部比对以后，将列表的第一个数和min_index坐标对应的数做一个交换

代码：

#encoding=utf-8

 

a=[6,9,3,5,0,1,4,2,7]

 

min_index=0

for i in range(1,len(a)):

    print "i:",i

    if a[min_index] > a[i]:

        min_index = i

        print "min_index:",min_index

       

print min_index

a[0],a[min_index] = a[min_index],a[0]

print a

 

程序执行过程：

D:\test>python test.py

i: 1

i: 2

min_index: 2

i: 3

i: 4

min_index: 4

i: 5

i: 6

i: 7

i: 8

4

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

 

可以看到，当i从1开始走，遇到比min_index（初始值0）小的，就把min_index改为i；

比如第一次遇到比min_index=0的数小的时候，i是2，那么把min_index改为2；

然后i继续走，遇到比min_index=2的值小的时候，i是4，那么把min_index改为4;

然后i继续走，再和min_index=4的值比较。。。

 

最后走到8时，程序走完，此时就把最小的数的坐标给了min_index了；

然后把这个数和第一个数作交换，即a[0],a[min_index] = a[min_index],a[0]

至此，第一步就实现了

 

其次，从第二个数开始依次把第一步的逻辑走一遍

 

之后的关键点就是，从第二个数开始依次把第一步的逻辑走一遍

 

怎么走呢？

 

其实第一步循环的关键是先把min_value设为第一个数的坐标0

 

那么第二步就应该把min_value设为1，然后从坐标2开始往前遍历，找到最小的数

 

第三步。。。设为2，坐标从3开始遍历，找到最小的数

 

其实每一步min_value的值就是所遍历的列表的第一个位置，在这个列表中，min_value就是最左边的数，所以就是把同样的逻辑在不同长度的列表中执行一遍

 

每次的区别就是列表的长度不同，就是原来列表右坐标不动，左坐标依次递增

 

那么这个过程就可以用两层循环来做

 

第一层循环用i从左到右遍历列表a

 

当i遍历到某个位置时，执行第一次的循环逻辑，把首位数坐标i赋值给min_value

 

冒泡排序和选择排序的逻辑是相反的

代码：

#encodjng=utf-8

 

a=[6,9,3,5,0,1,4,2,7]

 

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

    min_index=i

    print "i:",i

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

        print "  j:",j

        if a[min_index] > a[j]:

            min_index = j

            print "    min_index:","\033[1;32;40m %s \033[0m" %min_index

    print "  min_index:",min_index

    a[i],a[min_index] = a[min_index],a[i]

    print "  a:",a

print "a:",a 

 

 

代码执行过程：

D:\test>python test.py

i: 0

  j: 1

  j: 2

    min_index: [1;32;40m 2 [0m

  j: 3

  j: 4

    min_index: [1;32;40m 4 [0m

  j: 5

  j: 6

  j: 7

  j: 8

  min_index: 4

  a: [0, 9, 3, 5, 6, 1, 4, 2, 7]

i: 1

  j: 2

    min_index: [1;32;40m 2 [0m

  j: 3

  j: 4

  j: 5

    min_index: [1;32;40m 5 [0m

  j: 6

  j: 7

  j: 8

  min_index: 5

  a: [0, 1, 3, 5, 6, 9, 4, 2, 7]

i: 2

  j: 3

  j: 4

  j: 5

  j: 6

  j: 7

    min_index: [1;32;40m 7 [0m

  j: 8

  min_index: 7

  a: [0, 1, 2, 5, 6, 9, 4, 3, 7]

i: 3

  j: 4

  j: 5

  j: 6

    min_index: [1;32;40m 6 [0m

  j: 7

    min_index: [1;32;40m 7 [0m

  j: 8

  min_index: 7

  a: [0, 1, 2, 3, 6, 9, 4, 5, 7]

i: 4

  j: 5

  j: 6

    min_index: [1;32;40m 6 [0m

  j: 7

  j: 8

  min_index: 6

  a: [0, 1, 2, 3, 4, 9, 6, 5, 7]

i: 5

  j: 6

    min_index: [1;32;40m 6 [0m

  j: 7

    min_index: [1;32;40m 7 [0m

  j: 8

  min_index: 7

  a: [0, 1, 2, 3, 4, 5, 6, 9, 7]

i: 6

  j: 7

  j: 8

  min_index: 6

  a: [0, 1, 2, 3, 4, 5, 6, 9, 7]

i: 7

  j: 8

    min_index: [1;32;40m 8 [0m

  min_index: 8

  a: [0, 1, 2, 3, 4, 5, 6, 7, 9]

a: [0, 1, 2, 3, 4, 5, 6, 7, 9]

 

可以看到加了一层循环是把上一步的逻辑依从从第一个位置到最后一个位置执行了一遍，

第一层循环是控制i从0到len(a)-1一次递增，每次递增为1；

第二层是当i前进一步时，i不动，j在i之后的所有序列中找到最小的数，放到i的位置（j所遍历序列的第一个位置），即走一遍第一步的代码逻辑，然后第二层循环结束（此时i所在位置之前的数已经是排好序的了）；

然后回到第一层循环，把i往前移动一个，再走一遍第一步的查找最小数的逻辑，放到i的位置（j所遍历的序列的第一个位置）

这篇关于Python十大经典算法之选择排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！