我要评论
文章目录
1.0 实现冒泡排序
冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的元素，并交换它们直到列表排序完成。冒泡排序的时间复杂度为 o(n^2) ，在最坏的情况下需要进行 n*(n-1)/2 次比较和交换操作。是一个稳定排序。
具体步骤如下：
-从列表的第一个元素开始，依次比较相邻的两个元素，如果它们的顺序不正确，则交换它们的位置。
- 继续比较相邻的元素，直到达到列表的末尾。
- 重复以上步骤，直到列表排序完成。
代码如下：
2.0 实现选择排序
选择排序（selection sort）是一种简单直观的排序算法。选择排序的时间复杂度为 o(n^2) ，因为在每一轮中需要进行n次比较，找到最小元素。（默认从小到大排序）
基本思想：每次从待排序的数据元素中选出最小（或最大）的一个元素，然后放到已排序序列的末尾。内层循环代表的是：当前这次循环中，需要找到剩余数组中最小的元素；外层循坏代表的是：需要进行多少次内层循环，才能将数组中的元素按从小到大排序完成。
代码如下：
2.1 选择排序的改良升级
在选择过程中，内层循环每一次都是寻找最小的元素，这次改进是在寻找最小元素的同时，又找最大的元素，定义两个 letf ,right 指针，一开始分别指向数组的左右两边。此时外层的循环条件：left < right 。一次内层循环中找到了最小、最大元素，接着就分别于 left、right 下标元素进行交换，交换完之后，left++ ，right-- 。
一开始 minindex、maxindex 都是从 left 开始，从左到右进行查找元素的。重点需要需要注意的是：假如最大的元素就是当前的 left 下标时，且 minindex 与 left 进行交换后，会导致 maxindex 找的元素下标就会发生变化，所以在下标 minindex 与 left 交换完之后，需要判断 maxinde == left 是否发生，如果发生了，那么 maxindex 需要重新赋值为 maxindex = minindex 。
代码如下：
3.0 实现堆排序
堆排序（heap sort）是一种高效的排序算法，它利用了堆这种数据结构来实现排序。堆是一种特殊的完全二叉树，分为最大堆和最小堆两种类型。在堆排序中，通常使用最大堆。堆排序的时间复杂度为 o(nlogn) ，并且是原地排序算法，不需要额外的存储空间。
堆排序的基本思想：首先将待排序的数据构建成一个最大堆，然后将堆顶元素（最大元素）与堆的最后一个元素交换，然后对剩余的元素重新调整为最大堆，重复这个过程直到整个序列有序。
两个动作：首先是将数组中的元素构建成一个大顶堆的形式，接着从堆的最后一个元素与堆顶元素进行交换，再对当前的堆顶元素进行下潜处理，循环该过程即可。
代码如下：
4.0 实现插入排序
插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对未排序的数据逐个进行插入，从而达到排序的目的。插入排序的时间复杂度为 o(n^2) ，在最坏情况下（逆序排列的数组），需要进行 n*(n-1)/2 次比较和交换操作。插入排序适用于小规模数据或部分有序的数据。是一个稳定排序。
具体来说，插入排序的算法步骤如下：
1.从第一个元素开始，该元素可以认为已经被排序。
2.取出下一个元素，在已经排序的元素序列中从后向前扫描。
3.如果该元素（已排序）大于新元素，将该元素移到下一位置。
4.重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
5.将新元素插入到该位置后。
6.重复步骤2~5。
代码如下：
5.0 实现希尔排序
希尔排序（shell sort）是一种改进的插入排序算法，也被称为“缩小增量排序”。它通过将数组分割成若干个子序列，对每个子序列进行插入排序，最终进行一次完整的插入排序得到有序序列。希尔排序的工作原理是通过逐步减小增量的方式，最终达到增量为1的插入排序。希尔排序的时间复杂度取决于增量序列的选择，通常为 o(n logn) 。
希尔排序的算法步骤如下：
1. 选择一个增量序列，通常为 n/2、n/4、n/8……直到增量为 1 。
2. 对每个增量进行插入排序，即将数组分割成若干个子序列，对每个子序列进行插入排序。
3. 逐步缩小增量，重复步骤 2 ，直到增量为 1 。
4. 最后进行一次增量为 1 的插入排序，完成排序过程。
代码如下：
6.0 实现归并排序
归并排序（merge sort）是一种经典的分治算法，它的基本思想是将待排序的数组递归地分成两个子数组，分别对两个子数组进行排序，然后将两个已排序的子数组合并成一个有序的数组。归并排序的过程可以描述为“分而治之”。
归并排序是一种稳定的排序算法，它的时间复杂度始终为 o(n log n) ，这使得它在处理大规模数据时具有较好的性能。然而，归并排序的空间复杂度较高，因为它需要额外的空间来存储临时数组。
6.1 递归实现归并排序
归并排序的算法步骤如下：
1. 分：将待排序的数组分成两个子数组，直到子数组的长度为1。
2. 治：对每个子数组进行递归排序，直到子数组有序。
3. 合：将两个有序的子数组合并成一个有序的数组。
代码如下：
6.2 使用非递归实现归并排序
非递归归并排序的关键是正确地计算子数组的大小并进行合并操作，直到整个数组都被合并为一个有序序列。
以下是非递归归并排序的主要步骤：
1. 从数组中的每个元素开始，将其视为一个大小为1的有序序列。
2. 通过迭代，将相邻的有序序列合并为更大的有序序列，直到整个数组变为一个有序序列。
3. 在每次迭代中，合并的子数组大小以指数级增加，直到整个数组都被合并为一个有序序列。
代码如下：
6.3 递归归并排序 + 插入排序
即集合了递归排序的优点与插入排序的优点实现更加高效排序。
代码如下：
7.0 快速排序
快速排序是一种常用的排序算法，它基于分治的思想。快速排序的基本思想是选择一个基准值，然后将数组分割成两部分，使得左边的元素都小于基准值，右边的元素都大于基准值。然后对左右两部分分别进行递归排序，直到整个数组有序。
以下是快速排序的主要步骤：
1.选择一个基准值（通常是数组中的第一个元素）。
2.将数组分割成两部分，使得左边的元素都小于基准值，右边的元素都大于基准值。这一步称为分区操作。
3. 递归地对左右两部分进行快速排序。
4. 当左右两部分都有序时，整个数组也就有序了。
7.1 单边循环快排
单边循环快排的时间复杂度为 o(n logn)，空间复杂度为 o(logn)。单边循环快排（也称为荷兰国旗问题解法）是快速排序算法的一种实现方式，它通过使用单个指针在数组中进行循环遍历，实现数组的分区和排序。
代码如下：
7.2 双边循环快排
双边循环快排是一种快速排序算法的实现方式，它通过不断地将数组分割成两部分并对每一部分进行递归排序来实现排序。与单边循环快排相比，双边循环快排在分割数组时使用两个指针分别从数组的两端向中间移动，以实现更高效的分割操作。
双边循环快排的时间复杂度为 o(nlogn)，空间复杂度为 o(logn)。它是一种高效的排序算法，在大多数情况下都能够快速地对数组进行排序。
具体实现过程如下：
1. 选择数组中的一个元素作为基准值（通常选择第一个元素）。
2. 设置两个指针，一个指向数组的起始位置，另一个指向数组的末尾位置。
3. 从起始位置开始，找到第一个大于基准值的元素，并将其位置记录下来。
4. 从末尾位置开始，找到第一个小于基准值的元素，并将其位置记录下来。
5. 交换这两个元素的位置，然后继续寻找下一个需要交换的元素，直到两个指针相遇。
6. 将基准值与指针相遇的位置的元素交换位置，这样基准值左边的元素都小于基准值，右边的元素都大于基准值。
7. 对基准值左右两个子数组分别进行递归排序。
代码如下：
7.3 快速排序的改良升级
考虑快排时，遇到的重复元素过多而进行改良。
代码如下：
发表评论