归并排序的详解_JAVA_编程开发_程序员俱乐部

package org.com.cn.排序;

import java.util.Arrays;
/**
*
* @author 归并排序
* 主要的思想是：将两个或两个以上的有序合并成一个新的有序列表 即把待排序序列分为若干个
* 有序的子序列 再把有序的子序列合并为整体有序的序列
*
*/
public class 归并排序 {
public static void mergeSort(int[] list){
if(list.length > 1){
//声明一个子序列
int[] firstHalf = new int[list.length/2];
//将待排序的序列的一半复制到子序列中
System.arraycopy(list, 0, firstHalf, 0, list.length/2);
System.out.println("1:"+Arrays.toString(firstHalf));
//递归调用mergSort方法 对子序列进行划分 排序
mergeSort(firstHalf);
System.out.println("2:"+Arrays.toString(firstHalf));
//声明另一个子序列
int[] secondHalf = new int[list.length-list.length/2];
//将待排序的后半部分复制到子序列中
System.arraycopy(list, list.length/2, secondHalf, 0, list.length-list.length/2);
System.out.println("3:"+Arrays.toString(secondHalf));
//递归调用mergSort方法 对子序列进行划分 排序
mergeSort(secondHalf);
System.out.println("4:"+Arrays.toString(secondHalf));
//将两个排序好的子序列进行 归并 并且 排序
int[] temp = merge(firstHalf,secondHalf);
System.out.println("temp:"+Arrays.toString(temp));
System.arraycopy(temp, 0, list, 0,temp.length);
}
}
/**
*
* @param list1  第一个子序列
* @param list2 第二个子序列
* @return 返回一个合并的有序序列
*/
private static int[] merge(int[] list1,int[] list2){
//声明一个数组 长度是list1和list2数组长度之和
int[] temp = new int[list1.length+list2.length];
int current1 = 0;//list1的当前索引
int current2 = 0;//list2的当前索引
int current3 = 0;//list3是temp的当前索引

while(current1<list1.length && current2<list2.length){
/**
* 当list1当前下标值 比list2的当前下标值小的话 就将list1当前下标值 赋值给temp的当前下标值
* 否就是list2的当前下标值 赋值给 temp的当前下标值
*/
if(list1[current1] < list2[current2]){
temp[current3++] = list1[current1++];
}else{
temp[current3++] = list2[current2++];
}
}
while(current1 < list1.length){
temp[current3++] = list1[current1++];
}
while(current2 < list2.length){
temp[current3++] = list2[current2++];
}
System.out.println("5:"+Arrays.toString(temp));
return temp;
}
public static void main(String[] args) {
int[] list = {2,4,9,6,1,7,3,5,8,2,4,9,6,1,7,3,5,8,2,4,9,6,1,7,3,5,8,2,4,9,6,1,7,3,5,8,2,4,9,6,1,7,3,5,8};
long startTime=System.currentTimeMillis();
mergeSort(list);
long endTime = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println("总时间："+totalTime);
System.out.println(Arrays.toString(list));
}
}
刚刚学习的 归并道理简单 代码一开始看懵了 一时没有想明白
后面打印一下 了解 希望能帮大家理解