冒泡排序---程序员必经之路

时间:2023-02-18 11:49:00

一、 冒泡排序的概念及简单理解

冒泡排序(Bubble Sort)是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素的大小,如果他们的顺序错误就把他们交换过来。重复地走访数列直到没有再需要交换。

以一个简单的例子理解冒泡排序过程:

待排序数组:5,1,3,4

第一趟排序:5,1,3,4(开始)→ 1,5,3,4 → 1,3,5,4 → 1,3,4,5   (发生三次比较:5与1比,交换;5与3比,交换;5与4比,交换。此时确认5是最大数,移到最右)

第二趟排序:1,3,4,5(开始)→ 1,3,4,5 →  1,3,4,5                    (发生两次比较:1与3比,不交换;3与4比,不交换。此时确认4为次大数)

第三趟排序:1,3,4,5(开始)→ 1,3,4,5                                       (发生一次比较:1与3比,不交换。 此时确认3为第三大的数)

至此,已经确认5、4、3分别为最大、次大和第三大的数,由于整个数组只有四个元素,故排序已经完成。

总结

1、n个元素的数列进行冒泡排序,最多需要循环进行n-1次排序;

2、每次排序循环中,发生比较的次数是递减1的;

3、在第x次循环排序中,如果没有任何元素发生位置交换,则认为排序在x-1次循环后已经完成,后续循环无需继续(如上例,第二趟循环无交换,因为第一次循环后排序已完成)

 

二、 冒泡排序之Python实现

#  1.原始方法,不考虑排序中途完成的情况

nums = [5,1,3,4]
length = len(nums)
count = 0
for i in range(length-1):
    count += 1
    for j in range(length-i-1):
        if nums[j]>nums[j+1]:
            nums[j+1],nums[j] = nums[j],nums[j+1]
print(nums,'排序{}次'.format(count))

[1, 3, 4, 5] 排序3次

#  2.考虑排序中途完成,省略后续的排序过程

nums = [5,1,3,4]
length = len(nums)
count = -1
for i in range(length): #多走一次循环用于排序是否完成的判断
    flag = True
    count +=1
    for j in range(length-i-1):
        if nums[j]>nums[j+1]:
            nums[j+1],nums[j] = nums[j],nums[j+1]  #swap
            flag = False
    if flag:
        break
print(nums,'排序{}次'.format(count))

[1, 3, 4, 5] 排序1次

 

三、 冒泡排序总结

1、冒泡排序需要循环排序的次数最多为length-1

2、可能存在中间某趟就已经排序OK的情况,需设定一个标记位进行判断某趟排序中是否有位置交换,如无则排序完成,可break

3、最差的情况:初始顺序刚好是倒序。遍历次数为1,2,3,...n-1的和 即n(n-1)/2

4、最好的情况:初始顺序刚好是目标顺序,遍历次数为n-1次,即第一趟排序就发现无位置交换

5、时间复杂度为O(n2)