1. 冒泡排序（Bubble Sort）
算法步骤：
- 从数组的第一个元素开始，比较相邻的两个元素。如果前一个元素大于后一个元素，则交换它们的位置。
- 对每一对相邻元素重复这个操作，从数组的开始到结尾。这一步骤会将最大的元素“冒泡”到数组的最后位置。
- 忽略已经排序好的部分（最后一个元素），重复以上步骤，直到整个数组有序。
性能分析：
- 时间复杂度：
- 最佳情况：当数组已经有序时，只需进行一次遍历即可完成排序，时间复杂度为 $O(n)$。
- 平均情况和最坏情况：在平均情况下和最坏情况下，冒泡排序的时间复杂度为 $O(n^2)$，因为需要对每一对元素进行比较并可能进行交换。
-
空间复杂度：$O(1)$，冒泡排序是就地排序算法，只需要常量级的额外空间。
- 稳定性：冒泡排序是稳定的排序算法，因为在元素相等时不会交换它们的位置。
2. 选择排序（Selection Sort）
算法步骤：
- 从未排序部分中选择最小（或最大）的元素，将其与未排序部分的第一个元素交换。
- 将已排序部分向后移动一个位置，继续在未排序部分中选择最小（或最大）的元素，进行交换。
- 重复上述步骤，直到整个数组有序。
性能分析：
- 时间复杂度：
- 最佳情况、平均情况和最坏情况：选择排序的时间复杂度始终为 $O(n^2)$，因为每次选择最小元素都需要遍历未排序部分。
-
空间复杂度：$O(1)$，选择排序也是就地排序算法，不需要额外的存储空间。
- 稳定性：选择排序是不稳定的排序算法，因为当两个相等的元素存在时，选择排序可能会改变它们的相对顺序。
3. 插入排序（Insertion Sort）
算法步骤：
- 从第二个元素开始，将该元素与之前的元素进行比较。
- 如果当前元素小于之前的元素，将之前的元素后移一位，继续比较，直到找到合适的位置插入当前元素。
- 重复步骤2，直到数组有序。
性能分析：
- 时间复杂度：
- 最佳情况：当数组已经有序时，只需要进行 $O(n)$ 次比较，时间复杂度为 $O(n)$。
- 平均情况和最坏情况：插入排序的时间复杂度为 $O(n^2)$，因为每次插入操作可能需要在已排序部分中进行多次比较和移动。
-
空间复杂度：$O(1)$，插入排序是就地排序算法。
- 稳定性：插入排序是稳定的，因为相同元素的相对顺序不会被改变。
4. 快速排序（Quick Sort）
算法步骤：
- 从数组中选择一个“基准”（pivot），通常选择第一个元素、最后一个元素或随机选择。
- 重新排序数组，将所有比基准小的元素放到基准的左边，所有比基准大的元素放到基准的右边。此时，基准元素在其正确的位置上。
- 递归地对基准左边的子数组和右边的子数组进行快速排序。
- 重复上述步骤，直到整个数组有序。
性能分析：
- 时间复杂度：
- 最佳情况和平均情况：当基准总能将数组平衡分割时，时间复杂度为 $O(n \log n)$。
- 最坏情况：当基准每次都选择了数组中的最大或最小值，时间复杂度会退化为 $O(n^2)$。
-
空间复杂度：快速排序的空间复杂度为 $O(\log n)$，这是由于递归调用堆栈的深度。
- 稳定性：快速排序是不稳定的，因为在基准划分过程中，元素的相对顺序可能会改变。
5. 归并排序（Merge Sort）
算法步骤：
- 将数组递归地分成两半，直到每个子数组只包含一个元素。
- 依次将子数组两两合并，并在合并过程中对元素进行排序。
- 重复上述步骤，直到所有子数组合并为一个有序数组。
性能分析：
-
时间复杂度：归并排序的时间复杂度始终为 $O(n \log n)$，因为它总是将数组分成两半并合并。
-
空间复杂度：归并排序的空间复杂度为 $O(n)$，因为它需要额外的数组来存储合并结果。
-
稳定性：归并排序是稳定的排序算法，因为在合并过程中不会改变相同元素的相对顺序。
6. 堆排序（Heap Sort）
算法步骤：
- 将数组构造成一个最大堆（或最小堆），这是一个完全二叉树，满足堆的性质。
- 将堆顶元素（最大或最小）与最后一个元素交换，将堆的大小减一。
- 调整堆以维持堆的性质，继续交换堆顶元素和最后一个元素，直到堆大小为1。
性能分析：
-
时间复杂度：堆排序的时间复杂度为 $O(n \log n)$，因为构建堆需要 $O(n)$，而调整堆的过程需要 $O(\log n)$。
-
空间复杂度：堆排序的空间复杂度为 $O(1)$，因为它在原地进行排序。
-
稳定性：堆排序是不稳定的排序算法，因为在调整堆的过程中，可能会改变相同元素的相对顺序。
对于小规模数据集，插入排序可能是个不错的选择，而对于大规模数据集，快速排序和归并排序通常表现更佳。