데이터 정보의 역순 대

역순
역순 대 는 한 요소 서열 에서 일정한 크기 비교 방법 에 따라 서열 에서 두 요소 의 크기 순 서 를 뒤 바 꾸 는 조합 을 말한다.
A [1. n] 을 설정 하면 n 개의 다른 수 를 포함 하 는 배열 입 니 다. i < j 의 경우 A [i] > A [j] 가 있 으 면 (i, j) 는 A 중의 역순 대 라 고 합 니 다.
주어진 정렬 대기 서열 에 대해 그 중의 역순 대 에 대한 발견 과 복원 은 바로 정렬 이 해결 해 야 할 일이 다. 정렬 과정 에서 역순 대 를 먼저 발견 한 다음 에 복원 하 는 것 은 정렬 성능 이 향상 되 는 방법 을 연상 시 키 기 때문이다.
1. 한 번 의 복원 작업 으로 여러 그룹의 역순 을 복원 합 니 다.
eg: 총 21 쌍, 총 10 쌍.
7, 6, 5, 4, 3, 2, 1 - (1 과 7 교환) -- > 1, 6, 5, 4, 3, 2, 7
한 번 에 11 쌍 을 복원 처리 했다.
2. 한 번 에 조작 을 바 꾼 후, 가능 한 한 추가 적 인 역순 이 발생 하지 않도록 한다.
eg: 총 16 쌍, 총 11 쌍.
7, 6, 5, 1, 3, 2, 4 - (4 와 7 의 교환) -- > 4, 6, 5, 1, 3, 2, 7
한 번 에 5 쌍 을 복원 처리 하고, 또 한 쌍 이 더 생 겼 다.
내 가 관찰 한 비교 류 정렬 에서 빠 른 정렬 은 1 을 나타 내 는데 2 가 부족 하 다.합병 순 서 는 반대로 2 가 부족 하 다 는 것 을 보 여 준다.
역순 대 에 관 한 통계 알고리즘 코드 참조

