简述几种常用的排序算法
原文中文，约4500字，阅读约需11分钟。
📝
内容提要
归并排序和快速排序是两种复杂的排序算法，都使用分治思想和递归实现。归并排序的重点是递推公式和合并函数。
🎯
关键要点
-
归并排序和快速排序是复杂的排序算法，使用分治思想和递归实现。
-
理解归并排序的关键在于递推公式和合并函数。
-
冒泡排序通过相邻元素比较和交换来排序，最坏情况下需要 n 次冒泡操作。
-
冒泡排序的空间复杂度为 O(1)，时间复杂度最坏和平均为 O(n²)，最好为 O(n)。
-
插入排序将数组分为已排序和未排序区间，通过插入未排序元素来保持已排序区间有序。
-
插入排序的空间复杂度为 O(1)，时间复杂度最坏和平均为 O(n²)，最好为 O(n)。
-
选择排序每次从未排序区间选择最小元素放入已排序区间，时间复杂度为 O(n²)。
-
归并排序通过分治思想将数组分为两部分排序后合并，时间复杂度为 O(n log n)，空间复杂度为 O(n)。
-
快速排序选择一个分区点，将数组分为小于和大于该点的部分，时间复杂度为 O(n log n)。
-
归并排序和快速排序的理解重点在于递推公式和相应的合并或分区函数。
🏷️
