归并算法排序

 

算法思想

• 1.简单地将原始序列划分为两个子序列
• 2.分别对每个子序列递归排序
• 3.最后将排好序的子序列合并为一个有序的序列，即归并过程 

 

归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

 

java 代码
 

/**
 * 内部排序算法之归并排序
 * 默认按照从小到大进行排序操作
 * @author 小浩
 * @创建日期 2015-3-27
 */
public class Test{
    public static void main(String[] args) {
   //需要进行排序的数组
    int[] array=new int[]{8,3,2,1,7,4,6,5};
     //输出原数组的内容
    printResult(array);
    //归并排序操作
    sort(array,0,array.length-1);
    //输出排序后的相关结果
    printResult(array);
    }
     
    /**
     * 归并排序
     * @param array
     */
    private static void sort(int[] array,int i,int j) {
        if(i<j)
        {
            int middle=(i+j)/2;
            //递归处理相关的合并事项
            sort(array,i,middle);
            sort(array,middle+1,j);
            merge(array,i,middle,j);           
        }
    }
 
 
    /**
     * 合并相关的数组内容
     * 同时使合并后的数组仍然有序
     * @param array
     * @param i
     * @param middle
     * @param j
     *  4 5 6     9 10 11
     *
     */
    private static void merge(int[] array, int i, int middle, int j) {
        //创建一个临时数组用来存储合并后的数据
        int[] temp=new int[array.length];
        int m=i;
        int n=middle+1;
        int k=i;
        while(m<=middle&&n<=j)
        {
            if(array[m]<array[n])
                temp[k++]=array[m++];
            else
                temp[k++]=array[n++];
        }
        //处理剩余未合并的部分
        while(m<=middle)
        {
            temp[k++]=array[m++];
        }
        while(n<=j)
        {
            temp[k++]=array[n++];
        }
        //将临时数组中的内容存储到原数组中
        while(i<=j)
        {
            array[i]=temp[i++];
        }
    }
 
 
    /**
     *                                       
     * 输出相应数组的结果
     * @param array
     */
    private static void printResult(int[] array) {
       for(int value:array)    
           System.out.print(" "+value+" ");
      System.out.println();
    }
 
    /**
     * 交换数组中两个变量的值
     * @param array
     * @param i
     * @param j
     */
    private static void swap(int[] array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
}

 

排序算法的基本概念的讲解

     时间复杂度:需要排序的的关键字的比较次数和相应的移动的次数。

     空间复杂度:分析需要多少辅助的内存。

     稳定性:如果记录两个关键字的A和B它们的值相等，经过排序后它们相对的位置没有发生交换，那么我们称这个排序算法是稳定的。