解答
思路:
将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列
单趟逻辑:
Void merge (int []a , int left, int right, int middle)
{
//开辟新的空间,记录合并后的数据
int [] tempArr = new int [a.length];
int mid = middle + 1; //右侧开始位置
int cur = left ; //记录新数组插入位置
int temp = left; //用于将新数组赋值回原数组
while(left <= middle && mid <= right)
{
//从两个数组里选小的数放到新数组中
if (a[left] <= a[mid])
tempArr[cur ++] = a[left ++];
else
tempArr[cur ++] = a[mid++];
//将两个数组剩余的数插入新数组
while(left <= middle)
tempArr[cur++] = a[left++]
while(mid < =right)
tempArr[cur++] = a[mid ++];
while(temp < =right)
{
a[temp] = tempArr[temp]; temp++;
}
}
}
void mergeSort(int []a, int left, int right)
{
if(left < right)
{
int middle = (left +right)/2;
mergeSort (a, left, middle);//对左边进行递归
mergeSort(a, middle+1,right);//右边
merge(a, left, right, middle); //合并
}
感谢前辈