【Java数据结构与算法】Day2-高级排序（希尔、归并、快速、计数）
✅作者简介：热爱Java后端开发的一名学习者，大家可以跟我一起讨论各种问题喔。
🍎个人主页：Hhzzy99
🍊个人信条：坚持就是胜利！
💞当前专栏：【Java数据结构与算法】
🥭本文内容：Java数据结构与算法中的比较高级的排序，希尔排序、归并排序、快速排序、计数排序
Java数据结构与算法
文章目录
上一篇文章我们介绍了Java中的简单排序传送门🚩，本文介绍Java中的高级排序，希尔排序、归并排序、快速排序、计数排序
| 排序方法 | 时间复杂度（平均） | 时间复杂度（最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 希尔排序 | O(n1.5) | O(n²) | O(n) | O(1) | 不稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 |
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 快速排序 | O(nlog2n) | O(n²) | O(nlog2n) | O(nlog2n) | 不稳定 |
| 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 |
高级排序
1.希尔排序
描述：
第一批突破O(n2)时间复杂度的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，他会优先比较距离较远的元素。希尔排序又叫 缩小增量排序
算法的核心思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接 插入排序，具体算法描述：
- 先根据数组长度/n，获取增量K（第一次n为2）
- 按增量序列个数K进行分组，一般可以分为K组；
- 根据已分好的组进行插入排序；（每组排序，根据对应的增量k来找到当前组的元素）
- 当每组都排序完成之后，回到第一步将n*2再次分组进行插入排序，直到最终k=1的时候，再执行一次 插入排序 完成最终的排序
实现：
分解1： 先将数组根据长度分为length/2组（增量），并且将第一组的元素进行插入排序
可以先实现获取第一组的元素:
第一轮：增量10/2=5组
public static void main(String[] args) { int[] arrs = new int[]{8,6,1,7,2,5,4,12,9,3}; //分组 int group = arrs.length / 2; System.out.println("输出第一组的元素"); for (int j = 0; (j + group) < arrs.length; j += group){ int insert = j + group; while ((insert - group) >= 0){ if(arrs[insert - group] > arrs[insert]){ //交换 int temp = arrs[insert - group]; arrs[insert - group] = arrs[insert]; arrs[insert] = temp; //插入的指针向前移动 insert = insert - group; }else { break; } } } for (int i = 0; i < arrs.length; i++){ System.out.print(arrs[i] + ","); } }
分解2： 将第一轮分好的所有的组都进行插入排序。
第二轮：增量5/2=2组
外面嵌套一个小于group的循环
for (int i = 0; i < group; i++) { for (int j = i; (j + group) < arrs.length; j += group){ int insert = j + group; while ((insert - group) >= 0){ if(arrs[insert - group] > arrs[insert]){ //交换 int temp = arrs[insert - group]; arrs[insert - group] = arrs[insert]; arrs[insert] = temp; //插入的指针向前移动 insert = insert - group; }else { break; } } } }分解3： 执行完第一轮之后，再继续分组执行分解1和分解2的操作，最终到无法分组，排序完成
public static void main(String[] args) { int[] arrs = new int[]{8,6,1,7,2,5,4,12,9,3}; //分组 int group = arrs.length; //等于1时说明无法再分组了 while (group != 1){ //分组 group = group / 2; for (int i = 0; i < group; i++) { for (int j = i; (j + group) < arrs.length; j += group){ int insert = j + group; while ((insert - group) >= 0){ if(arrs[insert - group] > arrs[insert]){//交换int temp = arrs[insert - group];arrs[insert - group] = arrs[insert];arrs[insert] = temp;//插入的指针向前移动insert = insert - group; }else {break; } } } } } for (int i = 0; i < arrs.length; i++){ System.out.print(arrs[i] + ","); } }
2.归并排序
描述：
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略即将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案 “修补” 在一起，即分而治之 。
归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了 名为TimSort的排序算法，就是归并排序的优化版本。每次合并操作的平均时月复杂度为O(n)，而完全二叉树的深度为|1og2n|。总的平均时间复杂度为O(nlogn)。而旦，归并排序的最好，最坏，平均时间复杂度均为o(nlogn)。
归井排序核心思想是先分再治,具体算法描述如下：
先将未排序数组/2进行分组,然后再将分好组的数组继续/2再次分组,直到无法分组,这个就是分的过程。
然后再将之后把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的，同时在合并的过程中完成数组的排列，最终直到全部小的数组合并起来，这个就是治的过程。
实现
分解1： 先实现分的思想，将数组分解进行实现
先获取数组的中轴，然后以中轴将数组分为两个部分
使用递归分别执行左右两部分分解
public static void main(String[] args) { int[] arrs = {8,6,3,7,2,5,4,1}; mergeSort(arrs,0,arrs.length-1); } //实现归并排序 public static void mergeSort(int[] arrs, int first, int last){ //实现递归推出的条件 if(first >= last){ return; } //求出当前数组的中间值 int mid = (first + last)/2; //将左边的数组继续分解 mergeSort(arrs,first,mid); //将右边的数组继续分解 mergeSort(arrs,mid + 1, last); //输出分组情况 //先输出左边的数组 for (int i = first; i <= mid; i++){ System.out.print(arrs[i] + " "); } System.out.print("--------"); //输出右边的数组 for (int i = mid + 1; i <= last; i++) { System.out.print(arrs[i] + " "); } System.out.println(" "); }分解2： 实现具体治的过程，将左右两个数组合并到一个临时数组中
分别设计两指针i和j，遍历左右两个数组，取出元素进行比较，将小的元素放入到临时数组中。
然后将左右剩下的元素放入到数组中
将排序好的临时数组中的元素返回到未排序的数组中
public static void main(String[] args) { int[] arrs = {8,6,3,7,2,5,4,1}; mergeSort(arrs,0,arrs.length-1); //输出排序结果 for (int i = 0; i < arrs.length; i++) { System.out.print(arrs[i] + " "); } } //实现归并排序 public static void mergeSort(int[] arrs, int first, int last) { //实现递归推出的条件 if (first >= last) { return; } //求出当前数组的中间值 int mid = (first + last)>>>1; //将左边的数组继续分解 mergeSort(arrs, first, mid); //将右边的数组继续分解 mergeSort(arrs, mid + 1, last); //治，实现插入并完成排序 int[] temp = new int[last + 1]; //定义两个指针 int i = first;//左边数组的遍历指针 int j = mid + 1;//右边数组的遍历指针 int t = 0;//临时数组的指针 //遍历左右两个数组，将较小的元素插入到临时数组中 while (i <= mid && j <= last) { if (arrs[i] <= arrs[j]) { //将左边的指针指向的元素插入到临时数组中 temp[t++] = arrs[i++]; } else { //将右边的指针指向的元素插入到临时数组中 temp[t++] = arrs[j++]; } } //再将左右剩余的元素插入到临时数组中 while (i<=mid){ temp[t++] = arrs[i++]; } while (j<=last){ temp[t++] = arrs[j++]; } //还需要将临时数组中的元素复制到原始数组中 //先将t重置 t = 0; //将t指向的值，复制到first指向的原始数组的位置 while (first <= last){ arrs[first++] = temp[t++]; } }3.快速排序
描述:
快速排序是对冒泡排序的一种改进，通过分而治之的思想减少排序中交换和遍历的次数，整个过程可以通过递归的方式完成。
具体描述如下：
首先通过比较算法，找到基准数，比较过程通过交换最终达到基准数左边的数字都比右边的小。
然后以基准数作为中轴，将数组分为两部分，分别执行步骤1的算法（可以通过递归实现），直到无法再次分割排序完毕
递归
一个含直接或间接调用本函数语句的函数被称之为递归函数，他必须满足以下两个条件：
1）在每一次调用自己时，必须是（在某种意义上）更接近于解；
2）必须有一个终止处理或计算的准则；
基本格式
void func(){//递归条件if(condition)func();else//退出递归}实现
分解1： 创建左右两个指针，将最后一个值作为基准值，通过不断交换将数组分为两部分，左边的比右边的要小。
- 先判断左指针和基准的值，如果小于等于就向后移动，直到遇到比基准值大的值
- 再判断右边指针和基准值，如果大于等于就向前移动，直到遇到比基准值小的值
- 然后交换左右指针的值
- 循环上述操作，直到左右指针重合，然后交换重合值和基准值
public static void main(String[] args) { int[] arrs = {3,9,8,7,2,5,4,1,6}; //执行快速排序 quickSort(arrs); for (int i = 0; i < arrs.length; i++) { System.out.print(arrs[i] + " "); } } //定义快速排序方法 public static void quickSort(int[] arrs){ //定义左指针 int left = 0; //定义右指针 int right = arrs.length - 1; //定义基准值 int pos = arrs.length - 1; while (left != right){ //判断左指针是否比基准值大，如果大就停止移动 while(arrs[left] <= arrs[pos]){ left++; } if(left == right) break; //判断右指针是否比基准值小，如果小就停止移动 while (arrs[right] >= arrs[pos]){ right--; } if(left < right){ //交换左右指针指向的值 int temp = arrs[left]; arrs[left] = arrs[right]; arrs[right] = temp; } } //当left和right重合之后，需要将重合的值和基准值进行交换 int temp = arrs[left]; arrs[left] = arrs[pos]; arrs[pos] = arrs[left]; }
分解2： 将以left和right的重复位置作为中轴，将数组分为两部分，左右分别执行分解1的操作，直到排序完成
public static void main(String[] args) { int[] arrs = {3,9,8,7,2,5,4,1,6}; //执行快速排序 quickSort(arrs, 0, arrs.length-1); for (int i = 0; i < arrs.length; i++) { System.out.print(arrs[i] + " "); } } //定义快速排序方法 public static void quickSort(int[] arrs, int first, int last){ //设置一下递归退出条件 if(first >= last) return; //定义左指针 int left = first; //定义右指针 int right = last; //定义基准值 int pos = last; //当left不等于right while (left != right){ //判断左指针是否比基准值大，如果大就停止移动 while(arrs[left] <= arrs[pos]){ left++; } //判断右指针是否比基准值小，如果小就停止移动 while (arrs[right] >= arrs[pos] && left < right){ right--; } if(left < right){ //交换左右指针指向的值 int temp = arrs[left]; arrs[left] = arrs[right]; arrs[right] = temp; } } //当left和right重合之后，需要将重合的值和基准值进行交换 int temp = arrs[left]; arrs[left] = arrs[pos]; arrs[pos] = temp; //将左边的数组执行快速排序 quickSort(arrs, first,left - 1); //将右边的数组执行快速排序 quickSort(arrs,right + 1,last); }4.计数排序
描述：
计数排序是一个非基于比较的排序算法，该算法于1954年由Harold H.Seward，提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为o(n+k)(其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n))，如归并排序，堆排序)
计数排序是一种适合于最大值和最小值的差值不是不是很大的排序，也就是说重复的数据会比较多的情况。
实现
分解1： 找到最大的数字，并且以数字的大小创建一个统计数组
//分解1：根据最大值创建统一数组 //遍历数组找到最大的值 int max = arrs[0]; for (int i = 0; i < arrs.length; i++) { if(arrs[i] > max){ max = arrs[i]; } } //根据最大值创建统一数组 int[] countArrs = new int[max];分解2： 遍历未排序的数组，统计每个数字出现的次数，根据下标添加到新的统计数组中
for (int i = 0; i < arrs.length; i++) { //以arrs[i]作为下标++ countArrs[arrs[i]]++; }分解3： 将排序的结果返回到原先的数组中
public static void main(String[] args) { int[] arrs = {0,2,1,3,0,2,0,1,1}; //分解1：根据最大值创建统一数组 //遍历数组找到最大的值 int max = arrs[0]; for (int i = 0; i < arrs.length; i++) { if(arrs[i] > max){ max = arrs[i]; } } //分解2： //根据最大值创建统一数组 int[] countArrs = new int[max + 1];//注意考虑0，要加一个 //遍历原先数组 for (int i = 0; i < arrs.length; i++) { //以arrs[i]作为下标++ countArrs[arrs[i]]++; } //分解3:将统计数组对应的下标的数字返回到排序数组中 int k = 0;//统计数组的下标 int index = 0;//排序数组的下标 while (k < countArrs.length){ //判断统计数组中的值是否大于0 while(countArrs[k] > 0){ //将对应的下标，返回到排序数组中 arrs[index++] = k; //统计的数字减少一个 countArrs[k]--; } k++; } //输出结果 for (int i = 0; i < arrs.length; i++) { System.out.print(arrs[i] + " "); } }统计数组优化
如果待排序的数字很大，那么在创建数组的时候会浪费没有空间，同时也会导致创建的数组，所以需要进行优化;
可以通过使用最大数字减去最小数字求出需要数组的大小。
public static void main(String[] args) { int[] arrs = {90,92,91,93,90,92,90,91,91}; //分解1：根据最大值创建统一数组 //遍历数组找到最大和最小的值 int max = arrs[0]; int min = arrs[0]; for (int i = 0; i < arrs.length; i++) { if(arrs[i] > max){ max = arrs[i]; } if(arrs[i] < min){ min = arrs[i]; } } //分解2： //根据最大值创建统一数组 int[] countArrs = new int[max - min + 1];//注意考虑0，要加一个 //遍历原先数组 for (int i = 0; i < arrs.length; i++) { //以arrs[i]作为下标++ //获取值时需要减去min countArrs[(arrs[i] - min)]++; } //分解3:将统计数组对应的下标的数字返回到排序数组中 int k = 0;//统计数组的下标 int index = 0;//排序数组的下标 while (k < countArrs.length){ //判断统计数组中的值是否大于0 while(countArrs[k] > 0){ //将对应的下标，返回到排序数组中 //需要还原成之前的值+min arrs[index++] = k + min; //统计的数字减少一个 countArrs[k]--; } k++; } //输出结果 for (int i = 0; i < arrs.length; i++) { System.out.print(arrs[i] + " "); } }结语
本文的内容主要是Java数据结构与算法中的高级排序，大家如果感兴趣可以点点赞，关注一下，你们的支持是我最强大的动力，非常感谢您的阅读(❁´◡`❁)
来源地址：https://blog.csdn.net/XUHUANGHOST/article/details/128604872
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
