排序篇（6）--归并排序

2019-11-06 07:55:35

字体：大中小

来源：转载

供稿：网友

“归并”在数据结构中定义为：将两个或两个以上的有序数表组合成一个新的有序表。

一、归并排序

基本思想：利用归并的思想，假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并,得到n/2个长度为2或1的有序子序列，再两两归并….，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为“2路归并法”。

二、归并排序算法

采用递归的方式

package Sort;/** * Created by L_kanglin on 2017/3/3. */public class TestMergingSort { public static void main(String[] args){ int[] adj = new int[]{9,1,5,8,3,7,4,6,2}; PRint(adj); mergeSort(adj); System.out.println(); System.out.println("归并排序后的数组"); print(adj); } public static void mergeSort(int[] data){ sortTest(data,0,data.length-1); } public static void sortTest(int[] data,int left,int right){ if(left>=right){ return; } //找出中间的索引 int center= (left + right)/2; //对左边数组进行递归 sortTest(data,left,center); //对右边数组进行递归 sortTest(data,center+1,right); //合并 mergeTest(data,left,center,right); } /* * data :数组对象 * left：左数组的第一个元素的索引 * center：左数组的最后一个元素的索引，center+1是右数组第一个元素的索引 * right ：右数组最后一个元素的索引 * */ public static void mergeTest(int[] data, int left, int center, int right) { // 临时数组 int[] tmpArr = new int[data.length]; // 右数组第一个元素索引 int mid = center + 1; // third 记录临时数组的索引 int third = left; // 缓存左数组第一个元素的索引 int tmp = left; while (left <= center && mid <= right) { // 从两个数组中取出最小的放入临时数组 if (data[left] <= data[mid]) { tmpArr[third++] = data[left++]; } else { tmpArr[third++] = data[mid++]; } } while (mid <= right) { tmpArr[third++] = data[mid++]; } while (left <= center) { tmpArr[third++] = data[left++]; } // 将临时数组中的内容拷贝回原数组中 // （原left-right范围的内容被复制回原数组） while (tmp <= right) { data[tmp] = tmpArr[tmp++]; } } public static void print(int[] data) { for (int i = 0; i < data.length; i++) { System.out.print(data[i] + "/t"); } }}

运行结果如下：

9 1 5 8 3 7 4 6 2 归并排序后的数组1 2 3 4 5 6 7 8 9