数据算法排序之归并排序
2023-09-11 14:14:53 时间
在你渐渐迷失在你的人生道路上的时候,千万不要因为走的太久,而忘记了我们为什么出发,做码农,也要清楚自己如何才能用有效的土地种植出 出色的产品,于是细节就需要把握一下。
如果你有兴趣可以关注一下公众号 biglead 我的大前端生涯,获取每日学习资料
排序是一个非常经典的问题,它以一定的顺序对一个数组(或一个列表)中的项进行重新排序(可以进行比较,例如整数,浮点数,字符串等)(增加,非递减,递减, 增加,词典等)。
有许多不同的排序算法,每个都有其自身的优点和局限性
引用于 https://visualgo.net/zh
归并排序,是创建在归并操作上的一种有效的排序算法。算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
- 算法复杂度:O(nlogn)
- 核心思想:分治
如我这里有一组数据,归并排序过程描述如下:
我们把上面的流程图合到一起就是如下:
分割的过程中其实可理解为就是以二分法将数组分割成最小单元,如下图所示分析了一下最后一步的合并过程
//归并排序
@Test
public void mergeSortFunction2(){
//待排序数组
int arr[]={6,5,3,1,8,7,2,4};
int len = arr.length;
//临时数组
int[] result = new int[len];
//排序
sort(arr,result);
System.out.println(Arrays.toString(result));
}
public static void sort(int []arr,int []temp ){
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
//左边归并排序,使得左子序列有序
sort(arr,left,mid,temp);
//右边归并排序,使得右子序列有序
sort(arr,mid+1,right,temp);
//将两个有序子数组合并操作
merge(arr,left,mid,right,temp);
}
}
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
相关文章
- 快排序算法
- Java实现 蓝桥杯VIP 算法提高 Quadratic Equation
- Java实现 蓝桥杯VIP 算法训练 求完数
- 动画图解:十大经典排序算法动画与解析,看我就够了!(配代码完全版)
- 数据结构与算法-2 最短路径 Dijkstra A*搜索 [MD]
- 【LeetCode算法-58/66】Length of Last Word/Plus One
- 【python cookbook】【数据结构与算法】14.对不原生支持比较操作的对象排序
- 程序员的算法趣题Q55: 平分蛋糕
- 程序员的算法趣题Q45: 排序交换次数的最少化
- 有10000000条数据,用以下什么排序算法用时最短
- Atitit 贝叶斯算法的原理以及垃圾邮件分类的原理
- Algorithm:C++语言实现之图论算法相关(图搜索广度优先BFS、深度优先DFS,最短路径SPF、带负权的最短路径Bellman-ford、拓扑排序)
- ML之PFI(eli5):基于mpg汽车油耗数据集利用RF随机森林算法和PFI置换特征重要性算法实现模型特征可解释性排序
- 改进的人工鱼群算法求解TSP问题的研究(Matlab代码实现)
- 杂文 - [1.1]使用库语言排序算法
- 八大排序算法
- 006-排序算法-希尔排序
- C#之十大排序算法
- mahout demo——本质上是基于Hadoop的分步式算法实现,比如多节点的数据合并,数据排序,网路通信的效率,节点宕机重算,数据分步式存储
- 数据结构与算法_11 _ 排序(上):为什么插入排序比冒泡排序更受欢迎
- 图解排序算法(四)之归并排序
- Python数模笔记-模拟退火算法(1)多变量函数优化
- 【数据结构与算法】——第八章:排序