排序算法------ 归并排序

淡淡的烟草味﹌ 2024-03-31 14:09 17阅读 0赞

## 排序算法------ 归并排序 ##

归并排序算法的理念在于：  
1.递归  
2.切分至最小单位  
3.对最小单位进行排序  
3.1.从最小单位形成：有序数组  
3.2.比较有序数组的顺序

/**
     * 归并排序
     */
    public class GuiBing {
        
    
    
        public static void main(String[] args) {
        
            int[] a = {
        7,6,23,8,9,10,13,10,3,7,15,20,23};
            int[] end = guibingTest(a);
            System.out.println(Arrays.toString(end));
        }
    
        //对数组进行归并排序
        //精髓在于
        // 1. 递归调用自己，对数组进行无限切分，直至最小单位,在进行排序
        // 递归
        // 切分
        // 排序
        public static int[] guibingTest(int[]a){
        
            //如果切分到,最小单位，即一个数字，则返回，可以进行排序了
            if (a.length<2){
        
                return a;
            }
            //取中间数,切分左右两部分
            int middle = a.length / 2;
            //取0到中间点的数据
            int[] left = Arrays.copyOfRange(a, 0, middle);
            //取中间点到结尾的数据
            int[] right = Arrays.copyOfRange(a, middle, a.length);
            //递归调用自己,一直向下切分
            int[] minLeft = guibingTest(left);
            int[] minRigth = guibingTest(right);
    
            //进行排序
            int[] end = guibingpaixu(minLeft,minRigth);
            return end;
    
        }
    
        //对每个有序数组进行排序
        public static int[] guibingpaixu(int[] minLeft, int[] minRigth) {
        
            int[] newList = new int[minLeft.length+minRigth.length];
            //index 作为新数组的下标
            //i 作为左边数组的下标
            //y 作为右边数组的下标
            //循环新数组的长度
            for (int index = 0,i = 0,y = 0;index < newList.length; index++){
        
                //如果 左边数组没有值了,则取右边数组的值
                if (i >= minLeft.length){
        
                    newList[index] = minRigth[y];
                    y++;
                }else if(y >= minRigth.length){
        
                    //如果右边数组没有值了,则取左边数组
                    newList[index] = minLeft[i];
                    i++;
                }else if (minLeft[i] <= minRigth[y]){
        
                    //比较大小
                    newList[index] = minLeft[i];
                    i++;
                }else {
        
                    newList[index] = minRigth[y];
                    y++;
                }
            }
            return newList;
        }
    }

输出结果;

[3, 6, 7, 7, 8, 9, 10, 10, 13, 15, 20, 23, 23]