07-归并排序算法
2021-06-21 08:04
标签：span code ali string ima mic ges wrapper static 归并排序：利用分而治之的思想。 结果： ----- end ----- 07-归并排序算法 标签：span code ali string ima mic ges wrapper static 原文地址：https://www.cnblogs.com/denluoyia/p/9685841.html归并排序算法
归并排序代码
public static void merge(int[] arr, int left, int mid, int right){
int[] temp = new int[right - left + 1]; //新开一个临时数组存放每一代gap排好序的数组
int i = left, j = mid + 1, k = 0;
while (i if (arr[i] temp[k++] = arr[i++];
}else{
temp[k++] = arr[j++];
}
}
while (i temp[k++] = arr[i++];
}
while (j temp[k++] = arr[j++];
}
for (int x = 0; x arr[left+x] = temp[x];
}
}
public static void mergeSort(int arr[], int left, int right){
if (left int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid+1, right);
merge(arr, left, mid, right);
}
}测试样例
int[] arr = {2, 4, 9, 3, 8, 6, 7, 1, 5};
mergeSort(arr, 0, 8);
for (int x : arr){
System.out.print(x + " ");
}1 2 3 4 5 6 7 8 9