视频字幕
排序算法是计算机科学中最基础也是最重要的算法之一。它的作用是将一组数据按照特定的顺序重新排列,通常是从小到大或从大到小。排序算法可以按照不同的标准进行分类:比较排序和非比较排序,稳定排序和不稳定排序,内部排序和外部排序。我们评价排序算法的性能主要看三个指标:时间复杂度表示算法执行所需的时间,空间复杂度表示算法需要的额外内存,稳定性表示相等元素在排序后是否保持原有的相对位置。
冒泡排序是最简单直观的排序算法,它的基本思想是通过重复比较相邻的元素,如果顺序错误就交换它们的位置。算法的名字来源于较小的元素会像气泡一样逐渐浮到数组的顶端。冒泡排序的具体步骤是:首先比较相邻的两个元素,如果前面的元素大于后面的元素就交换它们,然后继续比较下一对相邻元素,重复这个过程直到整个数组有序。冒泡排序的时间复杂度是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),需要额外的存储空间。