文章目录
  1. 1. 归并排序的原理及时间复杂度

归并排序的原理及时间复杂度

  • 归并排序的定义:

    归并排序算法采用的是分治算法,即先把要排序的数组分成两个(或两个以上)有序表,然后再合并成一个新的有序表,即把待排序的序列分成若干个子序列,每个子序列都是有序的,然后把有序子序列合并成整体有序序列,这个过程也称为2-路归并.注意:归并排序的一种稳定排序,即相等元素的顺序不会改变.

  • 归并排序的原理

    将待排序的数组分成前后两个部分,再递归的将前半部分数据和后半部分的数据各自归并排序,得到的两部分数据,然后使用merge合并算法(算法见代码)将两部分算法合并到一起。
    例如:如果N=1;那么只有一个数据要排序,N=2,只需要调用merge函数将前后合并,N=4,……….. 也就是将一个很多数据的数组分成前后两部分,然后不断递归归并排序,再合并,最后返回有序的数组。

  • 归并排序的时间复杂度

    归并排序的最好、最坏和平均时间复杂度都是O(nlogn),而空间复杂度是O(n),比较次数介于(nlogn)/2和(nlogn)-n+1,赋值操作的次数是(2nlogn)。因此可以看出,归并排序算法比较占用内存,但却是效率高且稳定的排序算法。

  • 代码:

      public class MergeSort {
        private static void mergeSort(int[] array,int[] tmp,int left,int right){
            if(left<right){
                int center = ( left + right ) / 2;//取数组的中点
                mergeSort(array,tmp,left,center);//归并排序数组的前半部分
                mergeSort(array,tmp,center+1,right);//归并排序数组的后半部分
                merge(array,tmp,left,center+1,right);//将数组的前后半部分合并
            }
        }
        /*
         * 超简单的合并函数
         */
        private static void merge(int[] array, int[] tmp, int leftPos, int rightPos, int rightEnd) {
            // TODO Auto-generated method stub
            int leftEnd = rightPos - 1;
            int tmpPos = leftPos;
            int numElements = rightEnd - leftPos + 1;
            while(leftPos <= leftEnd && rightPos <= rightEnd){
                if(array[leftPos]<=array[rightPos]){
                    tmp[tmpPos++] = array[leftPos++];
                }else{
                    tmp[tmpPos++] = array[rightPos++];
                }
            }
            while(leftPos <= leftEnd){
                tmp[tmpPos++] = array[leftPos++];
            }
            while(rightPos <= rightEnd){
                tmp[tmpPos++] = array[rightPos++];
            }
            for(int i=0;i<numElements;i++,rightEnd--){
                array[rightEnd] = tmp[rightEnd];
            }
        }
        public static void mergeSort(int[] array){
            int[] tmp = new int[array.length];//声明一个用来合并的数组
            mergeSort(array,tmp,0,array.length-1);//调用排序函数,传入数字的起点和终点
        }
    }
    

更多精彩内容,请关注公众号:轮子工厂,公众号内回复:我要造轮子,可免费获得100本计算机经典电子图书; 回复:福利,获取大学生礼包; 回复:加群,邀请您进高手如云技术交流群。

文章目录
  1. 1. 归并排序的原理及时间复杂度