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`函数则用来绘制排序算法的运行时间图表，它调用

请编写复杂度为O(n 2 )、O(nlogn)、O(n)的任意程序，在不同问题规模下，记录运行时间，注明单位秒s或毫秒ms，对于运行时间过长的，给出预估时间。 鼓励使用不同语言（C/C++/Java/Python等）做比较。注意：编译时请不要用代码优化参数。

这是一个示例，我们将分别编写三个简单的算法，每个对应给定的时间复杂度：

1. O(n^2) 级别的冒泡排序算法（Python）：

import time

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(0, n-i-1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
    return lst

# 测试数据
test_list = [5, 3, 8, 6, 7, 1]

start_time = time.time()
sorted_list = bubble_sort(test_list.copy())
end_time = time.time()

print(f"Bubble Sort (n^2): {end_time - start_time} seconds")

这个算法在大数组上运行效率低，比如10000个元素，可能需要几秒钟。

2. O(n log n) 级别的快速排序算法（Java）：

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    public static void quickSort(int[] arr) {
        if (arr.length <= 1) return;
        int pivotIndex = partition(arr, 0, arr.length - 1);
        quickSort(arr, 0, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, arr.length - 1);
    }

    private static int partition(int[] arr, int low, int high) {
        // ...
    }

    public static void main(String[] args) {
        int[] testArray = new Random().ints(10000).toArray();
        long startTime = System.nanoTime();
        quickSort(Arrays.copyOf(testArray, testArray.length));
        long endTime = System.nanoTime();

        double elapsedSeconds = (endTime - startTime) / 1_000_000_000.0; // convert nanoseconds to seconds
        System.out.printf("Quick Sort (n log n): %.3f seconds\n", elapsedSeconds);
    }
}

这个算法对于同样大小的数据，预计在几毫秒内完成。

3. O(n) 级别的查找算法（C++）：

#include <iostream>
#include <vector>

int linear_search(std::vector<int>& nums, int target) {
    for (size_t i = 0; i < nums.size(); ++i) {
        if (nums[i] == target) return i;
    }
    return -1;
}

int main() {
    std::vector<int> testVector{1, 2, 3, 4, 5};
    int target = 3;

    auto start_time = std::chrono::high_resolution_clock::now();
    int result = linear_search(testVector, target);
    auto end_time = std::chrono::high_resolution_clock::now();

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time).count();
    float elapsedMicroseconds = static_cast<float>(duration) / 1000.0f; // convert microseconds to milliseconds

    std::cout << "Linear Search (n): " << elapsedMicroseconds << " milliseconds\n";
}

线性搜索在小到中等规模数据上应该几乎瞬间完成，例如几千个元素。

请注意，实际运行时间可能会因为计算机性能、操作系统调度等因素有所不同。在大型生产环境中，为了准确测量运行时间，通常会使用专门的性能分析工具。