数据结构与算法（冒泡排序与选择排序）

1.冒泡排序

冒泡排序是一种简单的排序算法，它重复的遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换，遍历数列的工作是重复的进行直到没有需要交换的元素。

冒泡排序算法执行如下：

1. 比较相邻的元素，如果第一个比第二个大（升序），就把他们交换；
2. 对每一对相邻元素作同样的工作，从开始第一队到结尾最后一对，执行完毕后，最后的元素会是最大的数；
3. 针对所有的元素重复以上的步骤，除第一个；
4. 持续每次对减少的元素重复执行上面步骤，直到没有任何一对数字需要比较。

冒泡排序分析

第一次交换过程图示：

bubblesort.jpg

那么我们需要进行n-1次冒泡过程，每次对应的比较次数如下图所示：

compare.jpg

代码：

#coding:utf-8
def bubble_sort(alist):
    """冒泡排序"""
    n=len(alist)
    for j in range(n-1):
        for i in range(0,n-j-1):
            #从头到尾

            if alist[i]>alist[i+1]:
                alist[i],alist[i+1]=alist[i+1],alist[i]


if __name__=='__main__':
    li=[12,54,536,189,697,100]
    print(li)
    bubble_sort(li)
    print(li)

2.选择排序

选择排序是一种简单直观的排序算法，工作原理为：首先在未排序序列中找到最小（最大）的元素，存放到排序序列的起始位置，然后，在从剩余未排序元素中继续寻找最小（最大）元素，然后放到已排序序列的末尾，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关，如果某个元素位于正确的最终位置上，则它不会被移动，选择排序每次交换一对元素，他们当中至少有一个将被移动到其最终位置，因此对n个元素的表进行排序总共进行最多n-1次交换，

选择排序分析

排序过程：

selectionsort.jpg

代码：

#coding:utf-8

def selection_sort(list):
    n=len(list)

    #需要进行n-1次选择操作
    for i in range(n-1):
        #记录最小位置
        min_index=i
        #从i+1位置到末尾选择出最小数据
        for j in range(i+1,n):
            if list[j]<list[min_index]:
                min_index=j

        #如果选择出的数据不在正确位置，进行交换
        if min_index!=i:
            list[i],list[min_index]=list[min_index],list[i]


list=[3,5,6,9,8,7,4,2,1,20,60,10]
print(list)
selection_sort(list)
print(list)

冒泡排序与选择排序时间复杂度比较

	最优时间复杂度	最坏时间复杂度	稳定性
冒泡排序	O(n)	O(n^2)	稳定
选择排序	O(n^2)	O(n^2)	不稳定