Python算法札记1_冒泡排序
2019-06-23 本文已影响1人
皮皮大
冒泡排序：
冒泡排序无疑是最为出名的排序算法之一，从序列的一端开始往另一端冒泡，依次比较相邻的两个数的大小。重复性的工作直到没有可以交换的两个元素，说明数列已经排序完成。冒泡算法的时间复杂度为O(n2)。
image.png
算法思想
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 每次循环固定一个数，比较的次数依次减1
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
通过一个简单的例子来进行说明，冒泡排序算法的具体过程，现在有一个列表list = [8, 2, 5, 9, 7]，如何通过冒泡算法实现排序：
1.jpg
首先比较第一个数字和第二个数字，发现8比2大，则8位置不动，整体还是[8,2,5,9,7]，此时指针右移一格
2.jpg
比较第二个数和第三个数的大小，发现2比5小，则交换它们的位置，5放到2的前面，变成[8,5,2,9,7]，指针右移一格
3.jpg
比较第三个数和第四个数的大小，发现2比9小，交换位置，变成[8,5,9,2,7]，指针右移一格。
4.jpg
比较第四个数和第五个的大小，发现2比7小，交换位置，变成[8,5,9,7,2]，指针右移发现已经到底。
第一轮的冒泡结束，第二轮开始
5.jpg
比较第一个和第二个数，8比5大，保持不变，指针右移
6.jpg
比较第二个和第三个数，发现5比9小，交换位置，变成[8,9,5,7,2]，只有指针右移。
7.jpg
比较第三个和第四个数，发现5也比7小，交换位置，变成[8,9,7,5,2]，指针右移；再比较第四个和第五个数字，5比2大，保持不变。
8.jpg
经过两轮的冒泡排序，变成了[8,9,7,5,2]的效果，经过多次循环的过程最终一定会变成[9,8,7,5,2]
Python代码实现
list1 = [1,7,3,5,2]
length = len(list1)
for i in range(length)：
for j in range(length-1-i): # 每次排序结束，j的次数都要减1，
if list1[j] > list1[j+1]:
list1[j], list1[j+1] = list1[j+1], list1[j]
print(list1)
def bubble_sort(nums):
for i in range(0, len(nums) - 1): # 设置冒泡排序进行的次数
for j in range(0, len(nums) - i - 1): # j为列表下标
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
if __name__ == "__main__":
lists = [1,9,3,5,2,8,4,6,10,7]
bubble_sort(lists)
print(lists)
# print(bubble_sort([1,9,3,5,2,8,4,6,10,7]))
def bubble(bubbleList):
listLength = len(bubbleList)
while listLength > 0:
for i in range(listLength - 1):
if bubbleList[i] > bubbleList[i+1]:
bubbleList[i], bubbleList[i+1] = bubbleList[i+1], bubbleList[i]
listLength -= 1
return bubbleList
if __name__ == '__main__':
bubbleList = [3, 4, 1, 2, 5, 8, 0]
bubble(bubbleList)
print(bubbleList)
