冒泡排序代码及时间空间复杂度

冒泡排序是一种基本的排序算法，它通过多次交换相邻元素的位置来将一个数组按照升序或降序进行排序。以下是冒泡排序的代码示例以及时间和空间复杂度分析，希望对大家有所帮助。北京木奇移动技术有限公司，专业的软件外包开发公司，欢迎交流合作。

冒泡排序的代码示例（升序排序）：

def bubble_sort(arr):

n = len(arr)

for i in range(n):

# 标记是否发生交换，若未发生则说明已经有序，可提前退出

swapped = False

# 每次循环将最大元素冒泡到末尾

for j in range(0, n-i-1):

if arr[j] > arr[j+1]:

# 交换相邻元素

arr[j], arr[j+1] = arr[j+1], arr[j]

swapped = True

# 如果一轮循环未发生交换，说明已经有序，可提前退出

if not swapped:

break

# 示例

arr = [64, 34, 25, 12, 22, 11, 90]

bubble_sort(arr)

print("排序后的数组：", arr)

时间复杂度分析：

冒泡排序的时间复杂度取决于数组中元素的个数（n）。最坏情况下，冒泡排序需要进行 n-1 轮比较和交换。每一轮比较需要比较 n-i-1 次，其中 i 是当前轮次。因此，最坏情况下的时间复杂度是 O(n^2)。在最好的情况下，如果输入数据已经是有序的，冒泡排序的时间复杂度是 O(n)。

空间复杂度分析：

冒泡排序是一种原地排序算法，它不需要额外的空间来存储数据，因此其空间复杂度是 O(1)，即常数级别的空间消耗。

总结：冒泡排序虽然容易理解和实现，但由于其最坏情况下的时间复杂度为 O(n^2)，在大规模数据集上性能较差。通常情况下，更高效的排序算法，如快速排序和归并排序，更常被使用。