归并排序的java实现

墨蓝 2022-03-02 06:26 113阅读 0赞

看了《算法》第四版归并排序部分，用java实现了一下，

![抽象实现方法][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0haUnVu_size_16_color_FFFFFF_t_70]

![图解归并排序][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0haUnVu_size_16_color_FFFFFF_t_70 1]

下贴源码：

public class MergeSort {
        private static int[] auk;
        public static void main(String[] args){
            int[] array = new int[]{34,53,33,65,23,75,33,6,12,64};
            auk = new int[array.length];
            sort(array,0,array.length-1);
            for (int i=0;i<array.length;i++){
                System.out.print(array[i]+" ");
            }
        }
    
        public static void sort(int[] array, int lo, int hi){
            if(lo>=hi){return;}
            int mid = lo+(hi-lo)/2;
            sort(array,lo,mid);
            sort(array,mid+1,hi);
            merge(array, lo,mid,hi);
        }
        public static void merge(int[] array, int lo, int mid, int hi){
            int i = lo;//左子数组指向指针
            int j = mid+1;//右子数组指向指针
            for(int k=lo;k<=hi;k++){ //新建备份数组
                auk[k] = array[k];
            }
            for(int k=lo;k<=hi;k++){//遍历原数组，考虑把数组的值装到备份数组的哪个位置
                if (i>mid) {//左边数组已遍历完
                    array[k] = auk[j];
                    j++;
                }
                else if(j>hi){//右边数组遍历完成
                    array[k] = auk[i];
                    i++;
                }
                else if(auk[i]<auk[j]){//左边数组比右边数组小，把左数组值给到备份数组
                    array[k] = auk[i];
                    i++;
                }
                else { //左边数组不比右边数组小
                    array[k] = auk[j];
                    j++;
                }
    
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0haUnVu_size_16_color_FFFFFF_t_70]: /images/20220302/0f47cf55cbf6414187391402b9a55e3b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0haUnVu_size_16_color_FFFFFF_t_70 1]: /images/20220302/02b9d55b01f0483d9d9556df666f0981.png