广州正规网站制作公司,杭州的设计网站建设,深圳4a广告公司,网站成功案例归并排序
1945年#xff0c;约翰冯诺依曼#xff08;John von Neumann#xff09;发明了归并排序#xff0c;这是典型的分治算法的应用。归并排序#xff08;Merge sort#xff09;是建立在归并操作上的一种有效的排序算法#xff0c;该算法是采用分治法#xff08;Di…归并排序
1945年约翰·冯·诺依曼John von Neumann发明了归并排序这是典型的分治算法的应用。归并排序Merge sort是建立在归并操作上的一种有效的排序算法该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。
基本思想
归并排序是使用分治算法就是把序列分成长度相同的两个子序列当无法继续往下分时也就是每个子序列中只有一个数据时就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行直到所有子序列都归并为一个整体为止。
图形演示
为方便查看我们用不同高度来表示不同的数字大小 首先我们把序列逐层对半分割
直至不能再分割为止
分割完毕接下来对每组元素进行合并合并时需要将数字按照从小到大的顺序排列
每次合并时比较两个子序列的首位数字。当合并有多个数字的子序列时要先比较首位数字再移动较小的数字由于34,所以要先移动3接下来再比较4和747所以移动4再比较6和7…如此往复左半个序列就排序好啦
右边也是如此直至所有的数字都合并为一个整体为止
合并完成序列的排序也就完成了
时间复杂度分析
归并排序中分割序列所花费的时间不算在运行时间内可以当作序列本来就是分 割好的。在合并两个已排好序的子序列时只需重复比较首位数据的大小然后移动较 小的数据因此只需花费和两个子序列的长度相应的运行时间。也就是说完成一行归 并所需的运行时间取决于这一行的数据量。 看一下上面的图便能得知无论哪一行都是 n 个数据所以每行的运行时间都为 O(n)。 而将长度为 n 的序列对半分割直到只有一个数据为止时可以分成 log2n 行因此总 共有 log2n 行。也就是说总的运行时间为 O(nlogn)这与前面讲到的堆排序相同。
代码实现
迭代法
public static void merge_sort(int[] arr) {int len arr.length;int[] result new int[len];int block, start;for(block 1; block len*2; block * 2) {for(start 0; start len; start 2 * block) {int low start;int mid (start block) len ? (start block) : len;int high (start 2 * block) len ? (start 2 * block) : len;int start1 low, end1 mid;int start2 mid, end2 high;while (start1 end1 start2 end2) {result[low] arr[start1] arr[start2] ? arr[start1] : arr[start2];}while(start1 end1) {result[low] arr[start1];}while(start2 end2) {result[low] arr[start2];}}int[] temp arr;arr result;result temp;}result arr;
}递归法
static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {if (start end)return;int len end - start, mid (len 1) start;int start1 start, end1 mid;int start2 mid 1, end2 end;merge_sort_recursive(arr, result, start1, end1);merge_sort_recursive(arr, result, start2, end2);int k start;while (start1 end1 start2 end2)result[k] arr[start1] arr[start2] ? arr[start1] : arr[start2];while (start1 end1)result[k] arr[start1];while (start2 end2)result[k] arr[start2];for (k start; k end; k)arr[k] result[k];
}public static void merge_sort(int[] arr) {int len arr.length;int[] result new int[len];merge_sort_recursive(arr, result, 0, len - 1);
}总结
归并排序与选择排序一样性能不受输入数据的影响但时间复杂度远小于选择排序。但由于归并排序需要另外一个与原数组长度相同的数组来做辅助排序需要占用额外的空间空间复杂度为O(n)
参考资料《我的第一本算法书》
