基本思想:
归并排序利用分治法,先将一个序列分成一个个子序列,然后对子序列进行排序,再把有序子序列合并为整体有序序列。
图片来自于http://www.cnblogs.com/shudonghe/p/3302888.html
Java代码实现:
public class GuiBing {
public static void main(String[] args) {
int[] a = { 14, 12, 15, 13, 11, 16 };
sort(a, 0, a.length-1);
}
//使用递归算法
public static void sort(int[] a, int left, int right) {
if (left >= right)
return;
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 = left; // index记录临时数组的索引
int tmp = left;
// 从两个数组中取出最小的放入中临时数组
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 = tmp; i <= right; i++) {
data[i] = tmpArr[i];
}
System.out.println(Arrays.toString(data));
}
}
算法性能分析:
时间复杂度:最坏最好和平均时间复杂度均为O(nlogn)
空间复杂度:归并排序需要一个大小为n的临时存储空间用以保存合并序列,所以空间复杂度为O(n)
算法稳定性:在归并排序中,相等的元素的顺序不会改变,所以它是稳定的算法。