01归并排序算法的JAVA实现
package Utils.Sort;
/**归并排序,要求待排序的数组必须实现Comparable接口 */
public class MergeSort implements SortStrategy
{ private Comparable[] bridge;
/** 利用归并排序算法对数组obj进行排序*/
public void sort(Comparable[] obj)
{ if (obj == null)
{ throw new NullPointerException("The param can not be null!");
}
bridge = new Comparable[obj.length]; //初始化中间数组
mergeSort(obj, 0, obj.length - 1); //归并排序
bridge = null;
}
/**
*将下标从left到right的数组进行归并排序
*@param obj 要排序的数组的句柄
*@param left 要排序的数组的第一个元素下标
*@param right 要排序的数组的最后一个元素的下标
*/
private void mergeSort(Comparable[] obj, int left, int right)
{ if (left < right)
{ int center = (left + right)/2;
mergeSort(obj, left, center);
mergeSort(obj, center + 1, right);
merge(obj, left, center, right);
}
}
/**
*将两个对象数组进行归并,并使归并后为升序。归并前两个数组分别有序
*@param obj 对象数组的句柄
*@param left 左数组的第一个元素的下标
*@param center 左数组的最后一个元素的下标
*@param right 右数组的最后一个元素的下标
*/
private void merge(Comparable[] obj, int left, int center, int right)
{ int mid = center + 1;
int third = left;
int tmp = left;
while (left <= center && mid <= right)
{ //从两个数组中取出小的放入中间数组
if (obj[left].compareTo(obj[mid]) <= 0)
{ bridge[third++] = obj[left++];
} else
bridge[third++] = obj[mid++];
}
//剩余部分依次置入中间数组
while (mid <= right)
{ bridge[third++] = obj[mid++];
}
while (left <= center)
{ bridge[third++] = obj[left++];
}
//将中间数组的内容拷贝回原数组
copy(obj, tmp, right);
}
/**
*将中间数组bridge中的内容拷贝到原数组中
*@param obj 原数组的句柄
*@param left 要拷贝的第一个元素的下标
*@param right 要拷贝的最后一个元素的下标
*/
private void copy(Comparable[] obj, int left, int right)
{ while (left <= right)
{ obj[left] = bridge[left];
left++;
} }
}
分享到:
相关推荐
资源名称:Java常用算法手册内容简介:现代的设计任务大多通过计算机编程来完成,而算法起到了至关重要的作用。可以毫不夸张地说,算法是一切程序设计的灵魂和基础。选择合理的算法,可以起到事半功倍的效果。 赵...
Java常用排序算法 Java常用排序算法 Java常用排序算法 Java常用排序算法
java 常用排序算法 java 常用排序算法 java 常用排序算法
Java常用8大排序算法,包含每种算法详细介绍,及代码如何实现。
java实现的常用的几种基本排序算法,插入、交换、选择、归并
Java常用排序算法源码 稳定:冒泡排序、插入排序、归并排序和基数排序;不稳定:选择排序、快速排序、希尔排序、堆排序
Java经典算法 ,各种排序算法 老掉牙 河內塔 費式數列 巴斯卡三角形 三色棋 老鼠走迷官(一) 老鼠走迷官(二) 騎士走棋盤 八個皇后 八枚銀幣 生命遊戲 字串核對 雙色、三色河內塔 背包問題(Knapsack...
详解Java常用排序算法-基数排序
详解Java常用排序算法-桶排序
详解Java常用排序算法-计数排序
详解Java常用排序算法-堆排序
详解Java常用排序算法-希尔排序
详解Java常用排序算法-插入排序
详解Java常用排序算法-冒泡排序
详解Java常用排序算法-快速排序
详解Java常用排序算法-归并排序
详解Java常用排序算法-选择排序