归并排序
归并排序概述排序原理排序图解代码实现具体实现合并的图解代码实现
时间复杂度分析
归并排序概述
归并排序是建立在归并操作上一种有效的排序算法，该算法采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
排序原理
排序原理:
尽可能的将一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组 的元素个数是1为止。将相邻的两个子组进行合并成一个有序的大组。不断的重复步骤2，直到最终只有一个组为止。
排序图解
{8,4,5,7,1,3,6,2}进行从小到大排序
代码实现
实现的api:
public static boolean greater( int a,int b) 比较a与b的大小，返回true/falsepublic static void exch(int[] a,int i,int j) 交换索引i处和索引j处的值的位置public static void sort(int[] a) 对数组a进行排序public static void sort(int[] a,int lo,int hi) 对数组指定索引lo到指定索引hi处的值进行排序public static void merge(int[] a,int lo,int mid,int hi) 将索引lo到索引mid的数组和索引mid+1到索引hi的数组合并成一个数组
具体实现合并的图解
代码实现
import java
. util
.Arrays
;
public class SortMerge {
private static int[] help
;
public static void main(String
[] args
) {
int[] array
=new int[]{8,4,5,7,1,3,6,2};
sort(array
);
System
. out
. println(Arrays
. toString(array
));
}
public static boolean greater( int a
,int b
){
return a
>b
;
}
public static void exch(int[] a
,int i
,int j
){
int temp
=a
[i
];
a
[i
]=a
[j
];
a
[j
]=temp
;
}
public static void sort(int[] a
){
help
=new int[a
. length
];
int lo
=0;
int hi
=a
.length
-1;
sort(a
,lo
,hi
);
}
public static void sort(int[] a
,int lo
,int hi
){
if(hi
<=lo
){
return;
}
int mid
=(lo
+hi
)/2;
sort(a
,lo
,mid
);
sort(a
,mid
+1,hi
);
merge(a
,lo
,mid
,hi
);
}
public static void merge(int[] a
,int lo
,int mid
,int hi
){
int i
=lo
;
int p1
=lo
;
int p2
=mid
+1;
while(p1
<=mid
&& p2
<=hi
){
if(greater(a
[p1
],a
[p2
])){
help
[i
++]=a
[p2
++];
}else{
help
[i
++]=a
[p1
++];
}
}
while(p1
<=mid
){
help
[i
++]=a
[p1
++];
}
while(p2
<=hi
){
help
[i
++]=a
[p2
++];
}
for(int index
=lo
;index
<=hi
;index
++){
a
[index
]=help
[index
];
}
}
}
时间复杂度分析
时间复杂度为O(nlogn) 缺点就是，需要申请额外的空间数组，当待排序的数量较多时，会导致空间复杂度复杂
