合并排序
闲来无事，来写写合并排序，第一次看到合并排序，我相信大家可能像我一样感觉看的有点迷糊，特别合并排序的思想：是将一个数组分成2个较小有序的数组，然后才进行合并排序。迷糊的地方：主要是下面涂色的地方，在归并前2个数组有序（怎么有序呢？），然后只要大家联想到递归或者树的遍历就知道，在将每个较大的数组拆分的时候呈现一个树形，到最后只有一个数字（有序），然后再依此合并。
importjava.util.*;
public class Merge1{ private int[] bridge;
publicstaticvoidmain(Stringargs[])
{
int[]brige={34,12,43,5,89,3};
Merge1mg=newMerge1();
mg.sort(brige);
for(inti=0;i<brige.length;i++)
System.out.println(""+brige[i]);
}
/**
*利用归并排序算法对数组obj进行排序
*/
public void sort(int[] obj)
{
bridge = new int[obj.length]; //初始化中间数组
mergeSort(obj, 0, obj.length - 1); //归并排序
//bridge = null;
}
/**
*将下标从left到right的数组进行归并排序
*@param obj 要排序的数组的句柄
*@param left 要排序的数组的第一个元素下标
*@param right 要排序的数组的最后一个元素的下标
*/
private void mergeSort(int[] obj, int left, int right)
{
if (left < right)
{
int center = (left + right)/2;
mergeSort(obj, left, center);
mergeSort(obj, center + 1, right);
merge(obj, left, center, right);
}
}
/**
*将两个对象数组进行归并，并使归并后为升序。归并前两个数组分别有序
*@param obj 对象数组的句柄
*@param left 左数组的第一个元素的下标
*@param center 左数组的最后一个元素的下标
*@param right 右数组的最后一个元素的下标
*/
private void merge(int[] obj, int left, int center, int right)
{
int mid = center + 1;
int third = left;
int tmp = left;
while (left <= center && mid <= right)
{
//从两个数组中取出小的放入中间数组
if (obj[left]<=obj[mid])
{
bridge[third++] = obj[left++];
}
else
bridge[third++] = obj[mid++];
}
//剩余部分依次置入中间数组
while (mid <= right)
{
bridge[third++] = obj[mid++];
}
while (left <= center)
{
bridge[third++] = obj[left++];
}
//将中间数组的内容拷贝回原数组
copy(obj, tmp, right);
}
/**
*将中间数组bridge中的内容拷贝到原数组中
*@param obj 原数组的句柄
*@param left 要拷贝的第一个元素的下标
*@param right 要拷贝的最后一个元素的下标
*/
private void copy(int[] obj, int left, int right)
{
while (left <= right)
{
obj[left] = bridge[left];
left++;
}
}
}