美文网首页算法
排序算法:归并排序

排序算法:归并排序

作者: ADark0915 | 来源:发表于2018-02-27 16:37 被阅读3次

    基本思想:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表。即,把待排序序列分为若干个子序列,每个子序列是有序的,然后再把有序子序列合并为整体有序序列。

        private void mergeSort(int[] pArr, int pLeft, int pRight) {
            if (pArr.length < 2) {
                return;
            }
            if (pLeft < pRight) {
                int mid = pLeft + (pRight - pRight) / 2;
                mergeSort(pArr, pLeft, mid);
                mergeSort(pArr, mid + 1, pRight);
    
                merge(pArr, pLeft, mid, pRight);
            }
        }
    
        private void merge(int[] pArr, int pLeft, int pMid, int pRight) {
            int[] temp = new int[pRight - pLeft + 1];
            // 左边数组起始指针
            int i = pLeft;
            // 右边数组起始指针
            int j = pMid + 1;
            // 临时数组起始指针
            int k = 0;
    
            // 先把较小的数放到数组中
            while (i <= pMid && j <= pRight) {
                if (pArr[i] < pArr[j]) {
                    temp[k++] = pArr[i++];
                } else {
                    temp[k++] = pArr[j++];
                }
            }
    
            // 把左边剩余的数放到数组中
            while (i <= pMid) {
                temp[k++] = pArr[i++];
            }
    
            // 把右边剩余的数放到数组中
            while (j <= pRight) {
                temp[k++] = pArr[j++];
            }
    
            // 把原始数组中相应位置的数据覆盖掉
            for (int l = 0; l < temp.length; l++) {
                pArr[pLeft + l] = temp[l];
            }
    
        }
    

    相关文章

      网友评论

        本文标题:排序算法:归并排序

        本文链接:https://www.haomeiwen.com/subject/wusmxftx.html