归并排序属于分治算法
分治法在每一层递归上都有三个步骤:
step1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
step2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;
step3 合并:将各个子问题的解合并为原问题的解;
void mergeSort(int q[], int l, int r)
{
//递归终止的条件
if(l >= r) return;
//第一步:分解成子问题
int mid = l + r >> 1;
//第二步:递归处理子问题
merge_sort(q, l, mid ), merge_sort(q, mid + 1, r);
//第三步:合并子问题
int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
while(i <= mid && j <= r)
if(q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//创建数组并设置数组长度
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
//输入数组元素
String[] ss = br.readLine().split(" ");
for (int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(ss[i]);
}
merge_sort(arr, 0, n - 1);
for (int i = 0;i<arr.length;i++){
System.out.print(arr[i] + " ");
}
}
//归并排序模板
private static void merge_sort(int[] q, int l, int r) {
if (l >= r) return;
int temp[] = new int[r - l + 1], k = 0;
//1.中间点
int mid = l + r >> 1;
//2.递归排序左右两段
merge_sort(q, l, mid);
merge_sort(q, mid + 1,r);
//3.合并子问题
int i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (q[i] <= q[j]) {
temp[k++] = q[i++];
} else {
temp[k++] = q[j++];
}
}
while (i <= mid) {
temp[k++] = q[i++];
}
while (j <= r) {
temp[k++] = q[j++];
}
for (int m = l,x = 0;m<=r;m++,x++){
q[m] = temp[x];
}
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。