import random import time def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr为这段代码加上注释

# 导入 random 和 time 模块
import random
import time

# 定义冒泡排序函数，参数为待排序的列表
def bubble_sort(arr):
    n = len(arr)  # 获取列表长度
    for i in range(n):  # 外层循环控制排序轮数
        for j in range(n-i-1):  # 内层循环控制每轮排序中的比较次数
            if arr[j] > arr[j+1]:  # 如果前一个数比后一个数大，则交换两个数的位置
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr  # 返回排好序的列表

注释的作用是为了让代码更易懂，方便阅读和维护。

相关问题

Implement three sorting algorithms: bubble sort, quicksort and heapsort. Use python to draw a figure showing how the running time of these sorting algorithms scales under different sizes of input arrays (e.g., 100, 500, 1000, 5000, 10000, …).

好的，我将用Python实现三个排序算法：冒泡排序，快速排序和堆排序，并绘制一张图表展示不同大小的输入数组下这些排序算法的运行时间。

以下是实现这三个算法的Python代码：

import random
import time

# 冒泡排序
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# 快速排序
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = [x for x in arr[1:] if x < pivot]
        right = [x for x in arr[1:] if x >= pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)

# 堆排序
def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[largest] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

# 测试排序算法的运行时间
def test_sorting_algorithm(algorithm, arr):
    start_time = time.time()
    algorithm(arr)
    end_time = time.time()
    return end_time - start_time

# 绘制排序算法的运行时间图表
def plot_running_time():
    sizes = [100, 500, 1000, 5000, 10000, 50000, 100000]
    bubble_sort_times = []
    quick_sort_times = []
    heap_sort_times = []
    for size in sizes:
        arr = [random.randint(0, 1000) for _ in range(size)]
        bubble_sort_times.append(test_sorting_algorithm(bubble_sort, arr))
        quick_sort_times.append(test_sorting_algorithm(quick_sort, arr))
        heap_sort_times.append(test_sorting_algorithm(heap_sort, arr))

    import matplotlib.pyplot as plt

    plt.plot(sizes, bubble_sort_times, label='Bubble Sort')
    plt.plot(sizes, quick_sort_times, label='Quick Sort')
    plt.plot(sizes, heap_sort_times, label='Heap Sort')
    plt.xlabel('Input size')
    plt.ylabel('Running time (seconds)')
    plt.title('Running time of sorting algorithms')
    plt.legend()
    plt.show()

plot_running_time()

上面的代码中，我们使用了Python的标准库`random`来生成随机数数组。`test_sorting_algorithm`函数用来测试给定排序算法在给定数组上的运行时间。`plot_running_time`函数则用来绘制排序算法的运行时间图表，它调用

排序算法比较代码，要求：用随机数产生100000个待排序元素的关键字值，测试排序函数的机器实际执行时间

以下是使用 Python 实现常见排序算法的比较代码，使用随机数生成100000个待排序元素并输出每个算法的执行时间：

import random
import time

# 生成随机数组
arr = [random.randint(1, 1000) for _ in range(100000)]

# 冒泡排序
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

start_time = time.time()
bubble_sort(arr)
end_time = time.time()
print("Bubble Sort:", end_time - start_time)

# 选择排序
def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

start_time = time.time()
selection_sort(arr)
end_time = time.time()
print("Selection Sort:", end_time - start_time)

# 插入排序
def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

start_time = time.time()
insertion_sort(arr)
end_time = time.time()
print("Insertion Sort:", end_time - start_time)

# 快速排序
def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi-1)
        quick_sort(arr, pi+1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low-1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

start_time = time.time()
quick_sort(arr, 0, len(arr)-1)
end_time = time.time()
print("Quick Sort:", end_time - start_time)

# 归并排序
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

start_time = time.time()
merge_sort(arr)
end_time = time.time()
print("Merge Sort:", end_time - start_time)

注意，不同机器的运行时间可能会有所不同。