排序算法的时间复杂度分析

# 1. 排序算法简介
排序算法在计算机科学中是一个基础且重要的概念。通过对数据的排序，我们可以更高效地搜索和查找所需的信息。在实际开发中，排序算法的选择直接影响到程序的性能和效率。因此，了解不同排序算法之间的差异以及它们的时间复杂度是至关重要的。在本章中，我们将介绍排序算法的基本概念、重要性以及常见的分类。

# 2. 时间复杂度简述

在排序算法中时间复杂度是一个至关重要的概念。接下来我们将初步介绍时间复杂度的定义、意义和如何计算时间复杂度。让我们深入了解这个关键概念。

# 3. 常见排序算法及时间复杂度分析

在本章中，我们将介绍一些常见的排序算法，并对它们的时间复杂度进行分析。

#### 3.1 冒泡排序算法及其时间复杂度

冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就将它们交换位置。

下面是Python实现冒泡排序的代码：

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

# 测试冒泡排序
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("排序后的数组:", sorted_arr)

冒泡排序的时间复杂度为O(n^2)，其中n是要排序数组的元素个数。

#### 3.2 选择排序算法及其时间复杂度

选择排序是一种简单直观的排序算法，它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置。

以下是Java实现选择排序的代码示例：

public class SelectionSort {
    public void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }