精华内容
下载资源
问答
  • 二路归并排序

    2015-06-06 23:21:31
    编写程序对{75.,87,68,92,88,61,77,96,80,72}进行二路归并排序
  • 主要介绍了java二路归并排序示例,需要的朋友可以参考下
  • 【Java常用排序算法】归并排序(二路归并排序

    千次阅读 多人点赞 2017-02-27 23:17:10
    归并排序 二路归并排序 Java实现

    归并排序的思路

    归并排序是通过“归并”操作完成排序的,将两个或者多个有序子表归并成一个子表。归并排序是“分治法”的一个非常典型的应用,同时它也是递归算法的一个好的实例。它将问题分成一些小的问题然后递归求解,而治就是把分阶段的答案拼起来。

    二路归并排序

    • 基本思想
      二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并:两个有序表放在同一数组的相邻位置上,arr[left]到arr[center-1]为第一个有序表,arr[center]到arr[right]是第二个有序表。每次从两段中取出一个进行比较,小的先放入一个temp数组,最后将比较剩下的直接放到temp中去,最后将temp又复制回arr。这是“治”。
      下面说“分”,只需要递归地将前半部分和后半部分的数据各自归并排序即可。
    • 例子
      {3,6,1,7,9,4,5,8,2}
      二路归并排序的过程如图所示:
    • 算法分析
      每一趟归并的时间复杂度为O(n),共需要进行⌈log2n⌉趟。对应的算法的时间复杂度为O(nlog2n)。归并排序的空间复杂度O(n)。另外,归并排序中归并的算法并不会将相同关键字的元素改变相对次序,所以归并排序是稳定的。
    • Java代码实现
    package com.gray;
    
    import java.util.Arrays;
    
    public class MergeSort {
        public static void main(String args[]) {
            int a[] = {3, 6, 1, 7, 9, 4, 5, 8, 2};
            mergeSort(a);
            System.out.println("排序后:" + Arrays.toString(a));
        }
    
        private static void mergeSort(int[] arr) {
            mergeSort(arr, new int[arr.length], 0, arr.length - 1);
        }
    
        private static void mergeSort(int[] arr, int[] temp, int left, int right) {
            if (left < right) {
                int center = (left + right) / 2;
                mergeSort(arr, temp, left, center); // 左边
                mergeSort(arr, temp, center + 1, right); // 右边
                merge(arr, temp, left, center + 1, right); // 合并两个有序
            }
        }
    
        /**
         * 将两个有序表归并成一个有序表
         *
         * @param arr
         * @param temp     临时数组
         * @param leftPos  左边开始下标
         * @param rightPos 右边开始下标
         * @param rightEnd 右边结束下标
         */
        private static void merge(int[] arr, int[] temp, int leftPos, int rightPos, int rightEnd) {
            int leftEnd = rightPos - 1; // 左边结束下标
            int tempPos = leftPos; // 从左边开始算
            int numEle = rightEnd - leftPos + 1; // 元素个数
            while (leftPos <= leftEnd && rightPos <= rightEnd) {
                if (arr[leftPos] <= arr[rightPos])
                    temp[tempPos++] = arr[leftPos++];
                else
                    temp[tempPos++] = arr[rightPos++];
            }
            while (leftPos <= leftEnd) {  // 左边如果有剩余
                temp[tempPos++] = arr[leftPos++];
            }
            while (rightPos <= rightEnd) { // 右边如果有剩余
                temp[tempPos++] = arr[rightPos++];
            }
            // 将temp复制到arr
            for (int i = 0; i < numEle; i++) {
                arr[rightEnd] = temp[rightEnd];
                rightEnd--;
            }
        }
    }
    
    展开全文
  • 前面有篇文章已经写了选择类排序、交换类排序和插入类排序(传送门),下面将介绍二路归并排序和基数排序。 二路归并排序 1、执行过程        原始序列:45 35 65 95 75 15 25 &...

    写在前面

           前面有篇文章已经写了选择类排序、交换类排序和插入类排序(传送门),下面将介绍二路归并排序和基数排序。

    二路归并排序

    1、执行过程

           原始序列:45 35 65 95 75 15 25
           1)将原始序列看作是7个有序的含有一个关键字的子序列
           子序列1:45
           子序列2:35
           子序列3:65
           子序列4:95
           子序列5:75
           子序列6:15
           子序列7:25
           2)两两归并,形成若干个有序的二元组
           {35,45} , {65,95} , {15,75} , {25}
           3)再将这个序列当作若干个二元组的子序列
           子序列1:35    45
           子序列2:65    95
           子序列3:15    75
           子序列4:25
           4)继续两两归并,形成若干个有序的四元组
           {35,45,65,95} , {15 ,25 ,75}
           5)最后只剩下两个子序列,再进行一次归并,就完成了整个二路归并排序,结果如下
           15    25    35    65    75    95

    2、算法代码

          由执行过程可知,归并排序可以看作是一个分而治之的过程:先将整个序列分成两半,对每一半分别进行归并排序,将得到两个有序序列,然后将这两个序列合并成一个序列即可。

    void mergeSort(int R[] , int low , int high){
    	if(low < high){
    		int mid = (low + high)/2;
    		mergeSort(R,low,mid);
    		mergeSort(R,mid+1,high);
    		merge(R,low,mid,high);//合并算法,将两个有序的序列合并成一段有序序列
    	}
    }
    

    3、性能分析

          时间复杂度O(nlogn),空间复杂度O(n)

    基数排序

    1、执行过程

          初始桶如下图所示:在这里插入图片描述
          原始序列:78   09   63   30   89   84   05   69   08   83
          1)进行第一趟分配和收集,按最后一位分配,如:
          78的最低位为8,放到桶8中,如下图所示:
    在这里插入图片描述
          09的最低位是9,放到桶9,如下图所示:
    在这里插入图片描述
          依次将原始序列的每个数放到桶中,结果如下图所示:在这里插入图片描述
          然后按照桶0到9的顺序,从桶下面收集关键字,结果为:
            30  63  83  84  05  78  08  09  89  69
          2)在第一趟排序的基础上,进行第二趟分配和收集,按照倒数第二位(本例中是第一位),结果如下图所示:
    在这里插入图片描述
          然后收集,结果为:
            05  08  09  30  63  69  78  83  84  89
          现在最高位有序,最高位相同的关键字最低位有序,于是整个序列有序,基数排序结束。

    3、性能分析

          时间复杂度:O(d(n+r)),空间复杂度O(r),其中,n为序列中关键字的个数,d为关键字的位数,r为关键字基的个数。

    展开全文
  • 主要介绍了c++实现二路归并排序的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • C++ 二路归并排序

    2017-03-28 10:32:42
    二路归并排序

    最坏时间复杂度O(nlogn)
    最好时间复杂度O(nlogn)

    void merge(int *a,int lo,int mi, int hi){
        int nl = mi-lo+1;//左边的长度
        int nr = hi - mi;//右边的长度 
    
       int *L = new int[nl+1];//空出一个哨兵的位置
       int *R = new int[nr+1];
       L[nl] = 100000;//左边队列的哨兵
       R[nr] = 100000;//右边队列的哨兵
      int i,j,k;
      for(i=0; i<nl; i++){
            L[i] = a[lo+i];//把左边部分的值赋给一个保存左边值的临时队列
        }
    
        for(j=0; j<nr;j++)
            R[j] = a[mi+1+j];
    
        //k从lo的位置开始
        for(i =0,j=0,k=lo;k<= hi;k++){
            if(L[i] <= R[j]){//把较小的值赋给主队列
                a[k] =L[i];
                i++;
            }else{
                a[k] = R[j];
                j++;
            }
        }
    
        delete []L;
        delete []R;
    }
    
    void mergeSort(int *a, int lo,int hi){
        if(lo < hi){
            int mi = (lo+hi) >> 1;
            mergeSort(a,lo,mi);
            mergerSort(a,mi+1,hi);
            merge(a,lo,mi,hi);
        }
    }
    
    void main(){
        int a[] = {9,8,7,6,5,4,3,2,1};
        int n = sizeof(a)/sizeof(a[0]);
        int lo = 0;
        int hi = n-1;
        mergeSort(a,lo,hi);
    
    
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,745
精华内容 8,698
关键字:

二路归并排序