内部排序（Internal Sorting）

内部排序 指的是在**主存（内存）**中进行的排序，所有数据都能存储在内存中进行排序操作，不需要借助外部存储（如磁盘）。
内部排序的常见算法包括：

插入排序（Insertion Sort）
选择排序（Selection Sort）
交换排序（Bubble Sort, Quick Sort）
归并排序（Merge Sort）
堆排序（Heap Sort）
基数排序（Radix Sort）

其中，快速排序、归并排序、堆排序是最常用的高效排序方法。

1. 插入排序（Insertion Sort）

原理

每次将一个元素插入到已排序的部分，使序列仍然有序。
适用于少量数据或者接近有序的数组。

时间复杂度

最坏情况（逆序）：O(n²)
最好情况（已排序）：O(n)
平均时间复杂度：O(n²)

代码实现

#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;
    }
}

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

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "原始数组: ";
    printArray(arr, n);

    insertionSort(arr, n);

    cout << "排序后的数组: ";
    printArray(arr, n);

    return 0;
}

2. 选择排序（Selection Sort）

原理

每轮从未排序部分找到最小值，然后交换到前面。
适用于数据量小，但排序性能不如插入排序。

时间复杂度

最坏情况：O(n²)
最好情况：O(n²)
平均时间复杂度：O(n²)

代码实现

#include <iostream>

using namespace std;

void selectionSort(int arr[], int n) {
    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;
            }
        }
        swap(arr[i], arr[minIndex]); // 交换
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "原始数组: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    selectionSort(arr, n);

    cout << "排序后的数组: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

3. 快速排序（Quick Sort）

原理

选择一个基准元素，将小的放左边，大的放右边，递归处理。
适用于大规模数据排序，最优的平均时间复杂度为 O(n log n)。

时间复杂度

最坏情况（已排序数组）：O(n²)
最好情况（均衡分割）：O(n log n)
平均情况：O(n log n)

代码实现

#include <iostream>

using namespace std;

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]); // 交换基准到正确位置
    return i + 1;
}

// 递归快速排序
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "原始数组: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    quickSort(arr, 0, n - 1);

    cout << "排序后的数组: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

4. 堆排序（Heap Sort）

原理

通过堆数据结构建立最大堆（或最小堆），然后逐步调整排序。
适用于大规模数据排序。

时间复杂度

最坏情况：O(n log n)
最好情况：O(n log n)
平均时间复杂度：O(n log n)

代码实现

#include <iostream>

using namespace std;

// 堆调整
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

// 堆排序
void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "原始数组: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    heapSort(arr, n);

    cout << "排序后的数组: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

总结

排序方法	最坏时间复杂度	最好时间复杂度	平均时间复杂度	适用场景
插入排序	O(n²)	O(n)	O(n²)	小规模数据
选择排序	O(n²)	O(n²)	O(n²)	小规模数据
快速排序	O(n²)	O(n log n)	O(n log n)	大规模数据
堆排序	O(n log n)	O(n log n)	O(n log n)	大规模数据