37.2° Blog

1.概念

将各元素按关键字递增或递减顺序重新排列

2.评价指标

稳定性

关键字相同的元素经过排序后相对顺序是否发生变化

时间复杂度

空间复杂度

3.分类

内部排序

• 数据在内存中
• 考虑时间、空间复杂度
• 一般需要比较和移动操作

外部排序

• 数据太多，无法全部放入内存
• 考虑时间、空间复杂度和磁盘读写次数

4.初始化

// 顺序表定义
typedef struct 
{
    ElemType* data;
    int length;
    int maxSize;
}SqList;

// 初始化顺序表
void initSqList(SqList& L)
{
    L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
    L.length = 0;
    L.maxSize = MaxSize;
}