亿行代码
java实现归并排序（Mergesort）
引言
3.29
简介
归并排序（MERGESORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序的时间复杂度是O(nlogn）， 空间复杂度是O(n)。是稳定的排序。
归并排序的思路流程是：
第一步、将待排序数列中的数字分为若干组，每个数字分成一组，即如果数列中8个数字，就分成8组。
第二步、将这些组两两合并，保证合并之后的数列是有序的。
第三步、重复第二步操作，直到只剩下一组，即排序完成。
看文字理解可能有点云里雾里，接下来我们用图来解释下这个过程。
3.29
图解流程
3.29
代码实现
Java：
import java.util.Arrays;public class MergeSort {public static void main(String[] args) {int[] arr = {2,3,4,1,5,7,8,6};System.out.println(Arrays.toString(arr));mergeSort(arr,0, arr.length-1);System.out.println(Arrays.toString(arr));}/**** @param arr //待排序数组* @param low //左边标识* @param high //右边标识*/public static void mergeSort(int[] arr,int low,int high){if(low >= high){return;}int mid = (low +high) >>> 1;mergeSort(arr,low,mid);mergeSort(arr,mid+1,high);//合并merge(arr, low, mid, high);}private static void merge(int[] arr, int low, int mid, int high) {int s1 = low; //第一个归并段开始int s2 = mid+1 ;//第二个归并段开始//临时数组int[] ret = new int[high-low +1];int i = 0; //ret数组的下标//归并段有数据while (s1 <= mid && s2 <=high ){//s1和s2数据比较if(arr[s1] <= arr[s2]){ret[i++] = arr[s1++];}else {ret[i++] = arr[s2++];}}//跳出循环while (s1 <= mid){ret[i++] = arr[s1++];}while (s2 <= high){ret[i++] = arr[s2++];}for (int j = 0; j < ret.length ; j++) {arr[j+low]= ret[j];}}}
C++:
template<typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能void merge_sort(T arr[], int len) {T *a = arr;T *b = new T[len];for (int seg = 1; seg < len; seg += seg) {for (int start = 0; start < len; start += seg + seg) {int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);int k = low;int start1 = low, end1 = mid;int start2 = mid, end2 = high;while (start1 < end1 && start2 < end2)b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];while (start1 < end1)b[k++] = a[start1++];while (start2 < end2)b[k++] = a[start2++];}T *temp = a;a = b;b = temp;}if (a != arr) {for (int i = 0; i < len; i++)b[i] = a[i];b = a;}delete[] b;}
如果该文章对你有帮助，"再看"和"点赞"是对我最大的鼓励！
扫二维码｜关注我们
谢谢观看
把城市夜晚的喧嚣，点出来
▼
