数据结构与算法总结（4）：你能列举各类排序算法的特点吗？

本文共计6547个文字，预计阅读时间需要27分钟。

排序算法是数据结构与算法中最基本算法之一。排序算法可分为内部排序和外部排序，内部排序是在内存中进行的排序，而外部排序是由于排序数据量大，一次性无法全部载入内存，因此需要将数据分批进行排序。

0.先言

　　排序算法是数据结构与算法中最基本的算法之一。

　　排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：、

0.1 名词解释

• n：数据规模
• k："桶"的个数
• In-place：占用常数内存，不占用额外内存
• Out-place：占用额外内存
• 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

1. 插入排序 1.1 直接插入排序

　　直接插入排序的特点:

• 时空效率: 时间复杂度为O(n^2),空间复杂度为O(1)。