欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

归并算法排序 博客分类: 常见排序算法  

程序员文章站 2024-03-19 10:21:46
...

归并算法排序

 

算法思想
  • 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它们的值相等,经过排序后它们相对的位置没有发生交换,那么我们称这个排序算法是稳定的。

  • 归并算法排序
            
    
    博客分类: 常见排序算法  
  • 大小: 779 KB