首页 > > 网络编程 > 其它 >

python基础:冒泡和选择排序算法实现

2018-08-10 11:26:53来源：博客园阅读 ()

冒泡排序和选择排序

首先引用一下百度百科对于冒泡算法的定义：

冒泡排序算法的原理如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

在很多计算机语言中冒泡算法都是一种经典的排序算法，在python中也可以轻松实现，并且代码更短，下面看代码：

#冒泡排序
def bubble_sort(lt):
    for i in range(len(lt)-1):         #外部循环，用来表示冒泡进行的次数
        for j in range(len(lt)-i-1):
        #内部循环，如果从下标为0的元素开始匹配，j下标一直到倒数第二个元素
            if lt[j] > lt[j+1]:
                lt[j], lt[j+1] = lt[j+1], lt[j]
                #上面两行代码-如果lt列表中下标为j的值大于下标为j+1的值，
                #就调换位置，相当于lt[j] = lt[j+1], lt[j+1] = lt[j]
    print(lt)     #打印列表
lt = [9, 8, 6, 4, 5, 1, 3, 10]    #首先建一个列表
bubble_sort(lt)  #调用函数输出经过冒泡排序后的列表

选择排序：对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。

#选择排序
list1 = [12, 3, 6, 2, 5, 7, 8, 9] #首先定义一个列表
def quick_sort(list1):
    for i in range(len(list1)-1): #默认从0下标开始
        x = i   #建立一个信号量
        for j in range(i+1, len(list1)):#从列表第i+1个元素开始
            if list1[x] > list1[j]:#一旦匹配到小于下标为i的元素
                x = j
        list1[i], list1[x] = list1[x], list1[i]
        #将元素赋值给信号量x，依次循环，遇到更小的，继续交换元素
    print(list1)
quick_sort(list1)