/* Copyright (C) 2000-2007 Wang Pengcheng <[email protected]>
 * Licensed to the Wang Pengcheng under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The LGPL licenses this file to You under the GNU Lesser General Public
 * Licence, Version 2.0  (the "License"); you may not use this file except in
 * compliance with the License.  You may obtain a copy of the License at
 *
 *     http://www.gnu.org/licenses/lgpl.txt
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package mypackage.algorithm.unit02;

public class Inversion ...{
    
    private static int tot;
    
    /** *//**
     *InsertionSort
     *The time limit of this sort is O(n^2)
     *<strong>O(n^2)</strong>
     *@param  element will be sorted
     */
    private static <Type extends Comparable> void insertionSort(Type element[])...{
        for(int j=1;j<element.length;j++)...{
            Type    key    =    element[j];
            int i    =    j-1;
            
            while( (i>=0)&&(element[i].compareTo(key)>0))...{
                element[i+1]    =    element[i];
                tot++;
                i--;
            }
            element[i+1]    =    key;
        }
    }
    /** *//**
     *Merge used in the mergeSort
     *<strong>O(n)</strong>
     *@param element Type[] the elements to be merged
     *@param p int the begin of the  first elements
     *@param q int the end of the first elements
     *@param r int the end of the second elements
     */
    private static <Type extends Comparable> void merge(Type element[],int p,int q,int r)...{
        int nl    =    q-p+1;
        int nr    =    r-q;
        
        Type[] lElement,rElement;
        lElement    =    (Type[])java.lang.reflect.Array.newInstance(element.getClass().getComponentType(),nl);
        rElement    =    (Type[])java.lang.reflect.Array.newInstance(element.getClass().getComponentType(),nr);
                
        for(int i=0;i<nl;i++)...{
            lElement[i]    =    element[p+i];
        }
        for(int i=0;i<nr;i++)...{
            rElement[i]    =    element[q+i+1];
        }
        
        int i=0,j=0;
        int k    =    p;
        while((i<nl)&&(j<nr))...{
            if(lElement[i].compareTo(rElement[j])<=0)...{
                element[k]    =    lElement[i];
                i++;
            }else...{
                element[k]    =    rElement[j];
                j++;
                tot+=nl-i;
            }
            k++;
        }
        
        while(i<nl)...{
            element[k]    =    lElement[i];
            i++;
            k++;
        }
        while(j<nr)...{
            element[k]    =    rElement[j];
            j++;
            k++;
        }
    }
    
    /** *//**
     *mergeSort
     *Sort the elements by the compareTo method
     *<strong>O(nlgn)</strong>
     *@param  element Type[] that will be sorted
     *@param p the begin of the list will be sorted
     *@param r the end of the list will be sorted
     */
    private static <Type extends Comparable> void mergeSort(Type element[],int p,int r)...{
        if(p<r)...{
            int q    =    (p+r)/2;
            mergeSort(element,p,q);
            mergeSort(element,q+1,r);
            merge(element,p,q,r);
        }
    }
    private static <Type extends Comparable> void mergeSort(Type element[])...{
        mergeSort(element,0,element.length-1);
    }
    
    /** *//**
     * Count the inversion number by O(nlgn)
     * @param <Type> inversion number type
     * @param element inversion number list
     * @return count number of inversion
     */
    public static <Type extends Comparable>  int countMerge(Type element[])...{
        tot=0;
        mergeSort(element.clone());
        return tot;
    }

    /** *//**
     * Count the inversion number by O(n^2)
     * @param <Type> inversion number type
     * @param element inversion number list
     * @return count number of inversion
     */
    public static <Type extends Comparable> int countInsertion(Type element[])...{
        tot=0;
        insertionSort(element.clone());
        return tot;
    }
    /** *//**
     * @param args
     */
    public static void main(String[] args) ...{
        Integer[] a = ...{4,6,5,1,3,2,7};
        System.out.println(Inversion.countMerge(a));
    }

}

 
마지막 으로 명심 하 자.
《 이 개 복: 알고리즘 의 힘 》 알고리즘 을 따 는 것 은 컴퓨터 와 네트워크 에 국한 되 지 않 는 다.
컴퓨터 분야 밖의 예 를 들 어 고에너지 물리 연구 에 있어 서 많은 실험 들 이 매 초 에 몇 TB 의 데 이 터 를 얻 을 수 있다.그러나 처리 능력 과 저장 능력 이 부족 하기 때문에 과학자 들 은 처리 되 지 않 은 대부분의 데 이 터 를 버 려 야 한다.그러나 새로운 요소 의 정 보 는 우리 가 처리 하지 못 한 데이터 안에 숨 어 있 을 가능성 이 높다 는 것 을 알 아야 한다.마찬가지 로 다른 어떤 분야 에서 도 알고리즘 은 인간 의 삶 을 바 꿀 수 있다.예 를 들 어 인류 유전자 에 대한 연 구 는 알고리즘 때문에 새로운 의료 방식 을 발명 할 수 있다.국가 안 보 분야 에서 효과 적 인 알고리즘 은 다음 911 의 발생 을 피 할 수 있다.기상 에 있어 서 알고리즘 은 미래 천재 의 발생 을 더욱 잘 예측 하여 생명 을 구 할 수 있다.
그래서 만약 에 컴퓨터 의 발전 을 응용 과 데이터 가 급속히 증가 하 는 큰 환경 에 두 면 반드시 발견 할 것 이다.알고리즘 의 중요성 은 날로 줄 어드 는 것 이 아니 라 날로 강화 되 고 있다.
감사합니다.
참고서
토 마 스 H. C. 코 멘, 찰스 E. 레이 서 슨, 로 널 드 L. 리 베 스 트, 클 리 퍼 드 스타 인 기계공 업 출판사
은 인 곤, 도 영 뢰, 사 약 양, 성 현화청화대학 출판사
유 여 가, 황 량 청화대학 출판사
《 이 개 복: 산법 의 힘 》.http://www.ieee.org.cn/dispbbs.asp?boardID=60&ID=31651