排序算法java实现归并排序

 

public class MergeSort {

//归并排序

//基本思想：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

//首先考虑下如何将两个有序数列合并：

//比较两个数列的第一个数，谁小就先去谁，取了后就在对应数列中删除这个数，然后再进行比较，

//如果数列为空，那么将另一个数列的数据依次取出即可。

 

//解决了两个数列合并问题，再来看归并排序，基本思路就是：

//将数组分成A,B两组，如果这两组内的数据都是有序的，就可以很方便的将这两组数据进行排序。

//那么可以将A,B组各自再分成两组，依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，

//然后再合并相邻的两个小组就可以了，这样通过先递归的分解数列，再合并数列就完成了归并排序你。

 

      //过程

 

//平均时间复杂度：O(nlogn)

//将数列分开成小数列为log(n),和并数列的过程为：O(n)

 

public static void main(String[] args) {

int[] arr = new int[]{6,2,4,1,9,3,6,7,0};

System.out.println("排序前=====");

print(arr);

System.out.println("");

System.out.println("排序后");

int[] temp = new int[arr.length];

mergeSort(arr,0,arr.length-1,temp);

print(arr);

}

 

public static void mergeSort(int[] arr,int first,int last,int[] temp) {

if(first < last){

int middle = (first + last) / 2;

mergeSort(arr,first,middle,temp);

mergeSort(arr,middle+1,last,temp);

mergeArray(arr,first,middle,last,temp);

}

 

}

 

//将两个数组合并

public static void mergeArray(int[] arr, int first,int middle,int last,int[] temp){

int i= first;

int j = middle + 1;

int k = 0;

while(i<=middle && j<=last){

if(arr[i]<=arr[j]){

temp[k] = arr[i];

k++;

i++;

}else{

temp[k] = arr[j];

k++;

j++;

}

}

while(i <= middle){

temp[k] = arr[i];

k++;

i++;

}

 

while(j<=last){

temp[k] = arr[j];

k++;

j++;

}

 

for(int x=0; x<k; x++){

arr[first+x] = temp[x];

}

}

 

public static void print(int[] arr){

for(int i=0; i<arr.length; i++){

System.out.print(arr[i]+",");

}

}

}