归并排序算法--java

  1 package com.zc.manythread;
  2 
  3 import java.util.Random;
  4 /**
  5  * 归并排序
  6  * @author 偶my耶
  7  *
  8  */
  9 public class MergeSort {
 10 
 11     public static void mergeSort(int[] data) {
 12         sort(data, 0, data.length - 1);
 13     }
 14 
 15     public static void sort(int[] data, int left, int right) {
 16         if (left >= right)
 17             return;
 18         // 找出中间索引
 19         int center = (left + right) / 2;
 20         // 对左边数组进行递归
 21         sort(data, left, center);
 22         // 对右边数组进行递归
 23         sort(data, center + 1, right);
 24         // 合并
 25         merge(data, left, center, right);
 26         print(data);
 27     }
 28 
 29     /**
 30      * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序
 31      * 
 32      * @param data
 33      *            数组对象
 34      * @param left
 35      *            左数组的第一个元素的索引
 36      * @param center
 37      *            左数组的最后一个元素的索引，center+1是右数组第一个元素的索引
 38      * @param right
 39      *            右数组最后一个元素的索引
 40      */
 41     public static void merge(int[] data, int left, int center, int right) {
 42         // 临时数组
 43         int[] tmpArr = new int[data.length];
 44         // 右数组第一个元素索引
 45         int mid = center + 1;
 46         // third 记录临时数组的索引
 47         int third = left;
 48         // 缓存左数组第一个元素的索引
 49         int tmp = left;
 50         while (left <= center && mid <= right) {
 51             // 从两个数组中取出最小的放入临时数组
 52             if (data[left] <= data[mid]) {
 53                 tmpArr[third++] = data[left++];
 54             } else {
 55                 tmpArr[third++] = data[mid++];
 56             }
 57         }
 58         // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
 59         while (mid <= right) {
 60             tmpArr[third++] = data[mid++];
 61         }
 62         while (left <= center) {
 63             tmpArr[third++] = data[left++];
 64         }
 65         // 将临时数组中的内容拷贝回原数组中
 66         // （原left-right范围的内容被复制回原数组）
 67         while (tmp <= right) {
 68             data[tmp] = tmpArr[tmp++];
 69         }
 70     }
 71 
 72     public static void print(int[] data) {
 73         for (int i = 0; i < data.length; i++) {
 74             System.out.print(data[i] + "\t");
 75         }
 76         System.out.println();
 77     }
 78     /**
 79      * 产生随机数组
 80      * @param count
 81      * @return
 82      */
 83     private static int[]  createDate(int count) {
 84         int[] data=new int[count];
 85           Random rand = new Random();
 86           boolean[] bool = new boolean[100];
 87           int num = 0;
 88           for (int i = 0; i < count; i++) {
 89            do {
 90             // 如果产生的数相同继续循环
 91             num = rand.nextInt(100);
 92            } while (bool[num]);
 93            bool[num] = true;
 94     
 95            data[i]=num;
 96           }
 97           return data;
 98     }
 99     public static void main(String[] args) {
100         int[] data = createDate(10);
101         print(data);
102         mergeSort(data);
103         System.out.println("排序后的数组：");
104         print(data);
105     }
106 
107 }