📢博客主页：🏀敲代码的布莱恩特🏀
📢欢迎点赞 👍 收藏 ⭐留言 📝 欢迎讨论！👏
📢本文由 【敲代码的布莱恩特】 原创，首发于 CSDN🙉🙉🙉
📢由于博主是在学小白一枚，难免会有错误，有任何问题欢迎评论区留言指出，感激不尽！✨
📖精品专栏（不定时更新）【JavaSE】 【Java数据结构】【LeetCode】
【Java数据结构】想进大厂必须牢记于心的——常见八大排序算法
🛸基本概念
⭐排序
- 排序，就是使一串记录，按照其中的某个或某些关键字的大小，
递增或递减的排列起来的操作。 - 平时的上下文中，如果提到排序，通常指的是排升序（非降序）。
- 通常意义上的排序，都是指的原地排序(in place sort)。
⭐稳定性
两个相等的数据，如果经过排序后，排序算法能 **
保证其相对位置不发生变化
** ，则我们称该算法是具备 **
稳定性
** 的排序算法。
🛸七大基于比较的排序
⭐插入排序
🎄1. 直接插入排序
思路：
- 插入排序基本思想是将一个记录插入到已经排好序的有序表中，从而变成一个新的、记录数增1的有序表。
- 在其实现过程使用双层循环，外层循环对
除了第一个元素之外的所有元素，内层循环对 **当前元素前面有序表进行待插入位置查找**，并进行移动
图解：
代码实现：
/*** 时间复杂度：* 最好：O(N) -> 数据是有序的** 最坏：O(N^2) -> 无序的数据** 空间复杂度：O(1)* 稳定性：稳定排序* @param array*///插入排序publicstaticvoid insertSort (int[]array){for(int i =1; i<array.length; i++){//外循环//从1开始表示：假设array[0] 已经放好位置了//后面的数字就是插入到它左边还是右边的问题。int tmp = array[i];//设置一个缓存tmpint 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的问题：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。**
当gap == 1时**，数组已经接近有序的了，这时 **相当于直接用插入排序**，这样就会很快，因为直接插入排序是越有序越快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
图解：
代码实现：
/*** @param array 排序的数组* @param gap 每组的间隔 -》 组数*/publicstaticvoidshell(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*/publicstaticvoidshellSort(int[] array){//处理gapint 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*/publicstaticvoidselectSort(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位置的数交换，如此反复执行，便能得到有序数组
图解：
代码实现：
//堆的向下调整publicstaticvoidsiftDown(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;}}}//建堆publicstaticvoidcreateHeap(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*/publicstaticvoidheapSort(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);//将剩余元素继续变成一个大根堆}}
⭐交换排序
🎄5. 冒泡排序
思路：
- 比较 **
相邻的两个元素**。如果第一个比第二个大则交换他们的位置(升序排列，降序则反过来)。 - 从列表的开始一直到结尾，**
依次对每一对相邻元素都进行比较。这样，值最大的元素就通过交换“冒泡”到了列表的结尾**，完成第一轮“冒泡”。 - 重复上一步，继续从列表开头依次对相邻元素进行比较。已经“冒泡”出来的元素不用比较(一直比较到结尾也可以，已经“冒泡”到后面的元素即使比较也不需要交换，不比较可以减少步骤)。
- 继续从列表开始进行比较，**
每轮比较会有一个元素“冒泡”成功。每轮需要比较的元素个数会递减，一直到只剩一个元素没有“冒泡”时**(没有任何一对元素需要比较)，则列表排序完成。
- 算法优化
如若在一轮排序中没有发生位置的交换，那么说明数据已经有序，不用继续进行后边的排序了
图解：
代码实现：
/*** 时间复杂度：* 最好最坏都是O(n^2) 但是：如果优化了 ，有序的时候就是O(n)* 空间复杂度：O(1)* 稳定性：稳定的排序* 冒泡 直接插入* @param array*/publicstaticvoidbubbleSort(int[] array){for(int i =0;i < array.length-1; i++){//外循环只用length-1趟boolean flg =false;//记录当前这一趟是否有换位子for(int j =0; j <array.length-1-i ; j++){//内循环array.length-1-i趟if(array[j]> array[j+1]){int tmp = array[j];array[j]= array[j+1];array[j+1]= tmp;flg =true;}}if(flg==false){//如果当前趟没换位置，说明已经有序，不需要再排序了break;}}}
🎄6. 快速排序
思路：
快速排序使用 **
分治策略
** 来把一个序列（list）分为两个子序列（sub-lists）。步骤为：
- 从数列中挑出一个元素，称为"
基准"（pivot）。 ①选择边上（左或者右）默认用这种方式②随机选择 ③几数取中（例如三数取中）：array[left], array[mid], array[right] 大小是中间的为基准值 - 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的 **
中间位置**。这个称为分区（partition）操作。 - 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。**
递归到最底部时，数列的大小是零或一，也就是已经排序好了**。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
图解：
代码实现：
/*** 时间复杂度：* 最好：O(n*logn) 均匀的分割下* 最坏：o(n^2) 数据有序的时候* 空间复杂度：* 最好：logn* 最坏：O(n)* 稳定性：不稳定的排序** k*n*logn* 2* 1.2* @param array*/publicstaticvoidquickSort(int[] array){sort(array,0, array.length -1);System.out.println(Arrays.toString(array));}privatestaticvoidsort(int[] array,int low,int high){int i = low;int j = high;if(array.length <=1){return;}if(i >= j){return;}int pivot = array[i];while(i < j){while(i < j && array[j]>= pivot){j--;}array[i++]= array[j];while(i < j && array[i]<= pivot){i++;}array[j--]= array[i];}array[i]= pivot;//i下标值就是pivot基准值，由此可以递归左右两边的序列sort(a, low, i -1);sort(a, i +1, high);}
非递归实现快速排序（
重点掌握递归实现
）
/*** 非递归实现快速排序* @param array*/publicstaticvoidquickSort_FDG(int[] array){Stack<Integer> stack =newStack<>();int start =0;int end = array.length-1;int pivot =partition(array,start,end);//左边有2个元素及以上if(pivot > start+1){stack.push(0);stack.push(pivot-1);}if(pivot < end-1){stack.push(pivot+1);stack.push(end);}while(!stack.empty()){end = stack.pop();start = stack.pop();pivot =partition(array,start,end);//左边有2个元素及以上if(pivot > start+1){stack.push(0);stack.push(pivot-1);}if(pivot < end-1){stack.push(pivot+1);stack.push(end);}}}
⭐🎄7. 归并排序·
思路：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
图解：
- 分而治之
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。“分” 阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。 - 合并相邻有序子序列 再来看看 “治” 阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。
代码实现：
publicstaticvoidmerge(int[] array,int low,int mid,int high){int s1 = low;int e1 = mid;int s2 = mid+1;int e2 = high;int[] tmp =newint[high-low+1];int k =0;//代表tmp数组的下标while(s1 <= e1 && s2 <= e2){if(array[s1]<= array[s2]){tmp[k++]= array[s1++];//k++;//s1++;}else{tmp[k++]= array[s2++];}}//有2种情况while(s1 <= e1){//说明第2个归并段没有了数据 把第1个归并段剩下的数据 全部拷贝过来tmp[k++]= array[s1++];}while(s2 <= e2){//说明第1个归并段没有了数据 把第2个归并段剩下的数据 全部拷贝过来tmp[k++]= array[s2++];}//tmp数组当中 存储的就是当前归并好的数据,现在还需要拷贝到原数组中//这样的代码是错误的/*for (int i = 0; i < array.length; i++) {array[i] = tmp[i];}*/for(int i =0; i < tmp.length; i++){array[i+low]= tmp[i];//加上对应的low，用来处理第二个归并段，如果是第一个归并段，low=0}}publicstaticvoidmergeSortInternal(int[] array,int low,int high){if(low >= high){return;}int mid =(low+high)/2;mergeSortInternal(array,low,mid);//分解前半段mergeSortInternal(array,mid+1,high);//分解后半段//合并的过程merge(array,low,mid,high);}/*** 时间复杂度： O(N*log n)* 空间复杂度：O(N)* 稳定性：稳定的* @param array*/publicstaticvoidmergeSort(int[] array){mergeSortInternal(array,0,array.length-1);}
非递归实现归并排序（了解即可，重点掌握递归实现）：
/*** 非递归实现 归并排序* @param array* @param gap*/publicstaticvoidmerge2(int[] array,int gap){int[] tmp =newint[array.length];int k =0;int s1 =0;int e1 = s1+gap-1;int s2 = e1+1;//int e2 = s2+gap-1 >= array.length ? array.length-1 : s2+gap-1;int e2 = s2+gap-1< array.length ? s2+gap-1: array.length-1;//保证有两个归并段while(s2 < array.length){while(s1 <= e1 && s2 <= e2){if(array[s1]<= array[s2]){tmp[k++]= array[s1++];}else{tmp[k++]= array[s2++];}}while(s1 <= e1){tmp[k++]= array[s1++];}while(s2 <= e2){tmp[k++]= array[s2++];}//一组完了 确定新的区间的开始和结束s1 = e2+1;e1 = s1+gap-1;s2 = e1+1;e2 = s2+gap-1< array.length ? s2+gap-1: array.length-1;}//e2 > array.lengthwhile(s1 <= array.length-1){tmp[k++]= array[s1++];}for(int i =0; i < tmp.length; i++){array[i]= tmp[i];}}publicstaticvoidmergeSort_FDG(int[] array){for(int i =1; i < array.length; i*=2){merge2(array,i);}}
🛸非基于比较的排序
🎄8. 基排序
思路：
- 基数排序的思想就是先排好 **
个位**，然后 **排好个位的基础上排十位**，以此类推，直到遍历最高位 次，排序结束（仔细理解最后一句话） - 基数排序不是比较排序，而是通过分配和收集的过程来实现排序
初始化10个桶(固定的)，桶下标为0-9- 通过得到待排序数字的个十百等位的数字，**
把这个数字对应的item放到对应的桶中** - 基数排序有两种排序方式：LSD和MSD，最小位优先(从右边开始)和最大位优先(从左边开始)
图解：
代码实现：
publicstaticvoidradixSort(int[] array){ArrayList<ArrayList<Integer>> queue =newArrayList<>();for(int i =0; i <10; i++){queue.add(newArrayList<>());// 创建一个基数从0---9 每个数字上都是一个list}// 找到最大值，并判断最大值是几位数int max = array[0];for(int i =1; i < array.length; i++){if(max < array[i]){max = array[i];}}int time =0;while(max >0){max /=10;time++;}for(int i =0; i < time; i++){// 循环每一个位数（个位、十位、百位）for(int j =0; j < array.length; j++){// 循环数组，取每一个值int x = array[j]%(int)Math.pow(10, i +1)/(int)Math.pow(10, i);ArrayList<Integer> queue3 = queue.get(x);queue3.add(array[j]);queue.set(x, queue3);}int count =0;for(int k =0; k <10; k++){while(queue.get(k).size()>0){ArrayList<Integer> queue4 = queue.get(k);array[count]= queue4.get(0);queue4.remove(0);count++;}}}}
🗽总结
**
一个稳定的排序，可以变成不稳定的排序
但是一个不稳定的排序，不可能变成稳定的排序
**
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙
❤原创不易，如有错误，欢迎评论区留言指出，感激不尽❤
❤ 如果觉得内容不错，给个三连不过分吧~ ❤
❤ 看到会回访~ ❤
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙
本文转载自: https://blog.csdn.net/DerrickWestbrook/article/details/122190540
版权归原作者 敲代码的布莱恩特 所有， 如有侵权，请联系我们删除。
版权归原作者 敲代码的布莱恩特 所有， 如有侵权，请联系我们删除。