java 算法之归并排序详解
一、思想
归并排序：将一个数组排序，可以先（递归地）将它分成两半部份分别排序，然后将结果归并起来；
二、概念
归并：将两个有序的数组归并成一个更大的有序数组；
三、特点
优点：能够保证将任意长度为n的数组排序所需要的时间和nlogn成正比；
缺点：需要额外的空间和n成正比；
四、实现方法
将两个不同的有序数组归并到第三个数组中；
先将前半部分排序，在将后半部分排序，然后在数组中移动元素而不需要使用额外的空间；
五、代码
我要评论
/**
* 归并排序
*
* @author pengcx
*
*/
public class merge extends sort {
/** 归并所需的辅助数组 */
private static comparable[] aux;
public static void main(string[] args) {
string[] a = { "d", "a", "w", "b", "q" };
merge.sort(a);
show(a);
}
public static void sort(comparable[] a) {
aux = new comparable[a.length];
sort(a, 0, a.length - 1);
}
/**
* 排序数组的a[lo]至a[hi]元素
*
* @param a
* 数组a
* @param lo
* 最小元素位置lo
* @param hi
* 最大元素位置hi
*/
private static void sort(comparable[] a, int lo, int hi) {
if (hi <= lo) {
return;
}
// 计算数组中间位置
int mid = lo + (hi - lo) / 2;
// 排序数组a左边的元素
sort(a, lo, mid);
// 排序数组a右边的元素
sort(a, mid + 1, hi);
// 合并数组a左边和右边的元素
merge(a, lo, mid, hi);
}
/**
* 将数组a的a[lo]至a[mid]的元素与a[mid]至a[hi]的元素合并
*
* @param a
* 合并的数组a
* @param lo
* 最小数组元素lo
* @param mid
* 中间元素位置mid
* @param hi
* 最大元素位置hi
*/
public static void merge(comparable[] a, int lo, int mid, int hi) {
int i = lo, 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[j], aux[i])) {
a[k] = aux[j++];
}
// 如果右半边的当前元素大于等于左半边的当前元素，取左半边元素
else {
a[k] = aux[i++];
}
}
}
}
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
如对本文有疑问， 点击进行留言回复！！
详解SpringBoot修改启动端口server.port的四种方式
网友评论