归并排序 订阅
归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 展开全文
归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
信息
外文名
Merge Sort
空间复杂度
T(n)
发明者
约翰·冯·诺伊曼
中文名
归并排序
稳定性
稳定
时间复杂度
O(n log n)
归并排序归并操作
归并操作,也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。如 设有数列{6,202,100,301,38,8,1}初始状态:6,202,100,301,38,8,1第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;第三次归并后:{1,6,8,38,100,202,301},比较次数:4;总的比较次数为:3+4+4=11;逆序数为14;
收起全文
精华内容
下载资源
问答
  • 归并排序

    千次阅读 2019-03-01 11:31:48
    归并排序

    0.时间复杂度

    lgn * n
    

    1.Java实现

        private static void println(int[] array) {
            for (int item : array) {
                System.out.print(item + " ");
            }
            System.out.println();
        }
    
        private static void mergeSortByIndex(int[] array, int startIndex, int endIndex) {
            // 最小处理块1 然后依次往上层归并
            if (startIndex < endIndex) {
                int centerIndex = (startIndex + endIndex) / 2;
                mergeSortByIndex(array, startIndex, centerIndex);
                mergeSortByIndex(array, centerIndex + 1, endIndex);
                mergeArray(array, startIndex, centerIndex, endIndex);
            }
        }
    
        private static void mergeArray(int[] array, int startIndex, int centerIndex, int endIndex) {
            int[] tempArray = new int[endIndex - startIndex + 1];
            int leftIndex = startIndex;
            int rightIndex = centerIndex + 1;
            boolean leftFlag = true;
            boolean rightFlag = true;
            int temp = 0;
            while (temp <= endIndex - startIndex) {
                if (leftIndex > centerIndex) {
                    leftFlag = false;
                }
                if (rightIndex > endIndex) {
                    rightFlag = false;
                }
                if (leftFlag && rightFlag) {
                    // 左右2边都有
    //                if (array[leftIndex] <= array[rightIndex]) {
                    if (array[leftIndex] >= array[rightIndex]) {
                        tempArray[temp] = array[leftIndex];
                        leftIndex ++;
                    } else {
                        tempArray[temp] = array[rightIndex];
                        rightIndex ++;
                    }
                } else if (!leftFlag && !rightFlag) {
                    // 左右2边都没有
                    break;
                } else if (!leftFlag && rightFlag) {
                    // 只有右边有
                    tempArray[temp] = array[rightIndex];
                    rightIndex ++;
                } else {
                    // 只有左边有
                    tempArray[temp] = array[leftIndex];
                    leftIndex ++;
                }
                temp ++;
            }
    
            // 复制到原数组中
            for (int copyIndex  = 0; copyIndex  < tempArray.length; copyIndex ++) {
                array[startIndex + copyIndex] = tempArray[copyIndex];
            }
        }
    
        private static void mergeSort(int[] array) {
            mergeSortByIndex(array, 0, array.length - 1);
        }
    
        public static void main(String[] args) throws Exception {
    //        int[] array = {10, 9, 8};
            int[] array = {8, 9, 10};
            println(array);
            mergeSort(array);
            println(array);
        }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 46,186
精华内容 18,474
关键字:

归并排序