Java MergeSort
2024-09-01 14:54:39
Java MergeSort
/**
* <html>
* <body>
* <P> Copyright 1994-2018 JasonInternational </p>
* <p> All rights reserved.</p>
* <p> Created on 2018年4月10日 </p>
* <p> Created by Jason</p>
* </body>
* </html>
*/
package cn.ucaner.algorithm.sorts; /**
* Merge sort is an O(n log n) comparison-based sorting algorithm. Most
* implementations produce a stable sort, which means that the implementation
* preserves the input order of equal elements in the sorted output.
* <p>
* Family: Merging.<br>
* Space: In-place.<br>
* Stable: True.<br>
* <p>
* Average case = O(n*log n)<br>
* Worst case = O(n*log n)<br>
* Best case = O(n*log n)<br>
* <p>
* @see <a href="https://en.wikipedia.org/wiki/Merge_sort">Merge Sort (Wikipedia)</a>
* <br>
* @author Justin Wetherell <phishman3579@gmail.com>
*/
@SuppressWarnings("unchecked")
public class MergeSort<T extends Comparable<T>> { public static enum SPACE_TYPE { IN_PLACE, NOT_IN_PLACE } private MergeSort() { } public static <T extends Comparable<T>> T[] sort(SPACE_TYPE type, T[] unsorted) {
sort(type, 0, unsorted.length, unsorted);
return unsorted;
} private static <T extends Comparable<T>> void sort(SPACE_TYPE type, int start, int length, T[] unsorted) {
if (length > 2) {
int aLength = (int) Math.floor(length / 2);
int bLength = length - aLength;
sort(type, start, aLength, unsorted);
sort(type, start + aLength, bLength, unsorted);
if (type == SPACE_TYPE.IN_PLACE)
mergeInPlace(start, aLength, start + aLength, bLength, unsorted);
else
mergeWithExtraStorage(start, aLength, start + aLength, bLength, unsorted);
} else if (length == 2) {
T e = unsorted[start + 1];
if (e.compareTo(unsorted[start]) < 0) {
unsorted[start + 1] = unsorted[start];
unsorted[start] = e;
}
}
} private static <T extends Comparable<T>> void mergeInPlace(int aStart, int aLength, int bStart, int bLength, T[] unsorted) {
int i = aStart;
int j = bStart;
int aSize = aStart + aLength;
int bSize = bStart + bLength;
while (i < aSize && j < bSize) {
T a = unsorted[i];
T b = unsorted[j];
if (b.compareTo(a) < 0) {
// Shift everything to the right one spot
System.arraycopy(unsorted, i, unsorted, i+1, j-i);
unsorted[i] = b;
i++;
j++;
aSize++;
} else {
i++;
}
}
} private static <T extends Comparable<T>> void mergeWithExtraStorage(int aStart, int aLength, int bStart, int bLength, T[] unsorted) {
int count = 0;
T[] output = (T[]) new Comparable[aLength + bLength];
int i = aStart;
int j = bStart;
int aSize = aStart + aLength;
int bSize = bStart + bLength;
while (i < aSize || j < bSize) {
T a = null;
if (i < aSize) {
a = unsorted[i];
}
T b = null;
if (j < bSize) {
b = unsorted[j];
}
if (a != null && b == null) {
output[count++] = a;
i++;
} else if (b != null && a == null) {
output[count++] = b;
j++;
} else if (b != null && b.compareTo(a) <= 0) {
output[count++] = b;
j++;
} else {
output[count++] = a;
i++;
}
}
int x = 0;
int size = aStart + aLength + bLength;
for (int y = aStart; y < size; y++) {
unsorted[y] = output[x++];
}
}
}
最新文章
- sphinx的配置
- REST风格URL
- 界面排版-TableLayout的stretchColumns方法
- [软件测试]Linux环境中简单清爽的Google Test （GTest）测试环境搭建（初级使用）
- 详细解读Jquery的$.get(),$.post(),$.ajax(),$.getJSON()用法
- CrowdFlower Winner's Interview: 1st place, Chenglong Chen
- System.Data.SqlTypes.SqlNullValueException: 数据为空。不能对空值调用此方法或
- Object.defineProperty vs __defineGetter__ vs normal
- QT GUI总结
- mysql 获取当前日期及格式化
- getMetaData()
- 使用C++名单在文档处理和学生成绩管理系统相结合
- QT creator编程C++第一步，说“Hello world!”
- Java基础学习笔记十九 IO
- MySQL官方教程及各平台的安装教程和配置详解入口
- SQL介绍
- static全局变量与普通全局变量的区别，static局部变量与普通局部变量的区别，static函数与普通函数的区别
- 福大软工1816 - 第八次作业（课堂实战）- 项目UML设计
- Postman—构建工作流
- AGC006C Rabbit Exercise