排序算法可以分为内部排序和外部排序，在内存中进行的排序称为内部排序，当要排序的数据量很大时无法全部拷贝到内存，这时需要使用外存进行排序，这种排序称为外部排序。

内部排序包括比较排序和非比较排序，比较排序包括插入排序、选择排序、交换排序和归并排序，非比较排序包括计数排序、基数排序和桶排序。

其中插入排序又包括直接插入排序和希尔排序，选择排序包括直接选择排序和堆排序，交换排序包括冒泡排序和快速排序。

直接插入排序属于插入排序，是一种稳定的排序，平均/最差时间复杂度均为 O(n²)，当元素基本有序时最好时间复杂度为 O(n)，空间复杂度为 O(1)。

基本原理：每一趟将一个待排序记录按其关键字的大小插入到已排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。

适用场景：待排序记录较少或基本有序的情况。

优化：直接插入没有利用到要插入的序列已有序的特点，插入第 i 个元素时可以通过二分查找找到插入位置 insertIndex，再把 i~insertIndex 之间的所有元素后移一位，把第 i 个元素放在插入位置上。

希尔排序属于插入排序，又称缩小增量排序，是对直接插入排序的一种改进，并且是一种不稳定的排序，平均时间复杂度为O(n^1.3^)，最差时间复杂度为 O(n²)，最好时间复杂度为 O(n)，空间复杂度为 O(1)。

基本原理：把记录按下标的一定增量分组，对每组进行直接插入排序，每次排序后减小增量，当增量减至 1 时排序完毕。

适用场景：中等规模的数据量，对规模很大的数据量不是最佳选择。

直接选择排序属于选择排序，是一种不稳定的排序，任何情况下时间复杂度都是 O(n²)，空间复杂度为 O(1)。

基本原理：每次在未排序序列中找到最小元素，和未排序序列的第一个元素交换位置，再在剩余未排序序列中重复该操作直到所有元素排序完毕。

适用场景：数据量较小的情况，比直接插入排序稍快。

堆排序属于选择排序，是对直接选择排序的改进，并且是一种不稳定的排序，任何情况时间复杂度都为 O(nlogn)，空间复杂度为 O(1)。

基本原理：将待排序记录看作完全二叉树，可以建立大根堆或小根堆，大根堆中每个节点的值都不小于它的子节点值，小根堆中每个节点的值都不大于它的子节点值。

以大根堆为例，在建堆时首先将最后一个节点作为当前节点，如果当前节点存在父节点且值大于父节点，就将当前节点和父节点交换。在移除时首先暂存根节点的值，然后用最后一个节点代替根节点并作为当前节点，如果当前节点存在子节点且值小于子节点，就将其与值较大的子节点进行交换，调整完堆后返回暂存的值。

适用场景：数据量较大的情况。

冒泡排序属于交换排序，是一种稳定的排序，平均/最坏时间复杂度均为 O(n²)，当元素基本有序时最好时间复杂度为O(n)，空间复杂度为 O(1)。

基本原理：是比较相邻的元素，如果第一个比第二个大就进行交换，对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，每一轮排序后末尾元素都是有序的，针对 n 个元素重复以上步骤 n -1 次排序完毕。

优化：当序列已经有序时仍会进行不必要的比较，可以设置一个标志记录是否有元素交换，如果没有直接结束比较。

快速排序属于交换排序，是对冒泡排序的一种改进，并且是一种不稳定的排序，平均/最好时间复杂度均为 O(nlogn)，当元素基本有序时最坏时间复杂度为O(n²)，空间复杂度为 O(logn)。

基本原理：首先选择一个基准元素，通过一趟排序将要排序的数据分割成独立的两部分，一部分全部小于等于基准元素，一部分全部大于等于基准元素，再按此方法递归对这两部分数据进行快速排序。

快速排序的一次划分从两头交替搜索，直到 low 和 high 指针重合，因此一趟时间复杂度是 O(n)，而整个算法的时间复杂度与划分趟数有关。最好情况是每次划分选择的中间数恰好将当前序列等分，经过 log(n) 趟划分便可得到长度为 1 的子表，这样算法的时间复杂度为O(nlogn)。最坏情况是每次所选中间数是当前序列中的最大或最小元素，这使每次划分所得子表其中一个为空表，另一个子表的长度为原表的长度 - 1。这样长度为 n 的数据表的需要经过 n 趟划分，整个排序算法的时间复杂度为O(n²)。

适用场景：数据量较大且元素基本无序的情况。