自顶向下归并排序
package com.zwl.net; /** * 递归归并排序 * @author v.zhaowenlong * @date2013-11-22 上午10:39:37 */ public class MergeSort { private Comparable[] aux; public static void main(String[] args) { String[] a={"E","E","G","M","R","A","C","E","R","T","D","Y","H","N","J","F"}; MergeSort ms=new MergeSort(); ms.sort(a); for(int i=0;i<a.length;i++) System.out.print(a[i]); } public void sort(Comparable[] a){ aux=new Comparable[a.length]; sort(a,0,a.length-1); } /** * 递归 * @param a * @param li * @param hi */ public void sort(Comparable[] a,int li,int hi){ if (hi<=li) return; int mid=li+(hi-li)/2; sort(a, li, mid); sort(a,mid+1,hi); merge(a,li,mid,hi); } /** * 原地归并排序 * @param a * @param loj * @param mid * @param hi */ public void merge(Comparable[] a,int lo, int mid,int hi){ int i=lo; int j=mid+1; //数组复制 for(int k=lo;k<=hi;k++){ aux[k]=a[k]; } for(int k=lo;k<=hi;k++){ if(i>mid)a[k]=aux[j++]; else if(j>hi)a[k]=aux[i++]; else if(less(aux[i],aux[j]))a[k]=aux[i++]; else a[k]=aux[j++]; } } /** * 判断字母大小 * @param a * @param b * @return */ private static boolean less(Comparable a,Comparable b){ int result=a.compareTo(b); return result<0?true:false; } }
归并排序依赖数
相关推荐
本文实例讲述了C++实现自顶向下的归并排序算法。分享给大家供大家参考,具体如下: 一. 算法描述 自顶向下的归并排序:采用分治法进行自顶向下的程序设计方式,分治法的核心思想就是分解、求解、合并。 1. 先将长度...
根号n段归并排序算法的C++代码实现: 1.合并【根号n向下取整】段子数组,使用了自底向上的两两合并策略。 2.算法的总体时间复杂度为nlogn 3.带有详细注释
//创建菜单 cout<<"----------线性表查找算法... cout* 13--归并排序(自顶向下) *"; cout* 14--归并排序(自底向上) *"; cout*-------------------------------------*"; cout请选择操作(0-14):"; cin>>nMenu;
排序算法基础、改进综合: //冒泡排序 //定向冒泡[鸡尾酒]排序 //选择排序 //改进的选择排序 ...//自顶向下地归并排序 //自底向上地归并排序 //堆排序 //快速排序 //改进的快速排序:三向切分快速排序
常用排序算法总结,包括插入排序(InsertionSort),冒泡排序(BubbleSort),选择排序(SelectionSort),快速排序(QuickSort... * 二路归并排序(MergeSort),堆排序(HeapSort)。有每一种排序算法的复杂度分析以及实现思路~
实现时:建堆:置换堆顶元素和最后一个元素,堆大小减少,保持新的堆为最大堆; 保持最大堆: 从底向上依次保持最大堆,从第一个父节点到根部。 1.6 MergeSort:拆分数组,递归实现排序,二路归并。用哨兵来阻止...
本文实例为大家分享了C语言实现归并排序的具体代码,供大家参考,具体内容如下 归并排序的基本思想: 将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治法分为若干个有序子序列,然后每两个子序列合并...
2.2.2 自顶向下的归并排序 171 2.2.3 自底向上的归并排序 175 2.2.4 排序算法的复杂度 177 2.3 快速排序 182 2.3.1 基本算法 182 2.3.2 性能特点 185 2.3.3 算法改进 187 2.4 优先队列 195 ...
自顶向下归并排序-MergeSort | 自底向上归并排序-MergeBUSort | 快速排序-QuickSort | 堆排序-HeapSort :lion:搜索算法-搜索 与搜索相关的数据结构:二叉查找树,平衡查找树,散列表 线性查找-LinearSearch 二分...
根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导
2.2.2 自顶向下的归并排序 171 2.2.3 自底向上的归并排序 175 2.2.4 排序算法的复杂度 177 2.3 快速排序 182 2.3.1 基本算法 182 2.3.2 性能特点 185 2.3.3 算法改进 187 2.4 优先...
练习 参考文献第12章 高级数据结构及其实现 12.1 自顶向下伸展树 12.2 红黑树 12.2.1 自底向上的插入 12.2.2 自顶向下红黑树 12.2.3 自顶向下的删除 12.3 确定性跳跃表 12.4 aa树 12.5 treap树 ...
练习 参考文献第12章 高级数据结构及其实现 12.1 自顶向下伸展树 12.2 红黑树 12.2.1 自底向上的插入 12.2.2 自顶向下红黑树 12.2.3 自顶向下的删除 12.3 确定性跳跃表 12.4 aa树 12.5 treap树 ...
2.2.2 自顶向下的归并排序 171 2.2.3 自底向上的归并排序 175 2.2.4 排序算法的复杂度 177 2.3 快速排序 182 2.3.1 基本算法 182 2.3.2 性能特点 185 2.3.3 算法改进 187 2.4 优先队列 195 2.4.1 ...
摊还分析11.1 一个无关的智力问题11.2 二项队列11.3 斜堆11.4 斐波那契堆11.4.1 切除左式堆中的节点11.4.2 二项队列的懒惰合并11.4.3 斐波那契堆操作11.4.4 时间界的证明11.5 伸展树总结练习参考文献第12章 高级数据...
2.2.2 自顶向下的归并排序 2.2.3 自底向上的归并排序 2.2.4 排序算法的复杂度 2.3 快速排序 2.3.1 基本算法 2.3.2 性能特点 2.3.3 算法改进 2.4 优先队列 2.4.1 API 2.4.2 初级实现 2.4.3 堆的定义 2.4.4...
2.2.2 自顶向下的归并排序 171 2.2.3 自底向上的归并排序 175 2.2.4 排序算法的复杂度 177 2.3 快速排序 182 2.3.1 基本算法 182 2.3.2 性能特点 185 2.3.3 算法改进 187 2.4 优先队列 195 2.4.1 API 195 ...
4.6.2 向下取整和向上取整 思考题 本章注记 第5章 概率分析和随机算法 5.1 雇用问题 5.2 指示器随机变量 5.3 随机算法 ?5.4 概率分析和指示器随机变量的进一步使用 5.4.1 生日悖论 5.4.2 ...