1.排序简介

排序算法（Sorting algorithm）是一种能将一串数据依照特定顺序进行排列的一种算法。

分类：内部排序、外部排序（区别在于数据量大小，是否需要借助外部辅助存储器）。

常见的排序法有：冒泡排序、选择排序、插入排序、合并排序、快速排序、堆积排序、希尔排序、基数排序。

排序算法的分析：

稳定性：相同键值的记录在排序后仍然保持原来的次序。

时间复杂度

空间复杂度：排序法所用到的额外空间。

2. 冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下：

比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

冒泡法分析：

时间复杂度： $O(n^{2})$

稳定性：稳定

空间复杂度：只需一个额外的空间，空间复杂度为最佳。

冒泡排序实现：

思路：第一遍时 i从0到n-1，两两比较，if当前大于后一个值，交换，最后一个即为最大值

第二遍 i从 0 到n -2(即倒数第二个元素）,执行同上步骤。

因此令j 0 到n-2 ,i 为0到 n-1-j

第一遍 j=0 , i range(0,n-1) (即最后一个元素）

第二遍 j=1 ,i range(0,n-2) (即倒数第二个元素）

第三遍 j= 2 i range(0,n-3) (即倒数第二个元素）

……

最后 i (0,1), 得 n-1-j=1 所以 j最大为n-2，故j range(n-1)

def bubble_sort(alist):    """冒泡排序"""    n = len(alist)    for j in range(n-1):        for i in range(0, n-1-j):            # 班长从头走到尾            if alist[i] > alist[i+1]:                alist[i],alist[i+1] = alist[i+1], alist[i]

或者

def bubble_sort(alist):    for j in range(len(alist)-1,0,-1):        # j表示每次遍历需要比较的次数，是逐渐减小的        for i in range(j):            if alist[i] > alist[i+1]:                alist[i], alist[i+1] = alist[i+1], alist[i]

例1 使用冒泡排序对数列排序

data=[16,25,39,27,12,8,45,63]	# 原始数据 print('冒泡排序法：原始数据为：')for i in range(8):    print('%3d' %data[i],end='')print()for i in range(7,-1,-1): #扫描次数    for j in range(i):        if data[j]>data[j+1]:#比较,交换的次数            data[j],data[j+1]=data[j+1],data[j]#比较相邻的两数,如果第一个数较大则交换    print('第 %d 次排序后的结果是：' %(8-i),end='') #把各次扫描后的结果打印出来    for j in range(8):        print('%3d' %data[j],end='')    print()	print('排序后的结果为：')for j in range(8):    print('%3d' %data[j],end='')print()

例2 发现冒泡排序的一个缺点，无论排序是否完成都固定实现n(n-1)次，因此使用岗哨的概念，可以提前中断程序

#[示范]：改进的冒泡排序法def showdata(data):    #使用循环打印数据    for i in range(6):        print('%3d' %data[i],end='')    print()    def bubble (data):    for i in range(5,-1,-1):        flag=0    #flag用来判断是否执行了交换操作        for j in range(i):            if data[j+1]

使用flag，当不执行交换时，说明已排好序，此时flag=0, 跳出循环。

转载地址：http://uerii.baihongyu.com/

你可能感兴趣的文章