内部排序

内部排序是指待排序数据可以全部放入内存中完成排序。它是数据结构学习中的核心内容。

一、排序分类

分类	算法
插入类	直接插入排序、希尔排序
交换类	冒泡排序、快速排序
选择类	简单选择排序、堆排序
归并类	归并排序
分配类	计数排序、桶排序、基数排序

二、稳定性

如果两个相等元素排序后相对顺序不变，则排序算法是稳定的。

稳定排序：

• 冒泡排序；
• 插入排序；
• 归并排序；
• 计数排序。

不稳定排序：

• 快速排序；
• 选择排序；
• 堆排序；
• 希尔排序。

三、常见复杂度

算法	平均时间	空间	稳定
冒泡排序	O(n²)	O(1)	是
插入排序	O(n²)	O(1)	是
选择排序	O(n²)	O(1)	否
快速排序	O(n log n)	O(log n)	否
归并排序	O(n log n)	O(n)	是
堆排序	O(n log n)	O(1)	否

四、快速排序

基本思想：

优点是平均性能好，缺点是极端情况下会退化。

五、归并排序

基本思想：

适合稳定排序和链表排序。

六、学习建议

• 先手写冒泡、插入、选择。
• 再理解快速排序和归并排序。
• 最后学习堆排序和非比较排序。
• 每个算法都要能说明复杂度和稳定性。