一、基本概念
归并排序是将两个有序序列合并成一个有序序列的过程。
详细步骤：
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一序列的指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾，一次归并结束
二、算法特点
是否稳定：true
平均时间复杂度：O(nlogn)
最差时间复杂度：O(nlogn)
最优时间复杂度：O(n)
空间复杂度：　　O(n)
三、相关代码
public static void main(String[] args) {
int[] a = { 57, 68, 59, 52, 72, 28, 96, 33 };
sort(a, 0, a.length-1);
public static void sort(int[] a, int left, int right) {
if (left &= right)
int center = (left + right) && 1;
sort(a, left, center);
sort(a, center + 1, right);
merge(a, left, center, right);
public static void merge(int[] data, int left, int center, int right) {
int[] tmpArr = new int[right+1];
int mid = center + 1;
int index = // index记录临时数组的索引
// 从两个数组中取出最小的放入中临时数组
while (left &= center && mid &= right) {
tmpArr[index++] = (data[left] &= data[mid]) ? data[left++]: data[mid++];
// 剩余部分依次放入临时数组
while (mid &= right) {
tmpArr[index++] = data[mid++];
while (left &= center) {
tmpArr[index++] = data[left++];
// 将临时数组中的内容复制回原数组
for (int i = i &= i++) {
data[i] = tmpArr[i];
System.out.println(Arrays.toString(data));
运行结果：
[57, 68, 59, 52, 72, 28, 96, 33]
[57, 68, 52, 59, 72, 28, 96, 33]
[52, 57, 59, 68, 72, 28, 96, 33]
[52, 57, 59, 68, 28, 72, 96, 33]
[52, 57, 59, 68, 28, 72, 33, 96]
[52, 57, 59, 68, 28, 33, 72, 96]
[28, 33, 52, 57, 59, 68, 72, 96]
阅读(...) 评论() &trackbacks-0
&&& 在学习算法的过程中，我们难免会接触很多和排序相关的算法。总而言之，对于任何编程人员来说，基本的排序算法是必须要掌握的。
从今天开始，我们将要进行基本的排序算法的讲解。Are you ready？Let&s go~~~
1、排序算法的基本概念的讲解
&&&& 时间复杂度:需要排序的的关键字的比较次数和相应的移动的次数。
&&&& 空间复杂度:分析需要多少辅助的内存。
&&&& 稳定性:如果记录两个关键字的A和B它们的值相等，经过排序后它们相对的位置没有发生交换，那么我们称这个排序算法是稳定的。
&&&&&&&&&&&&& 否则我们称这个排序算法是不稳定的。
&&& 排序算法的常见分类:
&&& 1、内部排序（最常见的一种排序方式，不需要借助第三方辅助存储工具）
&&& 2、外部排序（需要借助外部存储来辅助完成相关的排序操作）
&&&&&&& 如果参与排序的数据元素非常的多，数据量非常的大，计算机无法把整个排序过程放到内存中进行的话，
&&&&&&& 我们必须借助外部存储器如磁盘来完成，这种排序方式，我们称之为外部排序。
&&&&&&& 其中外部排序最常见的就是多路归并排序，即将原始文件分解成多个能够一次性装入内存的部分，分别把每一部分调入
&&&&&&& 内存完成相应的排序，接下来在对多个有序的外部文件进行多路归并排序。
&& 对于我们绝大多数的程序员而言，我们经常遇到的为内部排序。接下来我们将要对常见的内部排序进行相应的讲解。
&&& 今天要讲解的内部排序为:
&& 归并排序
& 1.归并排序的基本概念的讲解
归并排序建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个
有序表，称为二路归并。
归并过程为：比较a[i]和a[j]的大小，若a[i]&a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；
否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将
另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以
中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如　设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8，1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11,；
逆序数为14；
& 2.归并排序的Java代码实现
package com.yonyou.
* 内部排序算法之归并排序
* 默认按照从小到大进行排序操作
* @author 小浩
* @创建日期
public class Test{
public static void main(String[] args) {
//需要进行排序的数组
int[] array=new int[]{8,3,2,1,7,4,6,5};
//输出原数组的内容
printResult(array);
//归并排序操作
sort(array,0,array.length-1);
//输出排序后的相关结果
printResult(array);
* 归并排序
* @param array
private static void sort(int[] array,int i,int j) {
int middle=(i+j)/2;
//递归处理相关的合并事项
sort(array,i,middle);
sort(array,middle+1,j);
merge(array,i,middle,j);
* 合并相关的数组内容
* 同时使合并后的数组仍然有序
* @param array
* @param i
* @param middle
* @param j
private static void merge(int[] array, int i, int middle, int j) {
//创建一个临时数组用来存储合并后的数据
int[] temp=new int[array.length];
int n=middle+1;
while(m&=middle&&n&=j)
if(array[m]&array[n])
temp[k++]=array[m++];
temp[k++]=array[n++];
//处理剩余未合并的部分
while(m&=middle)
temp[k++]=array[m++];
while(n&=j)
temp[k++]=array[n++];
//将临时数组中的内容存储到原数组中
while(i&=j)
array[i]=temp[i++];
* 输出相应数组的结果
* @param array
private static void printResult(int[] array) {
for(int value:array)
System.out.print(" "+value+" ");
System.out.println();
* 交换数组中两个变量的值
* @param array
* @param i
* @param j
private static void swap(int[] array,int i,int j){
int temp=array[i];
array[i]=array[j];
阅读(...) 评论()你的位置： >
> java常用的7大排序算法汇总
这段时间闲了下来，就抽了点时间总结了下java中常用的七大排序算法，希望以后可以回顾！
1.插入排序算法
插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的元素即 [0..i-1] 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ，并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置”，最后将 k 对应的元素值赋为 x ，一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1)。
* @param int[] 未排序数组
* @return int[] 排完序数组
public int[] sortInsert(int[] array){
for(int i=1;i&array.i++){
int temp = array[i];
for(j=i-1;j &= 0 && temp& array[j]; j--){
array[j + 1] = array[j];
array[j + 1] =
2.选择排序算法
选择排序的基本思想是遍历数组的过程中，以 i 代表当前需要排序的序号，则需要在剩余的 [i…n-1] 中找出其中的最小值，然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们形象地称之为选择排序。选择排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) 。
* @param int[] 未排序数组
* @return int[] 排完序数组
public int[] sortSelect(int[] arr){
for (int i = 0; i & arr. i++) {
int miniPost =
for (int m = i + 1; m & arr. m++) {
if (arr[m] & arr[miniPost]) {
miniPost =
if (arr[i] & arr[miniPost]) {
temp = arr[i];
arr[i] = arr[miniPost];
arr[miniPost] =
3.冒泡排序算法
冒泡排序是將比較大的數字沉在最下面，较小的浮在上面
* @param int[] 未排序数组
* @return int[] 排完序数组
public int[] sortBubble(int[] array){
// 第一层循环:表明比较的次数, 比如 length 个元素,比较次数为 length-1 次（肯定不需和自己比）
for(int i=0;i&array.length-1;i++){
for (int j = array.length - 1; j & j--) {
if (array[j] & array[j - 1]) {
temp = array[j];
array[j] = array[j - 1];
array[j - 1] =
4.快速排序算法
通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可以分别对这两部分记录继续进行排序,已达到整个序列有序的目的，本质就是,找一个基位(枢轴,分水岭,作用是左边的都比它小,右边的都比它大.可随机,取名base，首先从序列最右边开始找比base小的,如果小,换位置,从而base移到刚才右边(比较时比base小)的位置(记为临时的high位),这样base右边的都比base大。然后,从序列的最左边开始找比base大的，如果大,换位置,从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位),这样base左边的都比base小，循环以上两步,直到 low == heigh, 这使才真正的找到了枢轴,分水岭. 返回这个位置,分水岭左边和右边的序列,分别再来递归。
* @param int[] 未排序数组
* @return int[] 排完序数组
public int[] sortQuick(int[] array){
return quickSort(array, 0, array.length-1);
private int[] quickSort(int[] arr, int low, int heigh) {
if (low & heigh) {
int division = partition(arr, low, heigh);
quickSort(arr, low, division - 1);
quickSort(arr, division + 1, heigh);
// 分水岭,基位,左边的都比这个位置小,右边的都大
private int partition(int[] arr, int low, int heigh) {
int base = arr[low]; //用子表的第一个记录做枢轴(分水岭)记录
while (low & heigh) { //从表的两端交替向中间扫描
while (low & heigh && arr[heigh] &= base) {
// base 赋值给 当前 heigh 位,base 挪到(互换)到了这里,heigh位右边的都比base大
swap(arr, heigh, low);
while (low & heigh && arr[low] &= base) {
// 遇到左边比base值大的了,换位置
swap(arr, heigh, low);
// now low =
private void swap(int[] arr, int a, int b) {
temp = arr[a];
arr[a] = arr[b];
5.合并排序算法
归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间
* @param int[] 未排序数组
* @return int[] 排完序数组
private int[] sort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
if (low & high) {
sort(nums, low, mid);
sort(nums, mid + 1, high);
// 左右归并
merge(nums, low, mid, high);
private void merge(int[] nums, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i =// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i &= mid && j &= high) {
if (nums[i] & nums[j]) {
temp[k++] = nums[i++];
temp[k++] = nums[j++];
// 把左边剩余的数移入数组
while (i &= mid) {
temp[k++] = nums[i++];
// 把右边边剩余的数移入数组
while (j &= high) {
temp[k++] = nums[j++];
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 & temp. k2++) {
nums[k2 + low] = temp[k2];
public int[] sortMerge(int[] array) {
return sort(array, 0, array.length - 1);
6.希尔排序算法
希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”，划分为若干个小的数组，以 gap 来划分，比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ，如果以 gap = 2 来划分，可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组（对应的，如 gap = 3 ， 则划分的数组为： [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] ）然后分别对划分出来的数组进行插入排序，待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤，直至 gap = 1 ，即对整个数组进行插入排序，此时的数组已经基本上快排好序了，所以需要移动的元素会很小很小，解决了插入排序在处理大规模数组时较多移动次数的问题，
希尔排序是插入排序的改进版，在数据量大的时候对效率的提升帮助很大，数据量小的时候建议直接使用插入排序就好了。
* @param int[] 未排序数组
* @return int[] 排完序数组
public int[] sortShell(int[] array) {
int step = array.length / 2;
while (step &= 1) {
for (int i = i & array. i++) {
int temp = array[i];
int j = 0;
// 跟插入排序的区别就在这里
for (j = i - j &= 0 && temp & array[j]; j -= step) {
array[j + step] = array[j];
array[j + step] =
step /= 2;
7.堆排序算法
本质就是先构造一个大顶堆,parent比children大,root节点就是最大的节点 把最大的节点(root)与尾节点(最后一个节点,比较小)位置互换，剩下最后的尾节点,现在最大,其余的,从第一个元素开始到尾节点前一位,构造大顶堆递归。
* @param int[] 未排序数组
* @return int[] 排完序数组
public int[] sortHeap(int[] array) {
buildHeap(array);// 构建堆
int n = array.
int i = 0;
for (i = n - 1; i &= 1; i--) {
swap(array, 0, i);
heapify(array, 0, i);
private void buildHeap(int[] array) {
int n = array.// 数组中元素的个数
for (int i = n / 2 - 1; i &= 0; i--)
heapify(array, i, n);
private void heapify(int[] A, int idx, int max) {
int left = 2 * idx + 1;// 左孩子的下标（如果存在的话）
int right = 2 * idx + 2;// 左孩子的下标（如果存在的话）
int largest = 0;// 寻找3个节点中最大值节点的下标
if (left & max && A[left] & A[idx])
if (right & max && A[right] & A[largest])
if (largest != idx) {
swap(A, largest, idx);
heapify(A, largest, max);
// 建堆函数，认为【s，m】中只有 s
// 对应的关键字未满足大顶堆定义，通过调整使【s，m】成为大顶堆=====================================================
public static void heapAdjust(int[] array, int s, int m) {
// 用0下标元素作为暂存单元
array[0] = array[s];
// 沿孩子较大的结点向下筛选
for (int j = 2 * j &= j *= 2) {
// 保证j为较大孩子结点的下标，j & m 保证 j+1 &= m ，不越界
if (j & m && array[j] & array[j + 1]) {
if (!(array[0] & array[j])) {
// 若S位较小，应将较大孩子上移
array[s] = array[j];
// 较大孩子的值变成S位的较小值，可能引起顶堆的不平衡，故对其所在的堆进行筛选
// 若S位较大，则值不变；否则，S位向下移动至2*s、4*s、。。。
array[s] = array[0];
转载请注明： &
与本文相关的文章java编程合并排序算法_百度知道
java编程合并排序算法
代码知何故排结求高指点（估计merge函数）public static void main(String[] args)
Integer arr[]={25,2,4,13,6};
Integer tmpArry[]=new Integer[5];
Mergesort mg=new Mergesort();
mg.mergesort(arr, tmpArry, 0, 4);//len-1);
mg.show(tmpArry); }class Mergesort { public &T extends Comparable&? super T&&
void mergesort(T[] a,T[]tmpArry,int left,int right) {
if(left&right)
int center=(left+right)/2;
mergesort(a,tmpArry,left,center);
mergesort(a,tmpArry,center+1,right);
merge(a,tmpArry,left,center+1,right);
public &T extends Comparable&? super T&&
void merge(T[] a,T[]tmpArry,int leftPos,int rightPos,int rightEnd) {
int leftEnd=rightPos-1;
int tmpPos=leftP
//int numElements=rightEnd-leftPos+1;
while(leftPos &=leftEnd && rightPos &=rightEnd)
if(a[leftPos].compareTo(a[rightPos])&=0)
tmpArry[tmpPos++]=a[leftPos++];
tmpArry[tmpPos++]=a[rightPos++];
while(leftPos&=leftEnd)
tmpArry[tmpPos++]=a[leftPos++];
while(rightPos&=rightEnd)
tmpArry[tmpPos++]=a[rightPos++];
} public &T extends Comparable&? super T&&
void show(T tmpArry[])
for(int i=0;i&tmpArry.i++){
System.out.println(&after Mergesort the tmpArry&+i+& is&+tmpArry[i]);
提问者采纳
package&p1;import&java.util.Apublic&class&Guy{ /** &*&归并排序 &*/ private&static&void&mergeSort&(&int[]&array,&int&start,&int&end,&int[]&tempArray&) {
if&(end&&=&start)
int&middle&=&(&start&+&end&)&/&2;
mergeSort&(array,&start,&middle,&tempArray);
mergeSort&(array,&middle&+&1,&end,&tempArray);
int&k&=&0,&leftIndex&=&0,&rightIndex&=&end&-&
System.arraycopy&(array,&start,&tempArray,&0,&middle&-&start&+&1);
for&(&int&i&=&0;&i&&&end&-&&i++&)
tempArray[end&-&start&-&i]&=&array[middle&+&i&+&1];
while&(k&&&end&-&start&+&1)
if&(tempArray[rightIndex]&&&tempArray[leftIndex])&//&
array[k&+&start]&=&tempArray[leftIndex++];
array[k&+&start]&=&tempArray[rightIndex--];
} } public&static&void&main&(&String[]&args&) {
int[]&array&=&new&int[]&{&11,&213,&134,&65,&77,&78,&23,&43&};
mergeSort&(array,&0,&array.length&-&1,&new&int[array.length]);
System.out.println&(Arrays.toString&(array)); }}
你的代码写的很好，能不能麻烦修改下我的代码，我想了好久也没发现问题所在
你的方法好多啊，我看不太懂啊
提问者评价
太给力了，你的回答完美地解决了我的问题，非常感谢！
其他类似问题
为您推荐：
java编程的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁二次元同好交流新大陆
扫码下载App
汇聚2000万达人的兴趣社区下载即送20张免费照片冲印
扫码下载App
温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(1356)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
在LOFTER的更多文章
loftPermalink:'',
id:'fks_',
blogTitle:'java归并排序算法',
blogAbstract:'&&&&& 归并排序的时间复杂度是：nlogn\r\n&&&&&& 主要是用到二路归并排序，也就是把两个有序集合合并为一个有序集合。\r\n&&&& 下面是我写的一个递归二路归并排序的算法：\r\n&&\r\npublic class MergeSort {&// private static long sum = 0;\r\n&/**& * &pre&& * 二路归并& * 原理：将两个有序表合并和一个有序表& * &/pre&& * & * @param a& * @param s& *&&&&&&&&&&& 第一个有序表的起始下标& * @param m& *&',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:2,
publishTime:8,
permalink:'blog/static/',
commentCount:0,
mainCommentCount:0,
recommendCount:0,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'',
hmcon:'1',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}}