归并排序及优化(Java实现)
2024-09-25 11:51:26
普通归并排序
public class MergeSort {
/**
* @param arr 待排序的数组
* @param left 本次归并的左边界
* @param mid 本次归并的中间位置，也就是分界线
* @param right 本次归并的右边界
* @param <T> 泛型
* @local aux 辅助空间(Auxiliary Space)
*/
private static <T extends Comparable<? super T>> void merge(T[] arr, int left, int mid, int right) {
T[] aux = java.util.Arrays.copyOfRange(arr, left, right + 1);
//aux，i j分别是这两半的起始指针。将这两个闭区间归并[left ... mid] [mid + 1 ... right]
int i = left;
int j = mid + 1;
for (int t = left; t <= right; t++) {//把arr数组中的[left...right]区间都覆盖了，就完事了
if (i > mid) { //i == mid + 1 时越界(跃出左半数组)
arr[t] = aux[j++ - left];
} else if (j > right) {//j == right + 1 时越界(跃出右半数组)
arr[t] = aux[i++ - left];
} else if (aux[i - left].compareTo(aux[j - left]) < 0) {//如果i-left小，那么插入。(左半边数组的指针所指的数小)
arr[t] = aux[i++ - left];
} else { //如果j-left小，那么插入。(右半边数组的指针所指的数小)
arr[t] = aux[j++ - left];
}
}
}
private static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1);
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);//3 5 1 7 2 9 8 0 4 6
sort(arr);
printArr(arr);//0 1 2 3 4 5 6 7 8 9
}
}
归并优化：利用插入排序
当递归到规模足够小时，利用插入排序
public class MergeSort {
/**
* @param arr 待排序的数组
* @param left 本次归并的左边界
* @param mid 本次归并的中间位置，也就是分界线
* @param right 本次归并的右边界
* @param <T> 泛型
* @local aux 辅助空间(Auxiliary Space)
*/
private static <T extends Comparable<? super T>> void merge(T[] arr, int left, int mid, int right) {
T[] aux = java.util.Arrays.copyOfRange(arr, left, right + 1);
//aux，i j分别是这两半的起始指针。将这两个闭区间归并[left ... mid] [mid + 1 ... right]
int i = left;
int j = mid + 1;
for (int t = left; t <= right; t++) {//把arr数组中的[left...right]区间都覆盖了，就完事了
if (i > mid) { //i == mid + 1 时越界(跃出左半数组)
arr[t] = aux[j++ - left];
} else if (j > right) {//j == right + 1 时越界(跃出右半数组)
arr[t] = aux[i++ - left];
} else if (aux[i - left].compareTo(aux[j - left]) < 0) {//如果i-left小，那么插入。(左半边数组的指针所指的数小)
arr[t] = aux[i++ - left];
} else { //如果j-left小，那么插入。(右半边数组的指针所指的数小)
arr[t] = aux[j++ - left];
}
}
}
/**
* @param arr 当规模小的时候对arr采用插入排序
* @param left 待排序部分的左边界
* @param right 待排序部分的右边界
* @param <T> 泛型
*/
private static <T extends Comparable<? super T>> void insertionSort(T[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
T temp = arr[i];
int j = i - 1;
while (j >= 0 && temp.compareTo(arr[j]) < 0) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
private static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {
if (right - left < 7) { //对小规模数据进行插入排序
insertionSort(arr, left, right);
return;
}
int mid = (left + right) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1);
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);//3 5 1 7 2 9 8 0 4 6
sort(arr);
printArr(arr);//0 1 2 3 4 5 6 7 8 9
}
}
归并排序继续优化：归并前判断一下是否还有必要归并
public class MergeSort {
/**
* @param arr 待排序的数组
* @param left 本次归并的左边界
* @param mid 本次归并的中间位置，也就是分界线
* @param right 本次归并的右边界
* @param <T> 泛型
* @local aux 辅助空间(Auxiliary Space)
*/
private static <T extends Comparable<? super T>> void merge(T[] arr, int left, int mid, int right) {
T[] aux = java.util.Arrays.copyOfRange(arr, left, right + 1);
//aux，i j分别是这两半的起始指针。将这两个闭区间归并[left ... mid] [mid + 1 ... right]
int i = left;
int j = mid + 1;
for (int t = left; t <= right; t++) {//把arr数组中的[left...right]区间都覆盖了，就完事了
if (i > mid) { //i == mid + 1 时越界(跃出左半数组)
arr[t] = aux[j++ - left];
} else if (j > right) {//j == right + 1 时越界(跃出右半数组)
arr[t] = aux[i++ - left];
} else if (aux[i - left].compareTo(aux[j - left]) < 0) {//如果i-left小，那么插入。(左半边数组的指针所指的数小)
arr[t] = aux[i++ - left];
} else { //如果j-left小，那么插入。(右半边数组的指针所指的数小)
arr[t] = aux[j++ - left];
}
}
}
/**
* @param arr 当规模小的时候对arr采用插入排序
* @param left 待排序部分的左边界
* @param right 待排序部分的右边界
* @param <T> 泛型
*/
private static <T extends Comparable<? super T>> void insertionSort(T[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
T temp = arr[i];
int j = i - 1;
while (j >= 0 && temp.compareTo(arr[j]) < 0) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
private static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {
// 先注释掉，为了测试
// if (right - left < 7) { //对小规模数据进行插入排序
// insertionSort(arr, left, right);
// return;
// }
if (left >= right) {
return;
}
int mid = (left + right) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
//在归并前判断一下，如果左边的最大的比右边的最小的还小(或者等于)，那就不用归并了，已经有序了。
if (arr[mid].compareTo(arr[mid + 1]) <= 0) {
return;
}
merge(arr, left, mid, right);
}
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1);
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);//3 5 1 7 2 9 8 0 4 6
sort(arr);
printArr(arr);//0 1 2 3 4 5 6 7 8 9
}
}
归并排序继续优化：只在排序前开辟一次空间
public class MergeSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
T[] aux = (T[]) new Comparable[arr.length];
sort(arr, aux, 0, arr.length - 1);
}
private static <T extends Comparable<? super T>> void sort(T[] arr, T[] aux, int left, int right) {
if (right - left < 4) {
insertionSort(arr, left, right);
return;
}
// if (left >= right) {
// return;
// }
int mid = (left + right) / 2;
sort(arr, aux, left, mid);
sort(arr, aux, mid + 1, right);
if (arr[mid].compareTo(arr[mid + 1]) > 0) {
merge(arr, aux, left, mid, right);
}
}
private static <T extends Comparable<? super T>> void merge(T[] arr, T[] aux, int left, int mid, int right) {
System.arraycopy(arr, left, aux, left, right - left + 1);
int i = left;
int j = mid + 1;
for (int t = left; t <= right; t++) {
if (i > mid) {
arr[t] = aux[j++];
} else if (j > right) {
arr[t] = aux[i++];
} else if (aux[i].compareTo(aux[j]) < 0) {
arr[t] = aux[i++];
} else {
arr[t] = aux[j++];
}
}
}
private static <T extends Comparable<? super T>> void insertionSort(T[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
T temp = arr[i];
int j = i - 1;
while (j >= left && temp.compareTo(arr[j]) < 0) {
arr[j + 1] = arr[j--];
}
arr[j + 1] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);//3 5 1 7 2 9 8 0 4 6
sort(arr);
printArr(arr);//0 1 2 3 4 5 6 7 8 9
}
}
最新文章
- 20145337 GDB调试汇编堆栈过程分析
- arcgis engine 监听element的添加、更新和删除事件（使用IGraphicsContainerEvents）
- [Data Structure] 数据结构中各种树
- Android之ListView&ViewPager模拟新闻界面
- U盘安装CentOS7的最终解决方案
- 修改tomcat小猫图标
- (十二)学习CSS之display属性
- 坑爹的IE quirk模式【转】
- c#反序列化
- uva 10718 Bit Mask （位运算）
- android的快速开发框架集合
- devexpress控件layoutview特效之一旋转木马的实现
- checkbox全选、全不选实现
- ABAP 内表数据 与 Json串 相互转换
- 2. MariaDB激活二进制日志
- python 7
- Theano教程：Python的内存管理
- 20155202《网络对抗》Exp8 Web基础
- Level-shifting nixes need for dual power supply
- java中读取配置文件内容，如读取.properties文件