L4_06 排序算法

一、冒泡排序

1.1 原理

重复遍历数组，比较相邻元素，如果顺序错误就交换。

1.2 代码实现

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    bubbleSort(arr, n);
    
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

1.3 时间复杂度

• 最好：O(n)（已排序）
• 平均：O(n²)
• 最坏：O(n²)

---

二、插入排序

2.1 原理

将未排序元素插入到已排序部分的正确位置。

2.2 代码实现

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    insertionSort(arr, n);
    
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

2.3 时间复杂度

• 最好：O(n)（已排序）
• 平均：O(n²)
• 最坏：O(n²)

---

三、选择排序

3.1 原理

每次从未排序部分选择最小元素放到已排序部分的末尾。

3.2 代码实现

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        swap(arr[i], arr[min_idx]);
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    selectionSort(arr, n);
    
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

3.3 时间复杂度

• 最好：O(n²)
• 平均：O(n²)
• 最坏：O(n²)

---

四、时间复杂度

4.1 常见复杂度比较

复杂度	描述	示例
O(1)	常数时间	数组访问
O(log n)	对数时间	二分查找
O(n)	线性时间	顺序查找
O(n log n)	线性对数时间	快速排序、归并排序
O(n²)	平方时间	冒泡排序、插入排序

4.2 复杂度曲线

n=100时:
- O(n) = 100
- O(n log n) ≈ 700
- O(n²) = 10000

---

五、空间复杂度

5.1 定义

算法执行过程中所需的额外存储空间。

5.2 示例

// O(1) 空间复杂度
void swap(int &a, int &b) {
    int temp = a;  // 只使用常量空间
    a = b;
    b = temp;
}

// O(n) 空间复杂度
int* copyArray(int arr[], int n) {
    int *newArr = new int[n];  // 使用线性空间
    for (int i = 0; i < n; i++) {
        newArr[i] = arr[i];
    }
    return newArr;
}

---

六、算法稳定性

6.1 定义

如果两个相等的元素在排序前后相对顺序不变，则算法是稳定的。

6.2 稳定性对比

排序算法	是否稳定
冒泡排序	是
插入排序	是
选择排序	否

---

七、简单算法复杂度的估算

7.1 估算方法

1. 确定基本操作
2. 分析循环次数
3. 计算总操作次数

7.2 示例分析

void example(int n) {
    // O(1)
    int a = 1;
    
    // O(n)
    for (int i = 0; i < n; i++) {
        cout << i;
    }
    
    // O(n²)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << i + j;
        }
    }
}
// 总复杂度：O(1) + O(n) + O(n²) = O(n²)

---

八、示例程序

#include <iostream>
#include <ctime>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "排序前: ";
    printArray(arr, n);
    
    clock_t start = clock();
    bubbleSort(arr, n);
    clock_t end = clock();
    
    cout << "排序后: ";
    printArray(arr, n);
    cout << "耗时: " << (end - start) << "ms" << endl;
    
    return 0;
}