视频字幕
排序算法是计算机科学中最基础也是最重要的算法之一。它的作用是将一组数据按照特定的顺序重新排列，通常是从小到大或从大到小。排序算法可以按照不同的标准进行分类：比较排序和非比较排序，稳定排序和不稳定排序，内部排序和外部排序。我们评价排序算法的性能主要看三个指标：时间复杂度表示算法执行所需的时间，空间复杂度表示算法需要的额外内存，稳定性表示相等元素在排序后是否保持原有的相对位置。
冒泡排序是最简单直观的排序算法，它的基本思想是通过重复比较相邻的元素，如果顺序错误就交换它们的位置。算法的名字来源于较小的元素会像气泡一样逐渐浮到数组的顶端。冒泡排序的具体步骤是：首先比较相邻的两个元素，如果前面的元素大于后面的元素就交换它们，然后继续比较下一对相邻元素，重复这个过程直到整个数组有序。冒泡排序的时间复杂度是O(n²)，空间复杂度是O(1)，它是一个稳定的排序算法。
选择排序和插入排序是两种经典的基础排序算法。选择排序的工作原理是每次从未排序的部分中找到最小的元素，然后将它放到已排序部分的末尾。具体来说，首先在整个数组中找到最小元素并将其与第一个元素交换，然后在剩余元素中找到最小元素与第二个元素交换，如此重复直到排序完成。插入排序的思想是将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，将其插入到已排序部分的正确位置。这两种算法的时间复杂度都是O(n²)，但插入排序在数据基本有序时性能更好。
快速排序是一种基于分治思想的高效排序算法，由英国计算机科学家托尼·霍尔在1960年提出。快速排序的基本思想是选择一个基准元素，通常选择数组的最后一个元素作为基准，然后将数组分为两个子数组：一个包含所有小于等于基准的元素，另一个包含所有大于基准的元素。这个过程称为分区操作。分区完成后，基准元素就处于其最终的正确位置上。然后递归地对两个子数组进行同样的操作，直到子数组的长度为1或0。快速排序的平均时间复杂度是O(n log n)，但在最坏情况下会退化到O(n²)，空间复杂度是O(log n)。
归并排序是另一种经典的分治排序算法，由约翰·冯·诺伊曼在1945年发明。与快速排序不同，归并排序采用自顶向下的分治策略。算法首先将数组不断分割成两半，直到每个子数组只有一个元素，然后自底向上地将这些有序的子数组合并成更大的有序数组，最终得到完全排序的数组。归并排序的关键在于合并操作：将两个已排序的数组合并成一个有序数组。归并排序最重要的特点是它是稳定的排序算法，相等元素的相对位置在排序后保持不变。它的时间复杂度始终是O(n log n)，不会像快速排序那样在最坏情况下退化，但空间复杂度是O(n)，需要额外的存储空间。