1 选择排序简介

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序步骤

1. 在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

选择排序分析

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：不稳定

2 选择排序示例

3 冒泡排序简介

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

冒泡排序步骤

1. 比较相邻的元素：如果第一个比第二个大（升序排序），就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

示例

假设有一个数组 ，以下是冒泡排序的过程：

• 第一轮比较和交换后：
• 第二轮比较和交换后：
• 第三轮比较和交换后：
• 第四轮比较和交换后：
• 第五轮比较和交换后（因为 12 已经在 11 的右边，所以不需要交换）：

冒泡排序分析

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：稳定

优化

• 如果在某一轮遍历中没有发生任何交换，那么数组已经排序完成，可以提前结束算法。

• 冒泡排序可以从两端向中间进行，这种优化称为“鸡尾酒排序”或“双向冒泡排序”。

4 冒泡排序示例

5 快速排序简介

快速排序是什么

快速排序（Quicksort）是一种高效的排序算法，它采用了分治（Divide and Conquer）的思想。

1. 分治策略：快速排序通过选择一个基准元素（pivot），将待排序的序列分成两部分，使得左边部分的所有元素都小于或等于基准元素，右边部分的所有元素都大于或等于基准元素。
2. 递归处理：然后，对左右两部分分别递归地应用上述过程，直到整个序列有序。

快速排序步骤

1. 选择基准元素：通常选择序列的第一个元素作为基准元素，但也可以采用其他策略，如随机选择或三者取中等。
2. 分区操作：通过一趟排序将待排序列分成两部分，使得左边部分的所有元素都小于或等于基准元素，右边部分的所有元素都大于或等于基准元素。
3. 递归排序：对左右两部分分别递归地应用快速排序算法。

快速排序分析

时间复杂度：O(nlogn)

• 最坏情况：当每次分区操作都出现最不平衡的情况时，即每次分区后一边序列为空，另一边序列只比原序列少一个元素时，快速排序的时间复杂度为O(n^2)。
• 最好情况：当每次分区操作都能将序列平均分成两部分时，快速排序的时间复杂度为O(nlogn)。
• 平均情况：快速排序的平均时间复杂度也为O(nlogn)。

空间复杂度：O(n)

稳定性：不稳定

基准关键字的选取

基准关键字的选取对快速排序的性能有很大影响。常用的选取方式有：

1. 固定选取：直接选择序列的第一个或最后一个元素作为基准关键字。
2. 三者取中：选择序列首、尾和中间位置上的三个元素，取其中值作为基准关键字。
3. 随机选取：在序列的left和right之间随机选择一个元素作为基准关键字。

课外阅读：图解快速排序[ https://blog.csdn.net/justidle/article/details/104203963 ]

6 快速排序示例

7 各种排序对比

如何选择排序算法？

在选择上述的排序算法时，通常需要考虑以下几个指标：

1. 时间复杂度：算法执行所需的时间。这通常通过最好情况、平均情况和最坏情况的时间复杂度来衡量。
   • 插入排序、选择排序、冒泡排序的时间复杂度通常是 O(n^2)。
   • 希尔排序的时间复杂度依赖于间隔序列的选择，但通常比 O(n^2) 要好。
   • 归并排序和快速排序的时间复杂度在平均和最好情况下是 O(n log n)，但在最坏情况下，快速排序可能会退化为 O(n^2)（当输入数组已经有序或接近有序时）。
   • 归并排序的最坏情况时间复杂度总是 O(n log n)。
2. 空间复杂度：算法执行所需的额外空间。
   • 插入排序、选择排序、冒泡排序和希尔排序是原地排序算法（in-place sorting），即它们只需要 O(1) 的额外空间（除了输入数组本身）。
   • 归并排序不是原地排序算法，因为它需要额外的空间来合并两个已排序的子数组。其空间复杂度是 O(n)。
   • 快速排序在递归调用中也需要额外的栈空间，但在平均情况下，其空间复杂度是 O(log n)。但在最坏情况下，如果递归调用不平衡，它可能需要 O(n) 的空间。
3. 稳定性：如果相等的元素在排序后保持其原始顺序，则算法是稳定的。
   • 插入排序、冒泡排序、归并排序和希尔排序（当间隔为1时）是稳定的。
   • 选择排序、快速排序和希尔排序（当间隔大于1时）通常不是稳定的。
4. 数据的特性：
   • 如果输入数据已经部分有序或接近有序，快速排序可能会表现得较差，因为它在最坏情况下的时间复杂度是 O(n^2)。在这种情况下，插入排序或希尔排序可能是一个更好的选择。
   • 如果内存限制是一个问题，并且需要原地排序，那么插入排序、选择排序、冒泡排序或希尔排序可能是更好的选择。
   • 如果需要稳定的排序算法，那么应该选择插入排序、冒泡排序、归并排序或希尔排序（当间隔为1时）。
5. 实现细节：不同的排序算法可能在不同的编程语言或环境中具有不同的性能特性。因此，了解特定实现的性能特点也是很重要的。
6. 并行性和分布式处理：一些排序算法（如归并排序和快速排序）可以更容易地并行化或分布到多个处理器上，以进一步提高性能。

8 示例题

如何对一个省200万学生的高考成绩（假设成绩最多只有2位小数，0~900范围）进行排序，用尽可能高效的算法。