算法——归并排序
程序员文章站
2022-07-03 19:37:42
归并排序算法是基于归并(Merge)操作的一种有效排序算法,是采用分治法(Divide and Conquer)的典型应用。基本思想:归并排序的原理是先将原始数组分解为多个子序列,然后对每个子序列进行排序,最后将排好序的子序列合并起来。/** * @Classname A * @Description TODO * @Date 2020/12/30 11:15 * @Created zzf */public class A { public static void main...
归并排序算法是基于归并(Merge)操作的一种有效排序算法,是采用分治法(Divide and Conquer)的典型应用。
基本思想:归并排序的原理是先将原始数组分解为多个子序列,然后对每个子序列进行排序,最后将排好序的子序列合并起来。
/**
* @Classname A
* @Description TODO
* @Date 2020/12/30 11:15
* @Created zzf
*/
public class A {
public static void main(String[] args) {
int[] arr = {11, 44, 5, 67, 49, 65, 1, 48, 9, 12};
int[] tmp = new int[arr.length];
for (int a : arr) {
System.out.print(a + " ");
}
System.out.println("\n--------------------------------");
mergeSort(arr, 0, arr.length - 1, tmp);
System.out.println("--------------------------------");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void merge(int[] arr, int low, int mid, int high, int[] tmp) {
int i = 0;
//左边序列
int j = low;
//右边序列起始索引
int k = mid + 1;
while (j <= mid && k <= high) {
if (arr[j] < arr[k]) {
tmp[i++] = arr[j++];
} else {
tmp[i++] = arr[k++];
}
}
//若左边序列还有剩余,则将其全部拷贝进tmp[]中
while (j <= mid) {
tmp[i++] = arr[j++];
}
//若右边序列还有剩余,则将其全部拷贝进tmp[]中
while (k <= high) {
tmp[i++] = arr[k++];
}
//将临时数组中的数据覆盖入原数组中
for (int t = 0; t < i; t++) {
arr[low + t] = tmp[t];
}
}
public static void mergeSort(int[] arr, int low, int high, int[] tmp) {
if (low < high) {
int mid = (low + high) / 2;
//对左边序列进行归并排序
mergeSort(arr, low, mid, tmp);
//对右边序列进行归并排序
mergeSort(arr, mid + 1, high, tmp);
//合并两个有序序列
merge(arr, low, mid, high, tmp);
for (int a : arr) {
System.out.print(a + " ");
}
System.out.println();
}
}
}
本文地址:https://blog.csdn.net/qq_37598011/article/details/111986865