## 归并排序 -java实现 原

Amui

``````public class MergeSort {
//合并两个分组
public static void Merge(int[] arr, int low, int mid, int high){
int i = low;
int j = mid + 1;
int k = 0;
int[] arr2 = new int[high - low + 1];

while(i <= mid && j <= high){
if(arr[i] < arr[j]){
arr2[k++] = arr[i++];
}else{
arr2[k++] = arr[j++];
}
}

while(i <= mid){
arr2[k++] = arr[i++];
}

while(j <= high){
arr2[k++] = arr[j++];
}

for(k = 0, i = low; i <= high; i++, k++){
arr[i] = arr2[k];
}
}

//划分
public static void MergePass(int[] arr, int gap, int length){
int i = 0;
for(i = 0; i + 2 * gap -1 < length; i = i + 2 * gap){
Merge(arr, i, i + gap -1, i + 2 * gap -1);
}

//余下两个分组，其后一个长度小于gap
if(i + gap -1 < length){
Merge(arr, i, i + gap -1, length-1);
}
}

public static void sort(int[] arr){
for(int gap = 1; gap < arr.length; gap = gap * 2){
MergePass(arr, gap, arr.length);
}
}

public static void main(String[] args){
int[] arr = {9, 8, 7, 13, 21, 1, 17, 6};
System.out.println("排序前:");
for(int i = 0; i < arr.length; i++){
System.out.print(arr[i] + ",");
}

sort(arr);

System.out.println("\n排序后:");
for(int i = 0; i < arr.length; i++){
System.out.print(arr[i] + ",");
}
}
}``````

``````public class MergeSort2 {
//合并两个分组
public static void Merge(int[] arr, int low, int mid, int high){
int i = low;
int j = mid + 1;
int k = 0;
int[] arr2 = new int[high - low + 1];

while(i <= mid && j <= high){
if(arr[i] < arr[j]){
arr2[k++] = arr[i++];
}else{
arr2[k++] = arr[j++];
}
}

while(i <= mid){
arr2[k++] = arr[i++];
}

while(j <= high){
arr2[k++] = arr[j++];
}

for(k = 0, i = low; i <= high; i++, k++){
arr[i] = arr2[k];
}
}

public static void sort(int[] arr, int l, int r){
if(l >= r){
return;
}
int mid = (l + r)/2;
sort(arr, l, mid);
sort(arr, mid + 1, r);
Merge(arr, l, mid, r);
}

public static void main(String[] args){
int[] arr = {9, 8, 7, 13, 21, 1, 17, 6};
System.out.println("排序前:");
for(int i = 0; i < arr.length; i++){
System.out.print(arr[i] + ",");
}

sort(arr, 0, arr.length-1);

System.out.println("\n排序后:");
for(int i = 0; i < arr.length; i++){
System.out.print(arr[i] + ",");
}
}
}``````

### Amui

java泛型中使用的排序算法——归并排序及分析

9龙
04/29
0
0

2011/05/12
1K
5

nanchen2251
2018/07/18
0
0

2011/05/12
19
0
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345，以下摘自作者介绍： “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中，对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
178
0

Qt程序打包发布方法（使用官方提供的windeployqt工具）

shzwork
28分钟前
4
0

49分钟前
3
0

59分钟前
6
0

7
0