python排序算法-冒泡排序优化

---

原理

冒泡排序是一种交换排序，核心是冒泡，把数组中最小的那个往上冒，冒的过程就是和他相邻的元素交换。
重复走访要排序的数列，通过两两比较相邻记录的排序码。排序过程中每次从后往前冒一个最小值，且每次能确定一个数在序列中的最终位置。若发生逆序，则交换；有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。

---

动图演示

二、代码

1.冒泡排序基本

代码如下（示例）：

def bubble_sort(arr):
    """
    基本冒泡排序
    :param arr:
    :return:
    """
    for i in range(len(arr) - 1):
        for j in range(len(arr) - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

2.冒泡排序优化

代码如下（示例）：

def bubble_sort_up1(arr):
    """
    优化：跳过已比较数据
    :param arr:
    :return:
    """
    for i in range(len(arr) - 1):
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

3.冒泡排序最终优化

代码如下（示例）：

def bubble_sort_up2(arr):
    """
    优化：跳过已比较数据，如果为有序直接退出
    :param arr:
    :return:
    """
    for i in range(len(arr) - 1):
        # 用于判断数组是否已经有序
        num = True
        # 跳过已经比较过的数据
        for j in range(len(arr) - i - 1):
            # 判断是否有序，如果无序将num置为false
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                num = False
        # 判断后为有序则直接结束
        if num:
            break
    return arr

时间复杂度：
O(n2)。

---

总结

工作随笔，希望可以帮助到大家！
如有不足之处，请多多指教！

转载：https://blog.csdn.net/black_lightning/article/details/115682440