/** * 归并排序 * <ul> * <li>平均情况:O(nlog(2)n)</li> * <li>最好情况:O(nlog(2)n)</li> * <li>最坏情况:O(nlog(2)n)</li> * <li>辅助存储:O(n)</li> * <li>稳定</li> * <ul> * * @timestamp Mar 12, 2016 6:29:11 PM * @author smallbug */ public class MergeSort { public static void main(String[] args) { int[] data = DataUtil.getData(100000); // System.out.println(Arrays.toString(data)); long time = System.currentTimeMillis(); mergeSort(data); // System.out.println(Arrays.toString(data)); System.out.println("speed " + (System.currentTimeMillis() - time) + " ms"); System.out.println("排序是否成功:" + (DataUtil.verify(data, DataUtil.ASC) ? "是" : "否")); } private static void mergeSort(int[] data) { sort(data, 0, data.length - 1); } public static void sort(int[] data, int left, int right) { if (left >= right) return; // 找出中间索引 int center = (left + right) >>> 1; // 对左边数组进行递归 sort(data, left, center); // 对右边数组进行递归 sort(data, center + 1, right); // 合并 merge(data, left, right); } public static void merge(int[] data, int left, int right) { insertSort(data, left, right); } /** * 局部插入排序 * * @timestamp Mar 12, 2016 6:28:30 PM * @param data * @param left * @param right */ private static void insertSort(int[] data, int left, int right) { int temp; for (int i = left + 1; i <= right; i++) { temp = data[i];// 保存待插入的数值 int j = i; for (; j > 0 && temp < data[j - 1]; j--) { data[j] = data[j - 1];// 如果待插入的数值前面的元素比该值大,就向后移动一位 } data[j] = temp;// 插入 } } }
相关推荐
归并排序是一种高效的排序算法,基于分治策略。在Java中实现归并排序,我们可以创建一个名为`MergeSort`的类来封装整个过程。归并排序的基本思想是将待排序的序列分成两个或更多的子序列,对每个子序列分别进行排序...
【归并排序】是一种高效的排序算法,其基本思想源于分治法(Divide and Conquer)。归并排序通过不断地将数组划分为较小的子序列,然后对这些子序列进行排序,最后将排序好的子序列合并成一个完整的有序序列。在这个...
### 归并排序算法实现详解 #### 一、引言 归并排序是一种经典的排序算法,采用分治法的思想,将待排序数组分为若干个子序列,这些子序列是已排序的,然后再按照一定的方式合并这些子序列得到最终排序后的数组。...
C#排序算法之归并排序 C#排序算法之归并排序是一种基于分治策略的排序算法,通过将数组分割成两个子数组,递归地对每个子数组进行排序,然后将两个有序的子数组合并成一个有序的数组。下面是对C#实现归并排序的详细...
本文实例为大家分享了C语言实现归并排序的具体代码,供大家参考,具体内容如下 归并排序的基本思想: 将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治法分为若干个有序子序列,然后每两个子序列合并...
归并排序是一种高效的、稳定的排序算法,其核心思想是“分而治之”。在Python中实现归并排序,我们可以分为以下几个步骤来理解: 1. **分割**:首先,我们需要将原始数组不断地分成两半,直到每个子数组只剩下一个...
归并排序是一种高效的排序算法,基于分治策略。在C#中,归并排序可以通过递归、非递归以及自然归并三种方式实现。以下是这三种实现方法的详细解释: 1. **递归归并排序**: 递归归并排序是归并排序最直观的实现...
归并排序(Merge Sort)是一种基于分治策略的高效排序算法。它的基本思想是将待排序的序列分为两部分,分别对这两部分进行排序,然后将排好序的子序列合并成一个完整的有序序列。这一过程可以递归地进行,直到每个子...
**三路归并排序**是一种高效的排序算法,尤其在处理含有大量重复元素的序列时表现优秀。该算法基于归并排序的思想,但将其分为三个部分处理,而不是传统的两个部分。在本文中,我们将深入探讨三路归并排序的原理、...
归并排序是一种分治策略的排序算法,它的基本思想是将大问题分解成小问题来解决。在归并排序中,我们将一个大数组分成两个或更多个小数组,然后对每个小数组进行排序,最后将这些小数组合并成一个大的有序数组。这个...
归并排序是一种基于分治策略的高效排序算法,它的核心思想是将大问题分解成小问题,然后分别解决小问题,最后将小问题的结果合并,得到大问题的解。在这个过程中,归并排序将待排序的序列不断地分成两半,直到每个子...
归并排序是一种基于分治策略的高效排序算法,它的核心思想是将大问题分解成小问题,逐个解决,然后再将结果合并,最终得到整个问题的解决方案。在归并排序中,这一过程主要分为三个步骤:分解、求解和组合。 1. **...
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"...
归并排序(Merge Sort)是一种经典的分治算法,它将一个数组分成两个子数组,分别对这两个子数组进行排序,然后再将两个已排序的子数组合并成一个完整的有序数组。压缩包文件代码是一个使用JavaScript实现归并排序的...
1,归并排序的概念 1.1,算法介绍 和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度。代价是需要额外的内存空间。归并排序是建立在归并操作上的一...
归并排序(Merge Sort)是一种基于分治策略的高效排序算法。它的基本思想是将待排序的元素序列分成两个或更多的子序列,分别对每个子序列进行排序,然后将排好序的子序列合并成一个有序序列。这个过程可以递归进行,...
归并排序是一种基于分治思想的高效排序算法,它的主要特点是将大问题分解为小问题来解决。在Java中实现归并排序,我们可以分别实现递归版和非递归版,这两种方法各有其特点和适用场景。 ### 1. 分治策略 归并排序...
内部排序之归并排序的代码实现,代码风格简单 易于看懂
本文将详细介绍C++中实现的希尔排序、快速排序、堆排序和归并排序这四种经典排序算法。 希尔排序,由Donald Shell于1959年提出,是一种改进的插入排序。它的基本思想是通过设置一个增量序列,将待排序的元素按照...