【算法】一个小白的算法笔记: 归并排序算法的编码和优化 (,,? ? ?,,)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【算法】一个小白的算法笔记: 归并排序算法的编码和优化 (,,? ? ?,,),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含9518字,纯文字阅读大概需要14分钟。
内容图文
参考资料
归并排序的概念
归并排序的两种实现方式:递归和循环
单趟归并算法
单趟排序的实现分析
- 设置两个游标 i 和 j 用于“元素比较” (在aux中进行):变量,i 和 j,分别代表左游标和右游标,开始时分别指向aux[low]和aux[mid]
- 设置游标k用于确定在a中放置元素的位置(在a中进行),k在开始时候指向a[low]
- 总体上来说i, j, k的趋势都是向右移动的
- 左半边用尽(取右半边的元素)
- 右半边用尽(取左半边的元素)
- 右半边元素小于左半边当前元素(取右半边的元素)
- 右半边元素大于等于左半边当前元素(取左半边的元素)
单趟排序算法的代码
/* * * @description: 完成一趟合并 * @param a 输入数组 * @param low,mid,high a[low...high] 是待排序序列, 其中a[low...mid]和 a[mid+1...high]已有序 */ private static void merge (int a [],int low,int mid,int high) { for(int k=low;k<=high;k++){ aux[k] = a[k]; // 将待排序序列a[low...high]拷贝到辅助数组的相同位置 } int i = low; // 游标i,开始时指向待排序序列中左半边的头元素 int j = mid+1; // 游标j,开始时指向待排序序列中右半边的头元素 for(int k=low;k<=high;k++){ if(i>mid){ a[k] = aux[j++]; // 左半边用尽 }elseif(j>high){ a[k] = aux[i++]; // 右半边用尽 }elseif(aux[j]<aux[i]){ a[k] = aux[j++]; // 右半边当前元素小于左半边当前元素, 取右半边元素 }else { a[k] = aux[i++]; // 右半边当前元素大于等于左半边当前元素,取左半边元素 } } } }
单趟排序的过程图解
基于递归的归并排序(自顶向下)
递归归并的思想
sort(a,low,mid); sort(a,mid+1,high); merge(a,low,mid,high);
/* * * @Author: HuWan Peng * @Date Created in 9:44 2017/11/29 */ public class MergeSort { private static int aux []; /* * * @description: 1. 初始化辅助数组aux,使其长度和原数组相同 * 2. 包装sort,向外只暴露一个数组参数 */ public static void sort(int a []){ aux = newint[a.length]; sort(a,0,a.length-1); } /** * @description: 基于递归的归并排序算法 */ private static void sort (int a [], int low,int high) { if(low>=high) { return; } // 终止递归的条件 int mid = low + (high - low)/2; // 取得序列中间的元素 sort(a,low,mid); // 对左半边递归 sort(a,mid+1,high); // 对右半边递归 merge(a,low,mid,high); // 单趟合并 } /** * @description: 单趟合并算法 * @param a 输入数组 * @param low,mid,high a[low...high] 是待排序序列,其中a[low...mid]和 a[mid+1...high]已有序 */ private static void merge (int a [],int low,int mid,int high) { int i = low; // 游标i,开始时指向待排序序列中左半边的头元素 int j = mid+1; // 游标j,开始时指向待排序序列中右半边的头元素 for(int k=low;k<=high;k++){ aux[k] = a[k]; // 将待排序序列a[low...high]拷贝到辅助数组的相同位置 } for(int k=low;k<=high;k++){ if(i>mid){ a[k] = aux[j++]; // 左半边用尽 }elseif(j>high){ a[k] = aux[i++]; // 右半边用尽 }elseif(aux[j]<aux[i]){ a[k] = aux[j++]; // 右半边当前元素小于左半边当前元素, 取右半边元素 }else { a[k] = aux[i++]; // 右半边当前元素大于等于左半边当前元素,取左半边元素 } } } }
public class Test { public static void main (String args[]){ int [] a = {1,6,3,2,9,7,8,1,5,0}; MergeSort.sort(a); for(int i=0;i<a.length;i++){ System.out.println(a[i]); } } }
0 1 1 2 3 5 6 7 9
递归栈深度和调用顺序
sort(a,low,mid); // A sort(a,mid+1,high); // B merge(a,low,mid,high);// C
递归归并的轨迹图像
(下面展示的归并进行了一些优化,对小数组使用插入排序)
基于递归归并排序的优化方法
优化点一:对小规模子数组使用插入排序
if(low>=high) { return; }
if(low + M>=high) { // 数组长度小于10的时候 InsertSort.sort(int a [], int low,int high) // 切换到插入排序 return; }
private static void sort (int a [], int low,int high) { if(low + 10>=high) { // 数组长度小于10的时候 InsertSort.sort(int a [], int low,int high)// 切换到插入排序 return; } // 终止递归的条件 int mid = low + (high - low)/2; // 取得序列中间的元素 sort(a,low,mid); // 对左半边递归 sort(a,mid+1,high); // 对右半边递归 merge(a,low,mid,high); // 单趟合并 }
优化点二: 测试待排序序列中左右半边是否已有序
private static void sort (int a [], int low,int high) { if(low>=high) { return; } // 终止递归的条件 int mid = low + (high - low)/2; // 取得序列中间的元素 sort(a,low,mid); // 对左半边递归 sort(a,mid+1,high); // 对右半边递归 if(a[mid]<=a[mid+1])return; // 避免不必要的归并 merge(a,low,mid,high); // 单趟合并 }
优化点三:去除原数组序列到辅助数组的拷贝
for(int k=low;k<=high;k++){ aux[k] = a[k]; // 将待排序序列a[low...high]拷贝到辅助数组的相同位置 }
public static void sort(int a []){ aux= a.clone(); // 拷贝一个和a所有元素相同的辅助数组 sort(a,aux,0,a.length-1); } /** * @description: 基于递归的归并排序算法 */ private static void sort (int a[], int aux[], int low,int high) { if(low>=high) { return; } // 终止递归的条件 int mid = low + (high - low)/2; // 取得序列中间的元素 sort(aux, a,low,mid); // 对左半边递归 sort(aux, a,mid+1,high); // 对右半边递归 merge(a, aux, low,mid,high); // 单趟合并 }
- 在排序前拷贝一个和原数组元素完全一样的辅助数组(不再是创建一个空数组了!)
- 在递归调用的每个层次交换输入数组和输出数组的角色
/* * * @Author: HuWan Peng * @Date Created in 9:44 2017/11/29 */ public class MergeSort { private static int aux []; /* * * @description: 1. 初始化辅助数组aux,使其和原数组元素完全相同 * 2. 包装sort,向外只暴露一个数组参数 */ public static void sort(int a []){ aux = a.clone(); // 拷贝一个和a所有元素相同的辅助数组 sort(a,aux,0,a.length-1); } /** * @description: 基于递归的归并排序算法 */ private static void sort (int a[], int aux[], int low,int high) { if(low>=high) { return; } // 终止递归的条件 int mid = low + (high - low)/2; // 取得序列中间的元素 sort(aux, a,low,mid); // 对左半边递归 sort(aux, a,mid+1,high); // 对右半边递归 merge(a, aux, low,mid,high); // 单趟合并 } /** * @description: 单趟合并算法 * @param a 输入数组 * @param low,mid,high a[low...high] 是待排序序列,其中a[low...mid]和 a[mid+1...high]已有序 */ private static void merge (int a [],int aux [],int low,int mid,int high) { int i = low; // 游标i,开始时指向待排序序列中左半边的头元素 int j = mid+1; // 游标j,开始时指向待排序序列中右半边的头元素 // 这里的for循环拷贝已经去除掉了 for(int k=low;k<=high;k++){ if(i>mid){ a[k] = aux[j++]; // 左半边用尽 }elseif(j>high){ a[k] = aux[i++]; // 右半边用尽 }elseif(aux[j]<aux[i]){ a[k] = aux[j++]; // 右半边当前元素小于左半边当前元素, 取右半边元素 }else { a[k] = aux[i++]; // 右半边当前元素大于等于左半边当前元素,取左半边元素 } } } }
基于循环的归并排序(自底向上)
循环归并的基本思想
/* * * @Author: HuWan Peng * @Date Created in 23:42 2017/11/30 */ public class MergeSort2 { private static int aux []; public static void sort(int a []){ int N = a.length; aux = newint [N]; for (int size =1; size<N;size = size+size){ for(int low =0;low<N-size;low+=size+size) { merge(a,low,low+size-1,Math.min(low+size+size-1,N-1)); } } } private static void merge (int a [],int low,int mid,int high) { int i = low; // 游标i,开始时指向待排序序列中左半边的头元素 int j = mid+1; // 游标j,开始时指向待排序序列中右半边的头元素 for(int k=low;k<=high;k++){ aux[k] = a[k]; } for(int k=low;k<=high;k++){ if(i>mid){ a[k] = aux[j++]; // 左半边用尽 }elseif(j>high){ a[k] = aux[i++]; // 右半边用尽 }elseif(aux[j]<aux[i]){ a[k] = aux[j++]; // 右半边当前元素小于左半边当前元素, 取右半边元素 }else { a[k] = aux[i++]; // 右半边当前元素大于等于左半边当前元素,取左半边元素 } } } }
循环归并的轨迹图像
原文:http://www.cnblogs.com/penghuwan/p/7940440.html
内容总结
以上是互联网集市为您收集整理的【算法】一个小白的算法笔记: 归并排序算法的编码和优化 (,,? ? ?,,)全部内容,希望文章能够帮你解决【算法】一个小白的算法笔记: 归并排序算法的编码和优化 (,,? ? ?,,)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。