简单排序:归并排序 博客分类： Sort

    public void mergeSort(int[] array){
        int temp = array.length/2;
        
        if(temp == 0){
            return;
        }
        
        int[] a = new int[temp];
        int[] b = new int[array.length - temp];
        
        for(int i=0;i<temp;i++){
            a[i] = array[i];
        }
        
        for(int i=0;i<array.length - temp;i++){
            b[i] = array[temp + i];
        }
        
        if(a.length != 1){
            this.mergeSort(a);
        }
        if(b.length != 1){
            this.mergeSort(b);
        }
        
        int aIndex = 0;
        int bIndex = 0;
        int arrayIndex = 0;
        
        while(aIndex != a.length && bIndex != b.length){
            if(a[aIndex] > b[bIndex]){
                array[arrayIndex++] = b[bIndex++];
                continue;
            }else if(a[aIndex] < b[bIndex]){
                array[arrayIndex++] = a[aIndex++];
                continue;
            }else{
                array[arrayIndex++] = a[aIndex++];
                array[arrayIndex++] = b[bIndex++];
            }
        }
        
        while(bIndex < b.length){
            array[arrayIndex++] = b[bIndex++];
        }
        
        while(aIndex < a.length){
            array[arrayIndex++] = a[aIndex++];
        }
    }

效率:
由于需要一个被排序数组等大小的数组来辅助排序,空间复杂度比较高,时间复杂度为:O(N*logN)