数据结构(十一):归并排序

2018-03-01 11:15:55来源:https://www.jianshu.com/p/1b279dab927f作者:林塬人点击

分享



利用递归与分治技术将数据序列划分成越来越小的半子表,在对半子表排序,最后再用递归方法将排好序的半子表合并成越来越大的有序序列
直接插入排序例子

流程:


分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素
治理: 对每个子序列分别调用归并排序 MergeSort
合并: 合并两个排好序的子序列,生成排序结果

举例:数组 int[] arr= { 50,10,90,30,70,40,80,60,20 };




归并排序

直接插入排序代码
public static void main(String[] args) {
int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};
int[] temp = new int[arr.length];
mergeSort(arr, temp, 0, arr.length - 1);
System.out.println(Arrays.toString(temp));
}
public static void mergeSort(int[] a, int[] tmp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(a, tmp, left, mid); // 左排序
mergeSort(a, tmp, mid + 1, right); // 右排序
merge(a, tmp, left, mid + 1, right); // 左右合并
}
}
public static void merge(int[] a, int[] tmp, int left, int rightPos, int right) {
int leftEnd = rightPos - 1;
int tmpPos = left;
int num = right - left + 1;
while (left <= leftEnd && rightPos <= right) {
if (a[left] < a[rightPos]) {
tmp[tmpPos++] = a[left++];
} else {
tmp[tmpPos++] = a[rightPos++];
}
}
while (left <= leftEnd) {
tmp[tmpPos++] = a[left++];
}
while (rightPos <= right) {
tmp[tmpPos++] = a[rightPos++];
}
for (int i = 0; i < num; i++, right--) {
a[right] = tmp[right];
}
}

归并排序性能
归并排序是一种稳定的排序
归并排序利用了完全二叉树深度是 log₂ⁿ+1 的特性,因此效率较高
一趟归并需要将数组 a[] 中相邻的长度为 h 的有序序列进行两两归并.并将结果放到 temp[] 中,这需要将待排序列中的所有记录扫描一遍,因此耗费O(n)
而完全二叉树的深度可知,整个归并排序需要进行 log₂ⁿ 次,因此总的时间复杂度为 O(nlogn),而且这是归并排序算法中最好、最坏、平均的时间性能
需要一个辅助向量来暂存两有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序







最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台