排序算法

直接插入排序

算法思想：

采用减治法，将数组分成已排序和未排序两部分，每次将未排序的第一个元素插入到已排序部分的适当位置。

算法实现（C++）

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

算法分析

时间复杂度：
- 最优情况：O(n) （当数组已经是有序的）
- 最差情况：O(n^2) （当数组是反序的）
- 平均情况：O(n^2)
空间复杂度：O(1) （只需要常数级别的辅助空间）
稳定性：稳定，因为在插入过程中，如果当前元素等于已经排序好的元素，插入时不会改变它们的相对顺序。

希尔排序

又称“缩小增量排序 Diminishing Increment Sort”

算法思想：

希尔排序是对插入排序的改进，首先将数组按一定间隔进行分组，在每组内进行插入排序，随着间隔逐渐减少，最终使数组基本有序。

算法实现（C++）

void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

算法分析

时间复杂度：
- 最优情况：O(n log n)
- 最差情况：O(n^2)
- 平均情况：取决于间隔序列，通常为O(n log n)
空间复杂度：O(1)
稳定性：不稳定，因为在分组进行插入排序时，元素可能会跨越较大的间隔进行交换，导致相同元素的相对顺序被打乱。

冒泡排序

算法思想：

冒泡排序通过多次遍历，交换相邻逆序的元素，使得每轮遍历后最大的元素逐渐移动到数组末尾。

算法实现（C++）

void bubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

算法分析

时间复杂度：
- 最优情况：O(n) （当数组已经有序）
- 最差情况：O(n^2)
- 平均情况：O(n^2)
空间复杂度：O(1)
稳定性：稳定，因为相邻元素的比较与交换不会改变相同元素的相对顺序，因此保持了稳定性。

简单选择排序

算法思想：

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

算法实现（C++）

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

算法分析

时间复杂度：
- 最优情况：O(n^2)
- 最差情况：O(n^2)
- 平均情况：O(n^2)
空间复杂度：O(1)
稳定性：不稳定，因为在寻找最小元素时，可能会交换不相邻的相同元素，从而打乱它们的相对顺序。

快速排序

算法思想：

采用分治法，选取一个基准元素，将数组分为两部分，左边小于基准，右边大于基准，对两部分分别递归排序。

算法实现（C++）

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++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::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);
    }
}

算法分析

时间复杂度：
- 最优情况：O(n log n)
- 最差情况：O(n^2) （当每次划分极不均匀）
- 平均情况：O(n log n)
空间复杂度：O(log n)（递归栈空间）
稳定性：不稳定，因为在划分过程中的交换操作可能会改变相同元素的相对顺序。虽然可以通过修改实现使其稳定，但标准实现是不稳定的。

堆排序

算法思想：

采用变治法，首先将数组构建为一个最大堆，然后依次将堆顶元素与末尾元素交换，减少堆的大小，并调整堆。

算法实现（C++）

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) {
    // 1. 构建最大堆
    // 从最后一个非叶子节点开始向上构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 2. 进行排序
    // 一个个将堆顶（最大元素）移到数组的最后
    for (int i = n - 1; i > 0; i--) {
        // 将当前最大值（堆顶元素）放到数组末尾
        swap(arr[0], arr[i]);

        // 重新调整剩余部分为最大堆
        heapify(arr, i, 0);
    }
}

算法分析

时间复杂度：
- 最优情况：O(n log n)
- 最差情况：O(n log n)
- 平均情况：O(n log n)
空间复杂度：O(1)
稳定性：不稳定，因为在堆调整过程中，父节点与子节点交换时，可能会改变相同元素的相对顺序。

归并排序

算法思想：

采用分治法，将数组分成两部分，对两部分分别排序，然后将它们合并成一个有序数组。

算法实现（C++）

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

算法分析

时间复杂度：
- 最优情况：O(n log n)
- 最差情况：O(n log n)
- 平均情况：O(n log n)
空间复杂度：O(n)
稳定性：稳定，在合并两个有序数组时，保持了相同元素的相对顺序，因此它是稳定的排序算法。

