当前位置:   article > 正文

归并排序_spdz算法

spdz算法

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法,包括两个步骤,先分解再合并,如图:
在这里插入图片描述
即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并排序 (递归实现)
时间复杂度: n*log(2)n
空间复杂度: O(n)
稳定排序

//归并排序
    public static void mergeSort(int[] array) {
        mergeSortInternal(array,0,array.length-1);
    }

    public static void mergeSortInternal(int[] array, int low, int high) {
        //当每组数组分解成只有一个时结束
        if (high-low <= 0) {
            return;
        }
        //mid 是每组数组的中间下标(分解后是前一个数组的最后一个数下标)
        int mid = (low + high)>>>1;//除2
        //分解(每次数组都二分)
        mergeSortInternal(array, low, mid);
        mergeSortInternal(array,mid+1,high);//mid+1 是后一个数组的第一个数下标
        //合并
        merge(array,low,mid,high);
    }
    //合并
    public static void merge (int[] array, int low, int mid, int high) {
        int les1 = low;//les1: 前一个数组的第一个数下标
        int les2 = mid + 1;//les2: 后一个数组的第一个数下标
        int[] ret = new int[high-low+1];//建一个长度为 需要合并 的两个数组的长度和 的新数组
        int i = 0;//新数组下标
        //需要合并 的两组按位置依次比较,将小的按顺序放入新数组
        while (les1 <= mid && les2 <= high) {
            //array[les1] <= array[les2] 保证了 归并排序的稳定性
            if (array[les1] <= array[les2]) {
                ret[i++] = array[les1++];
            }else {
                ret[i++] = array[les2++];
            }
        }
        //判断谁没走完,把剩下的数放到ret数组中
        while (mid >= les1) {
            ret[i++] = array[les1++];
        }
        while (high >= les2) {
            ret[i++] = array[les2++];
        }
        //将新数组中的数放到array数组中
        for (int n : ret) {
            array[low++] = n;
        }

    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/神奇cpp/article/detail/751582
推荐阅读
相关标签
  

闽ICP备14008679号