정렬 - 사고방식 간략 분석 (一)

간단 한 소개
이 글 은 최근 에 배 운 정렬 알고리즘 을 정리 하여 그 사상 과 차이 점 을 추출 해 냈 다.병합 정렬, 빠 른 정렬, 쌓 기 정렬 및 거품 정렬 이 있 습 니 다.
정렬 병합 (Merging Sort)

병합 은 두 개 또는 두 개 이상 의 질서 표를 새로운 질서 표 로 조합 하 는 것 을 말한다.

병합 정렬 은 무질서 한 대기 정렬 서열 을 여러 개의 질서 있 는 하위 서열 로 분해 하고 질서 있 는 하위 서열 을 전체 질서 있 는 서열 로 통합 하 는 과정 을 말한다.

길이 가 1 인 서열 은 질서 가 있다.

두 개의 분해 와 병합 전략 을 사용 하여 간단 하고 실행 하기 쉬 우 며 이러한 병합 순 서 는 2 - 도로 병합 정렬 이 라 고 합 니 다.
병합 정렬 의 실현
다른 표기 법:

//       a[i..m] a[m+1..n]    b[i..n]    n 
void Merge(int a[], int i,int m, int n, int b[]){
    int k,j;
    for(k = i, j = m+1; k <= m && j <= n;k++){
        if(a[i] < a[j]){
            b[k] = a[i++];
        }else{
            b[k] = a[j++];
        }
    }

    while(i<=m) b[k++] = a[i++];
    while(j<=n) b[k++] = a[j++];
}

// i：     （    0）--      MSort       a，b       ：
//  i    ，  a[s..t]   b[s..t]
//    b[s..t]   a[s..t]
void MSort(int a[], int b[], int i,int s,int t){
    int m;
    if( s == t ){
        if( 1 == i%2 ) b[s] = a[s];
    }else{
        m = (s+t)/2;
        MSort(a,b,i+1,s,m);
        MSort(a,b,i+1,m+1,t);

        if( 1 == i%2 ) Merge(a,s,m,t,b);
        else Merge(b,s,m,t,a);
    }
}

void MergeSort(int a[],int len){
    int b[len];
    MSort(a,b,0,0,len-1);
    free(b); //     
}

간단 한 분석: 전체 병합 정렬 과정 은 전체 8968 ° logn * 8969 ° 층 의 재 귀 분해 와 병합 을 해 야 합 니 다. 이 를 통 해 정렬 된 알고리즘 시간 복잡 도 는 O (n * logn) 입 니 다.
병합 정렬 은 안정 적 인 정렬 입 니 다.
빠 른 정렬 (빠 른 정렬)
가장 간단 한 교환 정렬 은 거품 정렬 이 고 빠 른 정렬 은 거품 정렬 에 대한 개선 입 니 다.
먼저 대기 서열 에서 하나의 키 워드 를 선택 하여 추축 이 라 고 한다. 키워드 와 추축 의 비 교 를 통 해 대기 서열 을 추축 전후 에 있 는 두 개의 하위 서열 로 나눈다. 그 중에서 추축 전의 하위 서열 의 모든 키 워드 는 추축 보다 크 지 않 고 추축 뒤의 하위 서열 은 모두 추축 보다 작 지 않다. 이때 추축 이 이미 도착 했다.다시 같은 방법 에 따라 이 두 개의 하위 서열 을 각각 귀속 시 켜 빠 른 정렬 을 하여 최종 적 으로 전체 서열 을 질서 있 게 한다
빠 른 정렬 의 구체 적 인 과정:

비트 로 우 를 대기 기록 의 첫 번 째 기록 (동시에 중추 기록) 을 가리 키 고 하 이 는 마지막 기록 을 가리 키 며 중추 기록 을 가리 키 는 0 번 유 휴 단원 으로 복사 합 니 다.

우선 하 이 가 가리 키 는 위 치 를 앞으로 이동 하여 첫 번 째 추축 기록 키워드 보다 작은 기록 을 찾 아 pivotkey 가 가리 키 는 위치 로 복사 합 니 다.

그리고 low 를 뒤로 이동 시 켜 첫 번 째 추축 기록 키워드 보다 큰 기록 을 찾 아 하 이 가 가리 키 는 위치 로 복사 합 니 다.

low 와 high 가 같 을 때 까지 중추 기록 을 low 가 가리 키 는 위치 로 복사

//     a[low..high]      ，            
//                     ，                   
int Partition(int a[],int low, int high){
    a[0] = a[low];
    while(low<high){
        while(low < high && a[high] >= a[0]) high --;
        a[low] = a[high];

        while(low < high && a[low] <= a[0]) low++;
        a[high] = a[low]; 
    }   
    a[low] = a[0];
    return low;
}

void QSort(int a[],int s,int t){
    int pivotloc;
    //       
    if( s<t ){
        pivotloc = Partition(a,s,t);
        //   pivotloc              
        QSort(a,s,pivotloc-1);
        QSort(a,pivotloc+1,t);
    }
}

//  a[1..len]        
void QuickSort(int a[],int len){
    QSort(a,1,len);
}

추축 키워드 가 가장 크 거나 가장 작은 상황 을 피하 기 위해 '삼자 취 중' 의 방법 을 사용 할 수 있다. 즉, a [s], a [t], a [(s + t) / 2] 삼자 중 키워드 의 크기 가 중심 에 있 는 기록 을 추축 으로 하고 a [s] 와 교환 할 수 있다.
쌓 기 정렬 의 기본 동작
더 미 는 완전 이 진 트 리 로 쌓 여 있 는 모든 비 잎 결점 이 좌우 부분 보다 크 지 않 으 면 작은 지붕 더미 라 고 부른다.만약 에 쌓 인 모든 비 잎 결점 이 좌우 부분 보다 작 지 않 으 면 큰 지붕 더미 라 고 부른다.
퇴적 구조 유형

