A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© sansu 中级黑马   /  2016-3-7 23:02  /  520 人查看  /  1 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文


public class Demo_O {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
     
                int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };  
                print(data);  
                mergeSort(data);  
                System.out.println("排序后的数组:");  
                print(data);  
            }  
         
            public 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) / 2;  
                // 对左边数组进行递归  
                sort(data, left, center);  
                // 对右边数组进行递归  
                sort(data, center + 1, right);  
                // 合并  
                merge(data, left, center, right);  
                print(data);  
            }  
         
            /**
             * 将两个数组进行归并,归并前面2个数组已有序,归并后依然有序
             *  
             * @param data
             *            数组对象
             * @param left
             *            左数组的第一个元素的索引
             * @param center
             *            左数组的最后一个元素的索引,center+1是右数组第一个元素的索引
             * @param right
             *            右数组最后一个元素的索引
             */  
            public static void merge(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只会执行其中一个)  
                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");  
                }  
                System.out.println();  
            }  
         
        
    }


QQ图片20160307230038.png (10.47 KB, 下载次数: 14)

QQ图片20160307230038.png

1 个回复

倒序浏览
在归并算法下,快速,冒泡等都弱爆了
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马