拓扑排序

算法思想：

采用减治法，针对有向无环图（DAG），找到入度为0的顶点，移除该顶点，并更新其相邻顶点的入度，重复直到图为空。

算法实现（C++）

#include <iostream>
#include <vector>
#include <queue>

void topologicalSort(std::vector<int> adj[], int V) {
    std::vector<int> in_degree(V, 0);

    for (int u = 0; u < V; u++) {
        for (int v : adj[u]) {
            in_degree[v]++;
        }
    }

    std::queue<int> q;


    for (int i = 0; i < V; i++) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    int count = 0;
    std::vector<int> top_order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        top_order.push_back(u);

        for (int v : adj[u]) {
            if (--in_degree[v] == 0) {
                q.push(v);
            }
        }

        count++;
    }

    if (count != V) {
        std::cout << "Graph contains a cycle\n";
        return;
    }

    for (int i : top_order) {
        std::cout << i << " ";
    }
}

算法分析

时间复杂度：O(V + E)
空间复杂度：O(V)

基数排序

基数排序是一种非比较排序算法，它将数据按位（digit-by-digit）进行排序，适用于整数或字符串等可以分解为“位”的数据。基数排序的核心思想是将数据按照位（从低位到高位，或从高位到低位）逐位排序，并依次完成所有位的排序，最终得到有序的结果。

基数排序可以采用两种方式：

LSD（Least Significant Digit）从最低有效位开始排序。
MSD（Most Significant Digit）从最高有效位开始排序。

算法实现（C++）

// 获取数组中的最大值
int getMax(int arr[], int n) {
    int max_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val)
            max_val = arr[i];
    }
    return max_val;
}

// 对数组 arr[] 进行计数排序，按照 exp 位进行排序
void countSort(int arr[], int n, int exp) {
    int output[n]; // 输出数组
    int count[10] = {0}; // 计数数组

    // 统计每个桶中的元素个数
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    // 将计数数组转换为位置数组，调整为实际输出位置
    for (int i = 1; i < 10; i++)
        // 累加计数数组，确定每个数字在输出数组中的位置
        count[i] += count[i - 1];

    // 根据当前位的值，将元素放到输出数组中
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // 将输出数组的值复制回原数组
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

// 基数排序函数
void radixSort(int arr[], int n) {
    // 找到数组中的最大值，确定排序的位数
    int max_val = getMax(arr, n);

    // 从个位开始对数组进行排序，exp 是当前的位数，1 表示个位，10 表示十位，以此类推
    for (int exp = 1; max_val / exp > 0; exp *= 10)
        countSort(arr, n, exp);
}

算法分析

时间复杂度：

基数排序的时间复杂度取决于数字的位数和每次位排序的复杂度。
如果有 d 位数字，每次位的排序采用 O(n) 的线性排序算法（如计数排序），则基数排序的时间复杂度为 O(d * n)。对于固定位数的整数，d 是一个常数，基数排序的时间复杂度接近 O(n)。

空间复杂度：

基数排序的空间复杂度为 O(n + k)，其中 n 是数组的大小，k 是计数排序中可能的数值范围（对于十进制来说，k = 10）。

稳定性：

基数排序是稳定的，因为它在对每一位进行排序时使用的是稳定的排序算法（如计数排序），保证了相同值的相对顺序不会改变。

菜单

分享

直接插入排序

算法实现（C++）

算法分析

希尔排序

算法实现（C++）

算法分析

冒泡排序

算法实现（C++）

算法分析

简单选择排序

算法实现（C++）

算法分析

快速排序

算法实现（C++）

算法分析

堆排序

算法实现（C++）

算法分析

归并排序

算法实现（C++）

算法分析

拓扑排序

算法实现（C++）

算法分析

基数排序

算法实现（C++）

算法分析

遍历二叉树和线索二叉树

排序算法

栈和队列

常见树形结构及其算法分析