💕"每一天都是值得被热爱的"💕
作者：Mylvzi
文章主要内容：常见排序算法实现
1.排序的概念
所谓排序，就是按照特定顺序重新排列序列的操作
排序的稳定性：
当一个序列中存在相同的元素时 排序过后 他们出现的顺序和原来序列的顺序一致就说明此排序稳定；否则，就不稳定
内部排序：
- 内部排序是指对数据集合完全加载到内存中进行排序的过程。
- 这种排序方法适用于数据量较小，可以在计算机内存中容纳整个数据集的情况。
- 常见的内部排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。
- 内部排序的优点是速度较快，因为所有数据都在内存中，不需要频繁的读取和写入操作。
外部排序：
- 外部排序是指对大规模数据集合进行排序的方法，数据量太大，无法一次性加载到内存中。
- 这种排序方法涉及将数据分割成适当大小的块，然后在内存中对这些块进行排序，最后将排序后的块写回磁盘或其他存储介质，并合并这些块以得到最终的排序结果。
- 外部排序常用于需要处理大量数据的场景，比如数据库系统中对大型表进行排序或外部存储设备上的数据排序。
- 常见的外部排序算法包括归并排序、多路归并排序等，这些算法允许对大规模数据进行高效排序，因为它们能够有效地利用磁盘I/O操作。
常见的排序算法
1.插入排序
插入排序是一种非常简单的排序 比如在玩扑克牌时 在发牌阶段 我们每抽取一张牌 都要从后往前去比较大小 把抽取的牌插入到合适的位置
所以，插入排序就是将待排序的元素（抽取的牌）插入到一个已经有序的序列之中
代码实现
/** * 插入排序 在一个已经存在的序列中 插入到合适位置 * 时间复杂度： * 最好情况：O(N) * 最坏情况:O(N^2) * 空间复杂度： * O(1) * 稳定性：是一个稳定的排序 * 所以对于一个有序的序列来说 插入排序就是最快的 */ public static void insertSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int tmp = arr[i]; int j = i-1; for (; j >= 0; j--) { // >tmp j向后挪动 if(arr[j] > tmp) { arr[j+1] = arr[j]; }else { // 要插入的元素已经是最大的了 不需要再去比较了 //arr[j+1] = tmp; break; } } // 跳出循环有两种情况 1.tmp是最小的需要插入到第一个元素 此时j=-1 结束条件是j不>=0了 2.else语句中的break； arr[j+1] = tmp; } }
2.希尔排序（缩小增量排序）
是根据插入排序的优点来进行优化的插入排序
我们知道，插入排序对于有序化高的序列来说速度是更快的，也就是说一个序列有序化越高，使用插入排序的时间复杂度就越低，速度就越快
所以，对于一大堆的数据来说，我们可以先进行“预排”，使其有序化程度越来越高，从而实现效率更高
设置gap 利用插入排序的思想 分组进行优化 组数不断降低 直到最后为1 最后一个进行排序时 序列的有序化程度已经很高 速度很快
希尔排序看似繁琐 实则提高了效率 虽然要进行多次插入排序 但时间优化了很多 主要原因在于以下几个方面：
1.分组会使得待排序的数据量减小 每次排序的数据量少 时间快
2.当gap = 1时，也就是要对整个序列进行排序 虽然数据量很大 但是有序化程度高 时间快
希尔排序的分析过
代码实现
/** * 希尔排序 优化的插入排序 * 先进行预排序 跳跃式进行分组 分的组数逐渐减少 直到组数为1 * 分组优化 * 时间复杂度：O(N^1.3) * 空间复杂度：O(1) * 稳定性：不稳定 */ public static void shellSort(int[] arr) { int gap = arr.length; while (gap > 1) { gap /= 2; shell(arr,gap); } } private static void shell(int[] arr,int gap) { for (int i = gap; i < arr.length; i++) { int tmp = arr[i]; int j = i-gap; for (; j >= 0; j-= gap) { // >tmp j向后挪动 if(arr[j] > tmp) { arr[j+gap] = arr[j]; }else { // 要插入的元素已经是最大的了 不需要再去比较了 //arr[j+1] = tmp; break; } } arr[j+gap] = tmp; } }
3.选择排序
选择排序也是一个比较简单的排序 其核心思想在于每次都要选择一个最小的/最大的元素位于最左边
选择排序无论你的顺序如何 都要遍历整个数组去寻找最小值/最大值 所以对于初始顺序不敏感
代码实现
public static void selectSort(int[] arr) { for (int i = 0; i < arr.length; i++) { int minIndex = i; for (int j = i+1; j < arr.length; j++) { if(arr[j] < arr[minIndex]) { minIndex = j; } } swap(arr,i,minIndex); } } private static void swap(int[] arr,int i,int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
4.堆排
堆排 就是利用堆的特性进行排序的一种方式
思路：
1.看条件创建堆 升序--》大根堆 降序--》小根堆
2.交换首元素和末元素 向下调整
常见排序算法实现（二）+https://developer.aliyun.com/article/1413533
