基于JAVA的merge sort
花了一天的时间，一直在边界+1 -1处挣扎，总算完成了，给大家共享一下，大家也提意见。
File 1:sort.java
package com.cmcc.algorithms.sort;
public class Sort {
public static void insertionSort(int[] arr) {
int key = 0;
int j = 0;
for (int i = 1; i < arr.length; i++) {
key = arr[i];
for (j = i; j > 0 && key < arr[j - 1]; j--) {
arr[j] = arr[j - 1];
}
arr[j] = key;
}
}
public static void mergeSort(int[] array, int p, int q) {
if (p < q) {
int m = (q + p) / 2;
mergeSort(array, p, m);
mergeSort(array, m + 1, q);
merge(array, p, m, q);
}
}
private static void merge(int[] array, int p, int m, int q) {
int[] left = new int[m - p + 2];
int[] right = new int[q - m + 1];
for (int i = 0; i < left.length - 1; i++)
left[i] = array[p + i];
for (int i = 0; i < right.length - 1; i++)
right[i] = array[m + i + 1];
left[m - p + 1] = Integer.MAX_VALUE;
right[q - m] = Integer.MAX_VALUE;
int i = 0;
int j = 0;
int k = 0;
while (k < (q - p + 1)) {
if (left[i] < right[j]) {
array[p + k] = left[i];
i++;
k++;
} else {
array[p + k] = right[j];
j++;
k++;
}
}
}
}
File 2:sortTest.java
package com.cmcc.algorithms.sort;
import org.junit.*;
public class SortTest {
@Test
public void TestInsertSort(){
int[] arr = new int[]{3,9,4,2,1,87,23,22,2342,0,2,3,8,33,87};
Sort.insertionSort(arr);
for(int i:arr)
System.out.print(i+" ");
for(int i = 0;i<arr.length-1;i++){
Assert.assertTrue(arr[i]<=arr[i+1]);
}
System.out.println();
}
@Test
public void TestMergeSort(){
int[] arr = new int[]{3,9,39383,3,88,4,122,34,23,1,2323,233,1,8,55,0,33,87};
Sort.mergeSort(arr,0,arr.length-1);
for(int i:arr)
System.out.print(i+" ");
for(int i = 0;i<arr.length-1;i++){
Assert.assertTrue(arr[i]<=arr[i+1]);
}
System.out.println();
}
}
[解决办法]
public class Mergesort
{
public static void merge(int a[],int pl,int mid,int pr)
{
int temp[]=new int[pr-pl+1];
int i=0,left=pl,right=mid+1;
while(left<=mid && right<=pr)
{
temp[i++]=a[left]<a[right] ? a[left++]:a[right++];
}
while(left<=mid)
{
temp[i++]=a[left++];
}
while(right<=pr)
{
temp[i++]=a[right++];
}
for(int j=0,k=pl;k<=pr;j++,k++)
{
a[k]=temp[j];
}
}
public static void sort(int a[],int left,int right)
{
int mid;
if(left<right)
{
mid=(left+right)/2;
sort(a,left,mid);
sort(a,mid+1,right);
merge(a,left,mid,right);
}
}
public static void main(String args[])
{
int a[]=new int[]{35,123,5,95,56,242,43,44,65,24};
Mergesort.sort(a, 0, a.length-1);
for(int i=0;i<a.length;i++)
{
System.out.printf("%-5d",a[i]);
}
}
}