typedef struct{
    int *rcd; //    ，0       
    int n; //    
    int size; //     
    int tag; //           
    int (*prior)(int a,int b); //     ，           
} Heap;

int greatPrior(int x,int y) { return x>=y; }
int lessPrior(int x,int y) { return x<=y; }

선별

더미 의 선별 작업 은 더미 에서 지정 한 pos 노드 가 뿌리 인 서브 트 리 를 쌓 는 특성 을 유지 하 는데 그 전 제 는 pos 노드 의 좌우 서브 트 리 가 모두 쌓 인 특성 을 만족 시 키 는 것 이다

.

과정: pos 결점 을 좌우 아이 우선 자 와 비교 하고 pos 결점 이 우선 이면 끝난다.그렇지 않 으 면 pos 결점 은 좌우 아이 우선 순위 와 위 치 를 교환 하고 pos 위치 표 시 를 아래로 이동 하 며 상기 절 차 를 반복 합 니 다.

int SwapHeapElem(Heap &H,int i, int j){
    if( i < 0 || i > H.n || j < 0 || j > H.n ) return 0;

    int t;
    t = H.rcd[i];
    H.rcd[i] = H.rcd[j];
    H.rcd[j] = t;
    return 1;
}

//       ，      pos                ，    pos              
void ShiftDown(Heap &H,int pos){
    int c, rc;
    while(pos<=H.n/2){
        c = pos*2;
        rc = pos*2+1;
        if(rc<=H.n && H.prior(H.rcd[rc],H.rcd[c])) c = rc; //              

        if(H.prior(H.rcd[pos],H.rcd[c]))
            return ;
        SwapHeapElem(H,pos,c);
        pos = c;
    }
}

더미 꼭대기 결산 점 삭제

과정: 1. 더미 꼭대기 의 결산 점 을 꺼낸다.2. 쌓 인 지붕 의 결산 점 과 쌓 인 위 치 를 교환 하고 쌓 인 길 이 를 1 로 줄인다.3. 퇴적 지점 을 선별

int RemoveFirsHeap(Heap &H, int &e){
    if(H.n<=0) return 0;

    e = H.rcd[1];
    SwapHeapElem(H,1,H.n);
    if(H.n>1)  ShiftDown(H,1);
    return 1;
} 

쌓 기 작업

void MakeHeap(Heap &H,int a[],int n,int size,int tag,int (*prior)(int a,int b)){
    H.rcd = a;
    H.n = n;
    H.size = size;
    H.tag = tag;
    H.prior = prior;

    int i;
    //          ，       
    for( i = H.n/2; i > 0; i -- ){
        ShiftDown(H,i);
    }
}

더미 정렬 (히트 정렬)

더미 의 특성 을 이용 하여 순 서 를 매 길 수 있 고 큰 무 더 기 는 오름차 순 서 를 매 길 수 있 으 며 작은 무 더 기 는 내림차 순 서 를 매 길 수 있다.먼저 정렬 대기 서열 을 큰 지붕 더미 로 만들어 서 쌓 인 지붕 의 결산 점 을 가장 크게 만 들 고 쌓 인 지붕 의 결산 점 과 쌓 인 꼬리 를 교환 하 는 위 치 를 1 로 줄 이 고 나머지 결산 점 을 쌓 아 두 번 째 큰 값 의 결산 점 을 얻 도록 한다.이 과정 을 반복 하면 상승 서열

을 얻 을 수 있다.

void HeapSort(int a[],int n){
    Heap H;
    MakeHeap(H,a,n,n+2,1,lessPrior);
    int e;
    for( int i = H.n; i > 0; i -- ){
        if(RemoveFirsHeap(H,e) )
            printf("%d ",e);
    }
}

거품 정렬 (Bubble Sort)

첫 번 째 거품 이 발생 하 는 과정 에서 먼저 첫 번 째 와 두 번 째 기록 을 비교 하고 역순 이면 위 치 를 교환한다.그 다음 에 두 번 째 와 세 번 째 기록 을 비교 하고 순서대로 조작 하 며 n - 1 과 n 번 째 기록 을 비교 할 때 까지 이때 n 번 째 기록 이 가장 크다.두 번 째 거품 은 n - 1 위치 로 큰 기록 을 교환 하여 모든 기록 이 질서 가 있 을 때 까지 합 니 다.

void BubbleSort(int a[], int len){
    int t;
    int i, j;
    // i         
    for( i = 0; i < len; i ++ ){
        //      len-i，len-i          
        for( j = 1; j < len-i; j ++ ){
            if( a[j-1] < a[j] ){
                t = a[j-1];
                a[j-1] = a[j];
                a[j] = t;
            }
        }
    }
} 

개선:

void BubbleSort(int a[], int len){
    int t;
    int i, j, flag;
    flag = -1;
    // i          ，（         ） 
    // flag  a[flag-1,flag..len-1]       ，  flag            
    for( i = 0; i < len; i ++ ){
        if( flag != -1 ){
            i = len - flag; //            
            flag = -1;
        }

        for( j = 1; j < len-i; j ++ ){
            if( a[j-1] > a[j] ){
                flag = j;
                t = a[j-1];
                a[j-1] = a[j];
                a[j] = t;
            }
        }
    }
} 

기타 학습 링크 거품 정렬 의 세 가지 실현