🛸基本概念
⭐排序
排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。
平时的上下文中,如果提到排序,通常指的是排升序(非降序)。
通常意义上的排序,都是指的原地排序(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);//将剩余元素继续变成一个大根堆 } }