归并排序

  • 更新时间: 2018-12-14
  • 来源: 原创或网络
  • 浏览数: 18次
  • 字数: 5172
  • 发表评论
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

1 分而治之

归并排序,by 5lulu.com

可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。

2 合并相邻有序子序列

再来看看阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。  归并排序,by 5lulu.com

归并排序,by 5lulu.com

3 代码实现

public static void insertsort(int arr[]){                
        for(int i = 1;i < arr.length; i ++){
            if(arr[i] < arr[i-1]){//注意[0,i-1]都是有序的。如果待插入元素比arr[i-1]还大则无需再与[i-1]前面的元素进行比较了,反之则进入if语句
                int temp = arr[i];
                int j;
                for(j = i-1; j >= 0 && arr[j] > temp; j --){                
                        arr[j+1] = arr[j];//把比temp大或相等的元素全部往后移动一个位置            
                }
                arr[j+1] = temp;//把待排序的元素temp插入腾出位置的(j+1)
            }            
        }
        
    }
        
    public static void main(String[] args) {
        int array[] = {4,2,1,5};
        
        System.out.println("排序之前:");
        for(int element : array){
            System.out.print(element+" ");
        }
        
        insertsort(array);
        System.out.println("\n排序之后:");        
        for(int element : array){
            System.out.print(element+" ");
        }
    }
}
执行结果

[1, 2, 3, 4, 5, 6, 7, 8, 9]

4 最后

归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。


标签: 排序 int

我来评分 :6
0

转载注明:转自5lulu技术库

本站遵循:署名-非商业性使用-禁止演绎 3.0 共享协议

相关推荐