정렬 코드 를 반절 삽입 하여 실현 하고 사고 하 다.

3006 단어 데이터 구조삽입 정렬반절 기 삽입 정렬
대량의 데이터 에 대해 정렬 을 직접 삽입 하 는 비교 와 이동 하 는 횟수 가 비교적 많 을 것 이다. 정렬 을 직접 삽입 하 는 토대 에서 비교 횟수 를 줄 이기 위해 반절 삽입 정렬 을 실현 했다.반절 삽입 정렬 은 주로 두 부분 으로 나 뉘 는데 첫 번 째 부분 은 배열 할 숫자 가 삽입 해 야 할 위 치 를 찾 는 것 이 고 두 번 째 부분 은 데 이 터 를 이동 하여 배열 할 데 이 터 를 질서 있 는 수열 에 삽입 하 는 것 이다.데이터 구 조 는 정렬 을 직접 삽입 하 는 데이터 구조 와 같 으 며, 절반 에 정렬 코드 를 삽입 하 는 것 은 다음 과 같다.
void BInsertSort(sqList L,int len)
{
    //           
    //             
    //                   
    //         
    if(len<=1) return;
    for(int i=2;i<=len;i++)
    {
        //             

            int low=1,high=i-1;
            L.r[0] = L.r[i];
            while(low<=high)
            {
                int mid=(low+high)/2;
                if(L.r[mid]<L.r[0]) low=mid+1;
                else high=mid-1;
            }
            //low high              
            //    
            for(int j=i-1;j>=high;--j)
                L.r[j+1]=L.r[j];
            L.r[high+1]=L.r[0];


    }
    cout<<endl;
    cout<<"             "<<endl;
    for(int i=1;i<=len;i++)
        cout<<L.r[i]<<" ";
    cout<<endl;
}

여기 서 가장 작은 오류 가 발생 하기 쉬 운 곳 은 삽입 할 위 치 를 비교 할 때 while (low < = high) 순환 입 니 다. 이 등 호 를 가 져 올 지 말 지 헷 갈 리 기 쉽 습 니 다. 이것 은 어떤 구체 적 인 인 인 스 턴 스 를 원 하 는 지 디 버 깅 프로그램 이 인상적 입 니 다.정렬 을 직접 삽입 하 는 것 에 비해 접 는 삽입 정렬 은 비교 횟수 를 줄 이 고 정렬 을 직접 삽입 합 니 다. 삽 입 된 위 치 를 찾 을 때 하나의 비교 가 필요 합 니 다. 접 는 삽입 정렬 은 점프 비교 이기 때문에 비교 하 는 횟수 가 줄 어 들 었 지만 이동 하 는 횟수 는 줄 어 들 지 않 았 습 니 다.코드 를 다 쓰 면 똑똑히 볼 수 있 습 니 다. 반 으로 접 고 정렬 하 는 시간 복잡 도 는 o (n2) 이지 만 비교 횟수 가 줄 었 습 니 다.
데이터 구조 학습 의 길 - 제2 장: 선형 표 의 순서 표시 와 실현
JVM 관련 면접 문제

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage