归并排序

归并排序 java中的归并排序 为什么使用归并排序, java中的Arrays.sort(Object[] o)是对数组进行排序，它使用的是归并排序的方式， 快速排序要比归并排序更快一些，但为什么使用归并排序了,原因是归并排序是一种稳定的排序 方式，即归并排序不交换相同的元素，这就意味着，在按一种方式排序后同时可以按另外一种 方式进行排序。比如员工可以首先按工资排序，然后按名字排序，一种排序不会打乱另一种排序 的顺序。 下面分析下sort方法的简化版: Java代码 , /** , * 归并排序 (递归实现) , * 前提: 每个元素要有可比性，这里元素必须实现 Comparable接口。 , * 基本原理为:1.拆分 假设有N个元素的列表，首 先把它拆分成2个或2个 , * 以上的元素组成的新的列表(这里我的新列表长度 不超过3)，分别对对它们进行排序。 , * 2.归并。把所有的排好序的子类表两两归并，如此 重复，直到归并成一个含N个 , * 元素的有序列表为止 , * 图解:(大于3就继续分解) ？ * 大于3 8 7 6 5 4 3 2 1 ,, * 分|解 ,, * | ,, * 大于3 8 7 6 5 4 3 2 1 ,, * 分|解 分|解 ,, * | | ,, * 小于 3 8 7 6 5 4 3 2 1 ,, * 排序 7 8 5 6 3 4 1 2 ,, * 归并 | | ,, * 7 8 5 6 3 4 1 2 ,？ * | | ,, * 顺序保存 5 6 7 8 1 2 3 4 ,, * | ,, * 归并 5 6 7 8 1 2 3 4 ,, * | ,, * 顺序保存 1 2 3 4 5 6 7 8 ,, * @param src 临时中间数组，它是目标数组的拷贝 ,, * @param target 目标排序数组 ,, * @param low 需排序的起始索引 ,, * @param high 需排序的结束索引 ,？ * ,, */ ,, public static void mergeSort(Object[] src,Object[] dest,int low,int high){ ,, int length = high - low; ,, if(length < 3 ){ //对长度小于3的列表排序 ,, //排序方法一:起泡排序(大数沉底) ,, // for(int i=low;i 0){ ,, // swap(dest, j, j+1); ,？ // } ,, // } ,, // } ,, //排序方法二:这是起泡排序的一种变体(小数上浮) ,, for (int i = low; i < high; i++){ ,, for (int j = i; j > low ; j--){ ,, if(((Comparable) dest[j - 1]).compareTo(dest[j]) > 0){ ,, swap(dest, j-1, j); ,, } ,, } ,？ } ,, return; ,, } ,, ,, int mid = (high + low)/2; //拆分 ,, mergeSort(dest, src, low, mid); //递归，可能会 继续拆分(那么必然继续合并) ,, mergeSort(dest, src, mid, high); ,, ,, //开始归并,方法一 ,, // for(int i=low,p=low,q=mid;i= high || (p < mid &&((Comparable) src[p]).compareTo(src[q]) <= 0)){ ,, // dest[i] = src[p++]; ,, // }else{ ,, // dest[i] = src[q++]; ,, // } ,, // } ,, ,, //开始归并，方法二 ,, int i = low; ,？ int p = low; //第一个列表指针 ,, int q = mid; //第二个列表指针 ,, while(p < mid && q = len){ ,,, high = len; ,,, } ,,, int l = high - low; ,,, if(l <= INSERTIONSORT_THRESHOLD){ ,,, sort(src,low,high); ,,, break; ,,, } ,,？ ,,, if(spreCount == 3){ //所有拆分的列表只进行一次排序 ,,, sort(dest,low,mid); ,,, sort(dest,mid,high); ,,, } ,,, if(l == len) //最后一次归并把src有次序的赋给dest ,,, Merge(src,dest,low,mid,high); ,,, else ,,, Merge(dest,src,low,mid,high); ,,, ,,？ } ,,, spreCount *= 2; ,,, } ,,, ,,, } ,,, //对拆分的每个列表进行排序 ,,, private static void sort(Object[] dest,int low,int high){ ,,, for (int i = low; i < high; i++){ ,,, for (int j = i; j > low ; j--){ ,,, if(((Comparable) dest[j - 1]).compareTo(dest[j]) > 0){ ,,？ swap(dest, j-1, j); ,,, } ,,, } ,,, } ,,, } ,,, ,,, //归并相邻两个列表并保存在dest中 ,,, private static void Merge(Object[] src, Object[] dest, int low, int mid, ,,, int high) { ,,, int i = low; ,,？ int p = low; //第一个列表指针 ,,, int q = mid; //第二个列表指针 ,,, while(p < mid && q