冒泡排序

比较相邻元素，如果顺序错误则交换，每轮将最大（升序）或最小（降序）元素 “冒泡” 到末尾。重复此过程，直到数组有序

static void BubbleSort(int[] arr) {
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

• 时间复杂度：平均和最坏情况为 O(n2)，最好情况（数组已有序）为 O(n)。
• 空间复杂度：O(1)，属于原地排序。
• 稳定性：稳定排序算法，相同元素相对顺序不变。

选择排序

• 原理：每轮从未排序元素中选择最小（升序）或最大（降序）元素，与未排序部分第一个元素交换位置，逐步完成排序。

static void SelectionSort(int[] arr) {
    int n = arr.Length;
    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;
            }
        }
        if (minIndex!= i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

• 时间复杂度：无论数组初始状态如何，均为 O(n2)。
• 空间复杂度：O(1)，原地排序。
• 稳定性：不稳定排序算法，相同元素相对顺序可能改变。

1. 对比
   • 时间复杂度：平均情况下两者相同，但冒泡排序在最好情况下性能更好。
   • 稳定性：冒泡排序稳定，选择排序不稳定。
   • 适用场景：都适用于小规模数据排序；若数据基本有序，冒泡排序更优。

集合

ArrayList

• 特点：动态数组，可按需自动调整大小，存储不同类型对象（类型不安全）。
• 常用 API：
  • Add(object value)：添加元素到列表末尾。
  • Insert(int index, object value)：在指定索引处插入元素。
  • Remove(object value)：移除指定元素。
  • RemoveAt(int index)：移除指定索引处元素。
  • Contains(object value)：检查列表是否包含指定元素。

ArrayList list = new ArrayList();
list.Add(10);
list.Insert(0, 5);
list.Remove(10);
bool contains = list.Contains(5);

List<T>

• 特点：泛型列表，类型安全，可动态调整大小，只能存储指定类型 T 的元素。
• 常用 API：
  • Add(T item)：添加元素到列表末尾。
  • Insert(int index, T item)：在指定索引处插入元素。
  • Remove(T item)：移除指定元素。
  • RemoveAt(int index)：移除指定索引处元素。
  • Contains(T item)：检查列表是否包含指定元素。
  • Find(Predicate<T> match)：查找满足条件的第一个元素。
  • FindAll(Predicate<T> match)：查找满足条件的所有元素。

List<int> intList = new List<int>();
intList.Add(10);
intList.Insert(0, 5);
intList.Remove(10);
bool contains = intList.Contains(5);
int firstMatch = intList.Find(i => i > 5);

对比

• 类型安全性：List<T> 类型安全，ArrayList 不安全，可能导致运行时类型错误。
• 性能：List<T> 性能更好，因为避免了装箱和拆箱操作（ArrayList 存储值类型时需装箱拆箱）。
• 适用场景：若需存储多种类型元素，使用 ArrayList；否则优先选择 List<T>。

字典（Dictionary<TKey, TValue>）

• 特点：键值对集合，键唯一，通过键快速查找对应值，无序存储。
• 常用 API：
  • Add(TKey key, TValue value)：添加键值对。
  • TryGetValue(TKey key, out TValue value)：尝试获取指定键对应的值。
  • Remove(TKey key)：移除指定键的键值对。
  • ContainsKey(TKey key)：检查是否包含指定键。
  • ContainsValue(TValue value)：检查是否包含指定值。

Dictionary<string, int> dict = new Dictionary<string, int>();
dict.Add("one", 1);
int value;
bool success = dict.TryGetValue("one", out value);
dict.Remove("one");
bool containsKey = dict.ContainsKey("one");
bool containsValue = dict.ContainsValue(1);

与列表对比

• 存储方式：列表按顺序存储单个元素，字典按键值对存储，通过键访问值。
• 查找效率：字典通过键查找值效率高（平均 O(1)），列表查找需遍历（O(n)），除非已知索引。
• 适用场景：需快速通过特定标识查找数据，用字典；需顺序存储和访问元素，用列表。