线性表

ADT

ADT: a set of objects together with a set of operations. Abstract data types are mathematical abstractions;nowhere in an ADT’s definition is there any mention of how the set of operations is implemented.

data structure is a data object together with the relationships among the instances and among the individual elements that compose an instance

\[Data_Structure = \{D,R\}\]

线性表

线性表的操作：

Create a linear list determine whether the list is empty determine the length of the list find the kth of the element search for a given element delete the kth element insert a new element just after the kth

数组

数组的本质：向系统索要了连续的一块内存空间，线性表中的元素被依次存放进这块内存里。

当我使用下标来查找元素，时间复杂度是\(O(1)\)，因为我进行的工作实际上只是通过下标计算我想要得到的元素的地址，也就是CPL里学过的arr[i]=*(arr+i)

search(x):O(n)

remove(k,x):O(n)

insert(k,x):O(n)

链表

链表的内存并不是连续的，因此要把链表作为一个整体，必须要有一个指针把各个元素联系起来

操作	时间复杂度	推导原因
访问	O(n)	必须从头部开始，逐个节点遍历，直到找到目标位置。平均需要扫描 n/2 个节点。
搜索	O(n)	必须遍历每个节点，检查其数据是否匹配目标值。最坏情况需要扫描全部 n 个节点。
插入	O(1)	已知操作位置的前驱节点时（如头部插入、或给定节点后插入），仅需修改几个指针。
删除	O(1)	已知操作位置的前驱节点时（如删除头节点、或给定节点的后一个节点），仅需修改指针。
在指定索引处插入/删除	O(n)	主要时间开销在于遍历到指定索引位置（O(n)），找到其前驱节点后，实际插入/删除操作仅为 O(1)。

双向链表

基数排序

核心思想：将整数按位数（“基数”）切割成不同的数字，然后按每个位数分别进行排序。

基数排序从最低有效位（LSD）到最高有效位（MSD），或从MSD到LSD，逐位进行排序。通常使用LSD方法更为常见和直观。

算法原理（以LSD为例）

基数排序的原理基于一个关键事实：一个高位数字的权重大于低位数字。如果我们先按低位排序，然后再按高位排序，那么低位已排序的顺序在高位相同的情况下会自动得到保持。

步骤：

1. 获取最大值：找到待排序数组中的最大数字，以确定需要处理的位数（例如，最大值是 356，那么最多有 3 位数）。
2. 初始化桶：创建10个“桶”（队列或列表），编号从0到9，分别对应每个位上可能的10个数字（0-9）。
3. 从最低位开始循环：从个位开始，依次向十位、百位…最高位进行遍历。对于每一位： a. 分配：遍历整个数组，根据当前位的数字，将每个元素放入对应的桶中。 b. 收集：按桶的编号顺序（0号桶 -> 1号桶 -> … -> 9号桶），依次将每个桶中的元素取出，放回原数组。
4. 重复步骤3：处理完最高位后，整个数组就变成了有序数组。

代码实现

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// 链表节点定义
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 基数排序实现（使用链表）
ListNode* radixSort(ListNode* head) {
    if (!head || !head->next) return head;
    
    // 找到链表中的最大值，确定需要处理的位数
    int max_val = head->val;
    ListNode* curr = head;
    while (curr) {
        max_val = max(max_val, curr->val);
        curr = curr->next;
    }
    
    // 计算最大位数
    int max_digits = 0;
    int temp = max_val;
    while (temp > 0) {
        max_digits++;
        temp /= 10;
    }
    if (max_digits == 0) max_digits = 1; // 处理全0的情况
    
    // 创建10个桶（使用list容器）
    vector<list<ListNode*>> buckets(10);
    
    // 从最低位到最高位进行排序
    int exp = 1;
    for (int digit = 0; digit < max_digits; digit++) {
        // 分配阶段：将节点放入对应的桶中
        curr = head;
        while (curr) {
            int bucket_index = (curr->val / exp) % 10;
            buckets[bucket_index].push_back(curr);
            curr = curr->next;
        }
        
        // 收集阶段：将桶中的节点重新连接成链表
        ListNode* new_head = nullptr;
        ListNode* tail = nullptr;
        
        for (int i = 0; i < 10; i++) {
            for (ListNode* node : buckets[i]) {
                if (!new_head) {
                    new_head = node;
                    tail = node;
                } else {
                    tail->next = node;
                    tail = node;
                }
            }
            buckets[i].clear(); // 清空桶以备下次使用
        }
        
        // 确保链表以nullptr结尾
        if (tail) tail->next = nullptr;
        
        head = new_head;
        exp *= 10; // 移动到下一位
    }
    
    return head;
}

// 创建链表（从vector）
ListNode* createList(const vector<int>& nums) {
    if (nums.empty()) return nullptr;
    
    ListNode* head = new ListNode(nums[0]);
    ListNode* curr = head;
    
    for (size_t i = 1; i < nums.size(); i++) {
        curr->next = new ListNode(nums[i]);
        curr = curr->next;
    }
    
    return head;
}

// 打印链表
void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr) {
        cout << curr->val;
        if (curr->next) cout << " -> ";
        curr = curr->next;
    }
    cout << endl;
}

// 释放链表内存
void deleteList(ListNode* head) {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

复杂度分析

• 时间复杂度：O(d * (n + k))
  • n 是数组长度（元素个数）。
  • k 是“桶”的数量，对于十进制整数，k=10。
  • d 是最大数字的位数。
  • 它之所以快，是因为它避免了比较，而比较排序算法的下限是 O(n log n)。
• 空间复杂度：O(n + k)
  • 需要额外的空间来创建 k 个桶，以及存储 n 个元素。

优缺点

优点：

1. 高效：当位数 d 不大时，它可以比基于比较的排序算法（如快速排序、归并排序）更快。
2. 稳定排序：它保持相等元素的相对顺序，这个特性在某些场景下非常重要。

缺点：

1. 适用范围有限：主要用于排序整数或可以表示为整数的东西（如字符串）。对于浮点数或复杂对象排序困难。
2. 空间开销：需要额外的内存空间来创建桶。
3. 依赖数据特征：如果最大数字的位数 d 非常大，效率会下降。

总结

基数排序是一种巧妙的、稳定的非比较排序算法。它通过“分治”的思想，将整数按位拆分，逐位排序，从而巧妙地避免了元素间的直接比较。虽然有其应用限制，但在处理范围已知、位数不大的整数数据集时，它是一个非常高效的选择。