参考资料：
- 《Python实现5大排序算法》
- 《六大排序算法：插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序》 --代码似乎是C语言
————————
本文介绍5种常见的排序算法和基于Python实现：
冒泡排序（Bubble Sort）：通过不断交换相邻元素，将较大的元素逐渐“冒泡”到数组的尾部，较小的元素逐渐沉到数组的头部。
选择排序（Selection Sort）：每次从未排序的部分中选择最小（或最大）的元素，然后放到已排序部分的末尾（或开头）。
插入排序（Insertion Sort）：将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的适当位置，使其保持有序。
快速排序（Quick Sort）：通过递归地选择一个基准元素，并将数组划分为小于基准和大于基准的两部分，然后对两部分继续进行快速排序。
归并排序（Merge Sort）：将数组拆分成两个子数组，对每个子数组进行排序，然后再将两个有序子数组合并成一个有序数组。
不同的排序算法在时间复杂度、空间复杂度以及稳定性等方面有所不同，选择适合具体情况的排序算法可以提高排序效率。
第二次循环，要判断n-2次=5.两两交换，要将次最大值64沉到尾部(90之前)。结果为：
【11，,12，,22，,25，,34，,64，,90】
第三次循环，要判断n-3次=4. 值得注意的是，在这次循环中，没有一次交换行为。
第四次循环，要判断n-4次=3.值得注意的是，在这次循环中，没有一次交换行为。
第五次循环，要判断n-5次=2.值得注意的是，在这次循环中，没有一次交换行为。
第六次循环，要判断n-6次=1.值得注意的是，在这次循环中，没有一次交换行为。
因此，设置一个“标志位”，用于优化。若某次循环中没有交换元素，说明数组已经有序，可以提前结束排序。即在第三次循环中，判断没有交换，则可以提前结束优化了。
1.1 代码
测试
在冒泡排序中，外层循环控制需要比较的次数，内层循环实际进行相邻元素的比较和交换。通过标志位swapped的引入，可以优化冒泡排序，当某次循环没有发生交换时，说明数组已经有序，可以提前结束排序。这样在数组近乎有序的情况下，冒泡排序的性能会有所提升。
改进
“swapped”是优化的循环次数，提前截止循环。当序列的长度足够大的时候，在循环的某次的内部是否可以提前截止交换呢？
【22，,12，,11，25, 34，,64 ，90】
1.2 优化后的代码
1.3 复杂度
时间复杂度：最坏情况：O(N^2)
最好情况：O(N)
空间复杂度：O(1)
2.1 代码
测试
在选择排序中，外层循环控制需要排序的次数，内层循环在未排序部分中找到最小元素的索引。然后将找到的最小元素与未排序部分的第一个元素交换位置。这样每一轮循环会将未排序部分的最小元素放到已排序部分的末尾，从而实现排序。选择排序的时间复杂度是O(n^2)，它是一个不稳定的排序算法。
改进
换个角度看，外层循环指示了已排序部分的末尾，要求所有的元素都必须经历排序，因此，外层循环是不可能像冒泡排序一样提前截止的。在每次循环的内部选择最小元素的时候，我们也必须在所有未排序的元素中选择，也不可以提前截止。因此，我们只能将优化的注意力放在“交换”上。
例如:【11，,12，,22，,25，,34，,90，,64】
第一次循环，位置arr[0], 选择最小的arr[0]–>交换
第二次循环，位置arr[1], 选择最小的arr[1]–>交换
第二次循环，位置arr[2], 选择最小的arr[2]–>交换
。。。
可以看到，出现了很多不必要的交换。因此，添加一个判断因素，从而停止交换。—提醒的是，计算机做判断的消耗的运行时间远远小于数组的位置交换所消耗的时间。
2.2 优化的代码
通过增加一个条件判断，只有当最小元素的索引不等于当前的第一个元素的索引时，才进行交换操作。这样就可以减少不必要的交换，进而优化选择排序的性能。这个优化对于已经近乎有序的数组尤为有效，因为这些情况下交换次数较少。尽管选择排序的时间复杂度仍然是O(n^2)，但这样的优化可以提高它的效率。
2.3 复杂度
时间复杂度：最坏情况：O(N^2)
最好情况：O(N^2)
空间复杂度：O(1)
3.1 代码
在插入排序中，外层循环控制需要插入的次数，从第2个元素开始（索引为1），依次向已排序部分插入未排序部分的元素。内层循环用于将已排序部分中比当前元素key大的元素后移，为key找到合适的插入位置。最后，将key插入到合适的位置，完成一次插入操作。
改进
在外层循环控制的插入次数，所有的元素都要被插入，因此无法提前截止。内层循环控制的是插入位置，一一倒序比较插入的位置是否合适。为了更快的找到插入位置，可以使用二分法判断插入位置。
3.2 优化的代码
3.3 复杂度
时间复杂度
最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)
快速排序（Quick Sort）是一种高效的排序算法，它使用分治法来对数组进行排序。快速排序的基本思想是选择一个基准元素（pivot），然后将数组中小于等于基准的元素放在左边，大于基准的元素放在右边，然后分别对左右两部分递归地进行快速排序，直到整个数组有序为止。
案例
以【34，,25，,11，,22，,12，,64，,90】为例。
4.1 代码
改进
在优化快速排序的代码中，主要关注减少递归调用的次数和减少额外空间的使用。以下是针对这两方面的优化方法：
- 优化递归调用次数：对于小规模的子数组，可以切换到其他排序算法，例如插入排序。这是因为在小规模数据下，插入排序的常数项较小，比快速排序的递归开销更小。
- 减少额外空间的使用：原始的快速排序需要额外的数组空间用于存放左右子数组，但我们可以通过就地分区的方式来减少空间使用。
或者说是用挖坑法 减少额外空间的使用。注意，在减少空间使用的的快速排序算法有很多，下面这个动态图比较形象，所以放在这里的。这与我们 下面使用的的代码不一致。
4.2 优化的代码
对于小规模的子数组，切换到插入排序
测试
在优化后的代码中，我们引入了insertion_sort函数用于对小规模子数组进行插入排序。当子数组大小不超过10个元素时，切换到插入排序。同时，在quick_sort函数中采用就地分区的方法，减少了额外的空间使用。
这些优化方法可以提高快速排序在小规模数据和近乎有序数组的性能。但需要注意的是，优化的效果也依赖于具体的数据情况