冒泡排序

1.原理:比较两个相邻的元素,将值大的元素交换到右边

2.思路:依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面。

    (1)第一次比较:首先比较第一和第二个数,将小数放在前面,将大数放在后面。

    (2)比较第2和第3个数,将小数 放在前面,大数放在后面。

    ......

    (3)如此继续,知道比较到最后的两个数,将小数放在前面,大数放在后面,重复步骤,直至全部排序完成

    (4)在上面一趟比较完成后,最后一个数一定是数组中最大的一个数,所以在比较第二趟的时候,最后一个数是不参加比较的。

    (5)在第二趟比较完成后,倒数第二个数也一定是数组中倒数第二大数,所以在第三趟的比较中,最后两个数是不参与比较的。

    (6)依次类推,每一趟比较次数减少依次

3.举例:要排序的数组  list1 = [7,4,2,14,3,24,135]  

list1 = [7,4,2,14,3,24,135]
for i in range(len(list1)):
  for j in range(0,len(list1)-i-1):
    if list1[j] > list1[j+1]:
      list1[j],list1[j+1] = list1[j+1],list1[j]
print(list1)

(1),第一趟排序

      第一次排序:7和4比较,7大于4,交换位置       [4,7,2,14,3,24,135]

      第二次排序:7和2比较,7大于2,交换位置  [4,2,7,14,3,24,135]

      第三次排序:7和14比较,7小于14,不交换位置  [4,2,7,14,3,24,135]

      第四次排序:14和3比较,14大于3,交换位置  [4,2,7,3,14,24,135]

        第五次排序:14和24比较,14小于24,不交换位置   [4,2,7,3,14,24,135]

      第六次排序:24和135比较,24小于135,不交换位置   [4,2,7,3,14,24,135]

      第一趟总共进行了六次比较,排序结果:[4,2,7,3,14,24,135]

(2),第一趟排序

      第一次排序:4和4比较,4大于2,交换位置       [2,4,7,3,14,24,135]

      第二次排序:4和7比较,4小于7,不交换位置  [2,4,7,3,14,24,135]

      第三次排序:7和3比较,7大于3,交换位置  [2,4,3,7,14,24,135]

         第四次排序:7和14比较,7小于14,不交换位置   [4,2,7,3,14,24,135]

      第五次排序:14和24比较,14小于24,不交换位置   [4,2,7,3,14,24,135]

......

算法分析:
    (1)由此可见:N个数字要排序完成,总共进行N趟排序,每i趟的排序次数为(N-i)次,所以可以用双重循环语句,外层控制循环多少趟,内层控制每一趟的循环次数
    (2)冒泡排序的优点:每进行一趟排序,就会少比较一次,因为每进行一趟排序都会找出一个较大值。如上例:第一趟比较之后,排在最后的一个数一定是最大的一个数,第二趟排序的时候,只需要比较除了最后一个数以外的其他的数,同样也能找出一个最大的数排在参与第二趟比较的数后面,第三趟比较的时候,只需要比较除了最后两个数以外的其他的数,以此类推……也就是说,每进行一趟比较,每一趟少比较一次,一定程度上减少了算法的量。

加油
原文地址:https://www.cnblogs.com/huahuacheng/p/14232846.html