非基于比较的排序算法 - O(N)

1. 计数排序
2. 基数排序

由于不比较元素对，它们比基于比较的排序最优解O(N log N)还要快。

稳定排序算法

当排序完成之后，值相同的元素的相对为止保持不变的算法，称之为稳定排序算法。

基于比较的算法 复杂度O(N²)

我们讨论三种基于比较的算法：

1. 冒泡
2. 选择
3. 插入

因为这些算法需要比较两个元素以决定是否交换位置，故称基于比较的算法。

这三种算法最容易实现，但不是最高效的。其时间复杂度是O(N²)。

排序问题和排序算法

排序是一个经典的重排元素顺序的问题（其元素可以是整型、浮点型、字符串等可比较的类型）。可以重排为递增序列、非递减序列¹，递减序列，非递增序列²。

排序算法非常多，各有优势与其限制。

排序通常是大学计算机学科中，介绍算法思想的入门问题。

不失一般性的，假定在本教学中我们只以非递减顺序排序整型，元素无需排重。

①链表 ②栈 ③队列 ④双向链表 ⑤双端队列

这物种结构的插入操作都是相同的，而查找/插入/移除有些微差别。

• 栈，只能从头/栈顶执行peek/push/pop操作，都是严格受限的。
• 队列，只能从队首peek，从队尾push，从队首pop。
• 双端队列，只能从两端peek/enqueue/dequeue，而不能从中间操作。

顺序链表和双向链表没有上述限制。

双端队列——Double-ended queue缩写deque，读作deck。其元素只能两端添加或删除，即只能从头部/尾部添加或删除。

双向链表和顺序链表99%都是相同的。主要的区别是：每个节点包含两个指针，next指针指向后一个元素（若存在）即a_j指向a_j+1，另一个prev指针指向前一个元素，即a_j指向a_j-1（若存在）。

prev指针是的双向链表能够反向遍历，但同时也增加了内存的消耗。它解决了顺序链表中移除尾元素的低效问题。

队列这种ADT中，元素是有序的，主要操作有enqueue入队和dequeue出队。

即Fist-In-First-Out(FIFO)。最下进入队列的元素，会最后出队列。

Stack栈是一种数据结构，它要求只能从顶部增加元素即push，只能从顶部移除元素即pop。亦即Last-In-First-out(LIFO)。