O(n^2) 平方时间复杂度与简单排序算法比较

# 1. 时间复杂度简介

## 1.1 什么是时间复杂度

时间复杂度是算法运行所需时间与问题规模之间的关系，用大O符号来表示。它反映了算法运行时间的增长率，是对一个算法运行时间的估计。

常见的时间复杂度包括O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)等。

## 1.2 如何分析时间复杂度

分析时间复杂度时，通常关注算法执行次数随输入规模增长的趋势。可以通过代码中循环次数、可能性的分支判断来推导出算法的时间复杂度。

常见的时间复杂度分析方法包括最好情况、最坏情况、平均情况分析等。下面通过一个表格简单说明几种常见时间复杂度的特点：

| 时间复杂度 | 表示 | 特点 |
|----------|------|----------------------------------------|
| O(1) | 常数阶 | 算法的执行时间不随问题规模变化而变化 |
| O(logn) | 对数阶 | 算法的执行时间随问题规模增大而增长，但增长缓慢 |
| O(n) | 线性阶 | 算法的执行时间随问题规模线性增加，时间与规模成正比 |
| O(nlogn) | 线性对数阶 | 常见于快速排序、归并排序等，介于线性和平方之间 |
| O(n^2) | 平方阶 | 算法的执行时间随问题规模的平方增加，时间与规模平方成正比 |

以上为常见时间复杂度的特点，对于不同问题可根据具体情况选择合适的算法以达到更加高效的计算效果。

# 2. O(n^2) 时间复杂度算法

### 2.1 冒泡排序
冒泡排序是一种简单直观的排序算法，其基本思想是两两比较相邻元素的大小，如果顺序错误就交换位置，直至整个数组排序完成。

#### 算法步骤：
1. 从第一个元素开始，依次比较相邻元素大小，若逆序则交换位置。
2. 继续对每一对相邻元素进行比较和交换，直到最后一对元素。
3. 重复上述步骤，直至没有任何一对元素需要比较交换。

#### 代码示例（Python）：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        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)

#### 结果说明：
通过冒泡排序算法对示例数组进行排序，最终得到的排序结果为 `[11, 12, 22, 25, 34, 64, 90]`。冒泡排序时间复杂度为O(n^2)。

### 2.2 选择排序
选择排序是一种简单直观的排序算法，其基本思想是每次从未排序的部分选择最小（或最大）的元素，放到已排序部分的末尾。

#### 算法步骤：
1. 遍历数组，找到最小元素的索引位置。
2. 将找到的最小元素与未排序部分的第一个元素交换位置。
3. 重复上述步骤，直至整个数组排序完成。

#### 代码示例（Python）：

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]
    return arr

# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = selection_sort(arr)
print("排序后的数组：", sorted_arr)

#### 结果说明：
通过选择排序算法对示例数组进行排序，最终得到的排序结果为 `[11, 12, 22, 25, 34, 64, 90]`。选择排序时间复杂度为O(n^2)。

# 3. O(nlogn) 时间复杂度算法

#### 3.1 快速排序
快速排序是一种经典的分治算法，通过不断地选取基准值，将数组分成左右两部分，然后递归地对左右子数组进行排序。

快速排序的步骤：
1. 选择一个基准值pivot，一般选择数组中间值。
2. 将数组分成两部分，左边部分的值都小于pivot，右边部分的值都大于pivot。
3. 递归地对左右两部分进行排序。

快速排序的实现代码如下（以Python为例）：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# 示例
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print(sorted_arr)

快速排序的时间复杂度为O(nlogn)，在平均情况下具有较好的性能，但在最坏情况下可能退化到O(n^2)。

#### 3.2 归并排序
归并排序是一种稳定的排序算法，基于分治思想，将数组分成两个子数组，分别排序后再合并。

归并排序的步骤：
1. 将数组不断地二分，直到每个子数组只有一个元素。
2. 合并两个有序的子数组，直到整个数组有序。

归并排序的实现代码如下（以Python为例）：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i