网站平台多少钱,西部数码wordpress,郑州市科协网站,高端网页制作公司哪家好图解 归并排序是一种效率比较高的分治排序算法#xff0c;主要分为两个步骤#xff0c;分别为“分”和“并”。 分#xff1a;将序列不断二分#xff0c;直到每个子序列只有一个元素为止。 并#xff1a;将相邻两个子序列进行合并#xff0c;合并时比较两个子序列的元素… 图解 归并排序是一种效率比较高的分治排序算法主要分为两个步骤分别为“分”和“并”。 分将序列不断二分直到每个子序列只有一个元素为止。 并将相邻两个子序列进行合并合并时比较两个子序列的元素大小按照从小到大的顺序放入新的序列中。 是一种分治算法在每轮排序中将待排序数组分成两部分递归地将每个子数组排序最后将两个排好序的子数组合并成一个有序数组。
具体实现如下 将待排序数组分成两个子数组每个子数组包含原数组的一半元素如果原数组长度为奇数则一个子数组比另一个多一个元素。 递归地对每个子数组进行归并排序直到子数组长度为1。 合并两个排好序的子数组。将两个子数组中的最小元素依次比较将较小的元素放入新数组中直到其中一个子数组的元素全部被放入新数组中此时将另一个子数组中的剩余元素直接放到新数组的尾部。 返回合并后的有序数组。
归并排序的时间复杂度为O(nlogn)空间复杂度为O(n)。它是一种稳定的排序算法适用于各种数据类型的排序。
以下是Java实现归并排序的代码
public class MergeSort {public static void mergeSort(int[] arr, int left, int right) {if (left right) {return;}int mid (left right) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid 1, right);merge(arr, left, mid, right);}private static void merge(int[] arr, int left, int mid, int right) {// 创建一个临时数组存放排序后的元素int[] temp new int[right - left 1];int i left;int j mid 1;int k 0;while (i mid j right) {if (arr[i] arr[j]) {temp[k] arr[i];} else {temp[k] arr[j];}}while (i mid) {temp[k] arr[i];}while (j right) {temp[k] arr[j];}// 将排序后的元素拷贝回原数组for (int p 0; p temp.length; p) {arr[left p] temp[p];}}public static void main(String[] args) {int[] arr {5, 3, 8, 4, 2, 1, 10, 7};mergeSort(arr, 0, arr.length - 1);for (int i : arr) {System.out.print(i );}}
}输出结果为1 2 3 4 5 7 8 10
