常见的排序算法
- 冒泡排序（Bubble Sort）
- 选择排序（Selection Sort）
- 插入排序（Insertion Sort）
- 快速排序（Quick Sort）
- 希尔排序 (Shell Sort）
- 归并排序 (Merge Sort)
冒泡算法的思想
冒泡排序算法的运作如下：
- 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
下面来用python实现冒泡排序
#_*_coding:utf-8_*_
def bubble_sort(a):
#a is a list
if not a:
return
length = len(a)
for i in range(0, length - 1):
for j in range(0, length - i -1):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1],a[j]
if __name__ == '__main__':
list1 = [34,12,1,8,9,19,12]
print(list1)
bubble_sort(list1)
print(list1)
分析一下上面的程序可以得出：
1.时间复杂度O(n^2)
- 如果原来的序列本来就是有序的话，如果按照上述算法，时间复杂度依旧是O(n^2), 对此可以进行算法优化，可以加入内循环计数器用来记录交换的次数，如果内循环计数器始终为零，则表示该数列是有序的，就不用进行外循环了，算法复杂度可以O（n）
优化算法实现为:
#_*_coding:utf-8_*_
def bubble_sort(a):
#a is a list
if not a:
return
length = len(a)
for i in range(0, length - 1):
**count = 0**
for j in range(0, length - i -1):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1],a[j]
**count += 1**
**if count == 0:
return**
if __name__ == '__main__':
#list1 = [34,12,1,8,9,19,12]
list1 = [1,2,3,4,5]
print(list1)
bubble_sort(list1)
print(list1)
冒泡算法时间复杂度总结
- 最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）
- 最坏时间复杂度：O(n2)
- 稳定性：稳定
