已知n个元素的数组将数组排序后输出
@ApiOperation(value="归并", notes="分治法-归并排序")
@GetMapping(value = "/guibingSort")
public int[] guibingsort() {
// 归并排序
// 问题 已知一个n个元素数值数组 排序后输出
int[] s1 = {8,5,6,4,7,1,3,2};
int[] s2 = new int[8];
mergeSort(0,s1.length-1,s1,s2);
return s1;
}
/**
* 分
* @param a
* @param b
*/
public void mergeSort(int a,int b,int[]s1,int[] s2){
if (a>=b) return ;
int mid = (a+b)/2;
mergeSort(a,mid,s1,s2);
mergeSort(mid+1,b,s1,s2);
merge(a,mid,b,s1,s2);
}
/**
* 合
* @param low
* @param mid
* @param hight
*/
public void merge(int low,int mid,int hight,int[] s1,int[] s2){
int i= low, j=mid+1,k=low;
// 比较两边将较小的先给s2
while (i <=mid && j<=hight){
if (s1[i]<s1[j]){
s2[k++] = s1[i++];
}else {
s2[k++]=s1[j++];
}
}
// 当其中一方走到头后 将另一方依序安排到s2后面
while (i<=mid){
s2[k++]=s1[i++];
}
while (j<=hight){
s2[k++]=s1[j++];
}
// 将s2 从low到hight 复制给s1
for (int l = low; l <= hight; l++) {
s1[l]=s2[l];
}
}
复杂度 O(nlogn)
