黑马程序员技术交流社区

标题: 算法之归并排序 [打印本页]

---

作者: sansu    时间: 2016-3-7 23:02
标题: 算法之归并排序

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)

下载附件

2016-3-7 23:01 上传

---

作者: sansu    时间: 2016-3-7 23:09
在归并算法下,快速,冒泡等都弱爆了

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2