🛸基本概念
⭐排序
排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
平时的上下文中，如果提到排序，通常指的是排升序（非降序）。
通常意义上的排序，都是指的原地排序(in place sort)。
⭐稳定性
两个相等的数据，如果经过排序后，排序算法能 保证其相对位置不发生变化 ，则我们称该算法是具备 稳定性 的排序算法
🛸七大基于比较的排序
⭐插入排序
🎄1. 直接插入排序
思路：
插入排序基本思想是将一个记录插入到已经排好序的有序表中，从而变成一个新的、记录数增1的有序表。
在其实现过程使用双层循环，外层循环对 除了第一个元素之外的所有元素，内层循环对 当前元素前面有序表进行待插入位置查找，并进行移动
图解：
代码实现：
/** * 时间复杂度： * 最好：O(N) -> 数据是有序的 * * 最坏：O(N^2) -> 无序的数据 * * 空间复杂度：O(1) * 稳定性：稳定排序 * @param array */ //插入排序 public static void insertSort (int[]array){ for (int i = 1; i<array.length; i++){//外循环 //从1开始表示：假设array[0] 已经放好位置了 //后面的数字就是插入到它左边还是右边的问题。 int tmp = array[i];//设置一个缓存tmp int j = i-1; for (; j >=0 ; j--){//内循环 if (array[j]>tmp){//如果array[j]大于缓存值，说明要换位置 array[j+1] = array[j]; }else{//否则直接退出当前这一次的循环 break; } } //最后记得要把缓存值插入到表中 array[j+1] = tmp;//j此时有可能已经是-1了，所以要变成0下标就得+1 } }
🎄2. 希尔排序（直接插入排序的优化）
思路：
希尔排序法又称缩小增量法。
希尔排序法的基本思想是：
先选定一个整数（gap），把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取gap / 2，重复上述分组和排序的工作。当gap到达1时，所有记录在同一组内排好序。
注意gap的问题：
1.希尔排序是对直接插入排序的优化。
2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这时 相当于直接用插入排序，这样就会很快，因为 直接插入排序是越有序越快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
图解：
代码实现：
/** * @param array 排序的数组 * @param gap 每组的间隔 -》 组数 */ public static void shell(int[] array,int gap) { //如果将gap全部换成1，会发现其实就是直接插入排序 //所以当gap到1的时候，这就表示这是最后一次排序 //这最后一次排序其实就是一个直接插入排序 for (int i = gap; i < array.length; i++) { int tmp = array[i]; int j = i-gap; for (; j >= 0; j -= gap) { if(array[j] > tmp) { array[j+gap] = array[j]; }else { break; } } array[j+gap] = tmp; } } /** * 时间复杂度：不好算 n^1.3 - n^1.5 之间 * 空间复杂度：O(1) * 稳定性：不稳定的排序 * 技巧：如果在比较的过程当中 没有发生跳跃式的交换 那么就是稳定的 * @param array */ public static void shellSort(int[] array) { //处理gap int gap = array.length; while (gap > 1) { gap /= 2;//保证最后一个序列间隔是 1 除几都行 shell(array,gap); } }
⭐选择排序
🎄3. 选择排序
思路：
将一组数据分为有序区（排过序的数据）和无序区（未排序数据），每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完 。
选择排序的步骤：
1>首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2>再从剩余未排序元素中继续寻找最小（大）元素，然后放到未排序序列的起始位置。
3>重复第二步，直到所有元素均排序完毕。
图解：
代码实现：
/** * 时间复杂度： * 最好：O(N^2) * 最坏：O(N^2) * 空间复杂度：O(1) * 稳定性：不稳定的 * @param array */ public static void selectSort(int[] array) { for (int i = 0; i < array.length; i++) {//下标i前边的为有序区间 for (int j = i+1; j < array.length; j++) { if(array[j] < array[i]) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } } }
🎄4.堆排序（如果不了解堆的话可以看看我上一篇讲 堆 的博客）
思路：
准备知识：
堆的结构可以分为大根堆和小根堆，是一个 完全二叉树，而堆排序是根据堆的这种数据结构设计的一种排序，下面先来看看什么是大根堆和小根堆
性质：
每个结点的值都大于其左孩子和右孩子结点的值，称之为大根堆；
每个结点的值都小于其左孩子和右孩子结点的值，称之为小根堆。
如下图
我们对上面的图中每个数都进行了标记，上面的结构映射成数组就变成了下面这个样子
基本步骤：
首先将待排序的数组构造成一个大根堆（升序用大根堆，降序就用小根堆），此时，整个数组的最大值就是堆结构的顶端
将顶端的数与末尾的数交换，此时，末尾的数为最大值，将末尾这个最大值提取出去，剩余待排序数组个数为n-1
将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组
图解：
代码实现：
//堆的向下调整 public static void siftDown(int[] array,int root,int len) {//len表示末尾元素下标 int parent = root; int child = 2*parent+1;//先找到左孩子节点 while (child <= len) {//当child>length的时候说明当前子树已经调整好了 //先根据左孩子节点判断右孩子节点是否存在，且是否大于左孩子节点 if(child+1 <= len && array[child] < array[child+1]) {//如果存在,且值大于左孩子节点 child++; } //child的下标就是左右孩子的最大值下标 if(array[child] > array[parent]) {//如果孩子节点最大值，大于父节点，则要交换位置，因为要建大根堆 int tmp = array[child]; array[child] = array[parent]; array[parent] = tmp; //继续向下看是否符合大根堆的条件 parent = child;//更新parent下标 child = 2*parent+1;//更新child下标 }else {//否则不用换位置 break; } } } //建堆 public static void createHeap(int[] array) { //从小到大排序 -》 大根堆 for (int i = (array.length-1 - 1) / 2; i >= 0 ; i--) { siftDown(array,i,array.length-1); } } /** * 时间复杂度：O(N*logN) 都是这个时间复杂度 * 复杂度：O(1) * 稳定性：不稳定的排序 * @param array */ public static void heapSort(int[] array) { createHeap(array);//O(n) int end = array.length-1;//end表示当前末尾元素的下标 while (end > 0) {//O(N*logN) int tmp = array[end];//因为要交换末尾与堆顶元素，所以先缓存末尾元素 //已经建好堆了，这时堆顶（0下标元素）就是当前的最大值 array[end] = array[0];//将他提取出来，放到数组的末尾，固定住 array[0] = tmp;//将末尾元素换到堆顶 end--;//固定了一个当前堆中的最大值之后，下一次参与排序的元素就得减少一个 siftDown(array,0,end);//将剩余元素继续变成一个大根堆 } }
