java之——归并排序

1.两路归并的排序算法思想2 算法实现3 算法分析 归并排序： 采用分治的思想。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。内排序的两路。

1.两路归并的排序算法思想

分而治之；每个递归过程分为以下三个过程 1> 分解：将代排序的n个元素分为两个子序列，每个子序列包含元素个数为n/2 2> 治理：对着两个子序列调用归并排序MergeSort，进行递归操作 3> 合并：合并两个排序好的子序列 过程如下：

2 算法实现

import java.util.Scanner; public class MergeSort { public static void sort(int[] a,int left,int right){ //递归终止条件 if(left>=right){ return; } //取中间位置 int mid = left+(right-left)/2; sort(a,left,mid); sort(a,mid+1,right); //两路合并 mergeSort(a,left,mid,right); } public static void mergeSort(int[] a,int left,int mid,int right){ int[] temp = new int[right-left+1]; int i = left; int j = mid+1; int k = 0; //小的加入数组 while (i<= mid&&j<=right){ if(a[i]<=a[j]){ temp[k++] = a[i++]; }else { temp[k++] = a[j++]; } } //左边剩余的 while(i<=mid){ temp[k++] = a[i++]; } //右边剩余的 while(j<=right){ temp[k++] = a[j++]; } //把新数组的值覆盖原数组的值 for (int x = 0;x<temp.length;x++){ a[x+left] = temp[x]; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); //一个或多个空格 String [] a = in.nextLine().split("\\s+"); int [] s = new int[a.length]; int k = 0; for(String i:a){ s[k++] = Integer.parseInt(i); } sort(s,0,s.length-1); for(Integer i:s){ System.out.print(i+" "); } } }

3 算法分析

稳定性：稳定的排序算法

时间复杂度：　对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。

空间复杂度： 辅助空间复杂度为O(n)，显然它不是就地排序。