排序

C++ 排序

sort 函数

// 头文件
#include <algorithm>

// 升序排序（默认）
sort(arr, arr + n);                    // 数组
sort(vec.begin(), vec.end());          // vector

// 降序排序
sort(arr, arr + n, greater<int>());    // 数组
sort(vec.begin(), vec.end(), greater<int>()); // vector

// 自定义比较函数
bool cmp(int a, int b) {
    return a > b;  // 降序
}
sort(arr, arr + n, cmp);

// 结构体排序
struct Point {
    int x, y;
    bool operator<(const Point& p) const {
        return x < p.x;  // 按x升序
    }
};
sort(points.begin(), points.end());

稳定排序

// stable_sort 保持相等元素的相对顺序
stable_sort(arr, arr + n);
stable_sort(vec.begin(), vec.end());

部分排序

// 部分排序，只保证第n个位置正确
nth_element(vec.begin(), vec.begin() + n, vec.end());

// 部分排序，对指定范围排序
partial_sort(vec.begin(), vec.begin() + n, vec.end());

Java 排序

Arrays 类排序

// 基本类型数组排序
Arrays.sort(arr);                      // 升序
Arrays.sort(arr, fromIndex, toIndex);  // 指定范围

// 降序排序（仅适用于对象数组）
Integer[] arr = {3, 1, 4, 1, 5};
Arrays.sort(arr, Collections.reverseOrder());

// 自定义比较器
Arrays.sort(arr, new Comparator<Integer>() {
    @Override
    public int compare(Integer a, Integer b) {
        return b - a;  // 降序
    }
});

// Lambda表达式
Arrays.sort(arr, (a, b) -> b - a);  // 降序

Collections 类排序

// List排序
List<Integer> list = new ArrayList<>();
Collections.sort(list);                // 升序
Collections.sort(list, Collections.reverseOrder());  // 降序

// 自定义比较器
Collections.sort(list, (a, b) -> b - a);  // 降序

对象排序

class Point implements Comparable<Point> {
    int x, y;
    
    @Override
    public int compareTo(Point p) {
        return this.x - p.x;  // 按x升序
    }
}

// 使用自然顺序
Arrays.sort(points);
Collections.sort(pointList);

// 使用比较器
Arrays.sort(points, (p1, p2) -> p1.y - p2.y);  // 按y升序

Python 排序

sorted 函数

# 列表排序
arr = sorted(nums)                     # 升序，返回新列表
arr = sorted(nums, reverse=True)       # 降序

# 自定义排序
arr = sorted(nums, key=lambda x: -x)   # 降序
arr = sorted(nums, key=abs)            # 按绝对值排序

# 多级排序
points = [(1, 2), (3, 1), (2, 3)]
arr = sorted(points, key=lambda p: (p[0], p[1]))  # 先按x后按y

list.sort 方法

# 原地排序
nums.sort()                            # 升序
nums.sort(reverse=True)                # 降序

# 自定义排序
nums.sort(key=lambda x: -x)            # 降序
nums.sort(key=abs)                     # 按绝对值排序

# 对象排序
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

points.sort(key=lambda p: p.x)         # 按x排序
points.sort(key=lambda p: (p.x, p.y))  # 先按x后按y

时间复杂度

• C++ sort：平均 ，最坏
• Java Arrays.sort：
  • 基本类型：双轴快速排序，平均
  • 对象类型：TimSort，平均
• Python sorted/sort：TimSort，平均

注意事项

1. C++ sort 不保证稳定性，需要稳定排序使用 stable_sort
2. Java 对基本类型和对象类型使用不同的排序算法
3. Python 的排序总是稳定的
4. 自定义比较函数要满足传递性
5. 优先使用语言内置的排序函数，而不是自己实现

经典例题

1. 排序
2. 活动安排
3. 小红的整数配对