时代Java，与您同行！关注微信公众号，关注前沿技术，微信搜索：nowjava或时代Java，也可点击这里扫码关注

时代Java

Java 使用合并排序对数组排序。

欢马劈雪

工程师 (已认证)

原创分享签约作者

发表于实例源码

463

使用合并排序对数组排序。

实例源码：

源代码：

执行

执行中...

import java.security.SecureRandom;

import java.util.Arrays;

/**
时 代 J a v a 公 众 号 - N o w J a v  a . c o m
**/

public class Main

{

// calls recursive split method to begin merge sorting

public static void mergeSort(int[] data)

{

sortArray(data, 0, data.length - 1); // sort entire array

}

// splits array, sorts subarrays and merges subarrays into sorted array

private static void sortArray(int[] data, int low, int high) /** from 时代Java公众号 - nowjava.com**/

{

// test base case; size of array equals 1

if ((high - low) >= 1) // if not base case

{

int middle1 = (low + high) / 2; // calculate middle of array

int middle2 = middle1 + 1; // calculate next element over

// output split step

System.out.printf("split:   %s%n", subarrayString(data, low, high));

System.out.printf("         %s%n", subarrayString(data, low, middle1));

System.out.printf("         %s%n%n",subarrayString(data, middle2, high));

// split array in half; sort each half (recursive calls)

sortArray(data, low, middle1); // first half of array

sortArray(data, middle2, high); // second half of array

// merge two sorted arrays after split calls return

merge (data, low, middle1, middle2, high);

}

// merge two sorted subarrays into one sorted subarray

private static void merge(int[] data, int left, int middle1, int middle2, int right){

int leftIndex = left; // index into left subarray

int rightIndex = middle2; // index into right subarray

int combinedIndex = left; // index into temporary working array

int[] combined = new int[data.length]; // working array

// output two subarrays before merging

System.out.printf("merge:   %s%n", subarrayString(data, left, middle1));

System.out.printf("         %s%n", subarrayString(data, middle2, right));

// merge arrays until reaching end of either

while (leftIndex <= middle1 && rightIndex <= right)

{

// place smaller of two current elements into result

// and move to next space in arrays

if (data[leftIndex] <= data[rightIndex])

combined[combinedIndex++] = data[leftIndex++];

else

combined[combinedIndex++] = data[rightIndex++];

}

// if left array is empty

if (leftIndex == middle2)

// copy in rest of right array

while (rightIndex <= right)

combined[combinedIndex++] = data[rightIndex++];

else // right array is empty

// copy in rest of left array

while (leftIndex <= middle1)

combined[combinedIndex++] = data[leftIndex++];

// copy values back into original array

for (int i = left; i <= right; i++)

data[i] = combined[i];

// output merged array

System.out.printf("         %s%n%n",

subarrayString(data, left, right));

}

// method to output certain values in array

private static String subarrayString(int[] data, int low, int high)

{

StringBuilder temporary = new StringBuilder();

// output spaces for alignment

for (int i = 0; i < low; i++)

temporary.append("   ");

/**代码未完, 请加载全部代码(NowJava.com).**/

编辑/阅读全部代码

执行结果：

<li>Unsorted array:</li>
<li>[54, 20, 14, 99, 71, 96, 52, 56, 67, 86]</li>
<li></li>
<li>split:    54 20 14 99 71 96 52 56 67 86</li>
<li>          54 20 14 99 71</li>
<li>                         96 52 56 67 86</li>
<li></li>
<li>split:    54 20 14 99 71</li>
<li>          54 20 14</li>
<li>                   99 71</li>
<li></li>
<li>split:    54 20 14</li>
<li>          54 20</li>
<li>                14</li>
<li></li>
<li>split:    54 20</li>
<li>          54</li>
<li>             20</li>
<li></li>
<li>merge:    54</li>
<li>             20</li>
<li>          20 54</li>
<li></li>
<li>merge:    20 54</li>
<li>                14</li>
<li>          14 20 54</li>
<li></li>
<li>split:             99 71</li>
<li>                   99</li>
<li>                      71</li>
<li></li>
<li>merge:             99</li>
<li>                      71</li>
<li>                   71 99</li>
<li></li>
<li>merge:    14 20 54</li>
<li>                   71 99</li>
<li>          14 20 54 71 99</li>
<li></li>
<li>split:                   96 52 56 67 86</li>
<li>                         96 52 56</li>
<li>                                  67 86</li>
<li></li>
<li>split:                   96 52 56</li>
<li>                         96 52</li>
<li>                               56</li>
<li></li>
<li>split:                   96 52</li>
<li>                         96</li>
<li>                            52</li>
<li></li>
<li>merge:                   96</li>
<li>                            52</li>
<li>                         52 96</li>
<li></li>
<li>merge:                   52 96</li>
<li>                               56</li>
<li>                         52 56 96</li>
<li></li>
<li>split:                            67 86</li>
<li>                                  67</li>
<li>                                     86</li>
<li></li>
<li>merge:                            67</li>
<li>                                     86</li>
<li>                                  67 86</li>
<li></li>
<li>merge:                   52 56 96</li>
<li>                                  67 86</li>
<li>                         52 56 67 86 96</li>
<li></li>
<li>merge:    14 20 54 71 99</li>
<li>                         52 56 67 86 96</li>
<li>          14 20 52 54 56 67 71 86 96 99</li>
<li></li>
<li>Sorted array:</li>
<li>[14, 20, 52, 54, 56, 67, 71, 86, 96, 99]</li>
<li></li>

本文系作者在时代Java发表，未经许可，不得转载。如有侵权，请联系nowjava@qq.com删除。

编辑于 2020-03-26 09:23:272020-03-26 09:23:27

实例源码

实例源码订阅