"chaos" 의 알고리즘 - 비 재 귀적 정렬

[성명: 판권 소유, 전재 환영. 사서함 으로 연락:[email protected]】
나의 지난 블 로그 에서 나 는 해시 표 에 대해 이야기 했다. 해시 표 로 대량의 데 이 터 를 찾 는 것 은 좋 은 방법 이다. 그것 은 일반 알고리즘 을 찾 는 것 보다 약간 은 말 하지 않 아 도 안다.예 를 들 어 100 만 개의 데이터 로 서 일반적인 검색 방법 을 사용 하면 모든 데 이 터 를 평균 적 으로 찾 으 려 면 몇 십 만 번 이 필요 하 다. 2 점 으로 20 번 을 찾 으 면 해결 할 수 있 고 해시 표 로 찾 으 면 더욱 빠 를 것 이다.이 차 이 는 매우 뚜렷 하 다.그러나 이 세 가지 검색 방법 으로 볼 때 성능 이 좋 은 것 은 모두 데이터 에 대해 질서 있 게 조작 하 는 것 이다.이 박문 에서 우 리 는 정렬 알고리즘 에 대해 총 결 을 한다.
정렬 과정 에서 데이터 요소 가 메모리 에서 완전히 두 가지 로 나 눌 수 있 는 지 여부 에 따라 내부 정렬 과 외부 정렬 입 니 다.정렬 은 주로 세 가지 요 소 를 바탕 으로 비교 한다. 시간 복잡 도, 공간 복잡 도와 알고리즘 의 안정성 이다.그러나 개인 적 으로 정렬 알고리즘 은 주로 재 귀적 정렬 과 비 재 귀적 정렬 로 나 뉜 다 고 생각 합 니 다.비 재 귀적 정렬 은 주로 비 재 귀적 방법 에 따라 데 이 터 를 정렬 합 니 다. 즉, 주요 데이터 의 위치 이동 과 순환 으로 완성 합 니 다. 재 귀적 방법 은 우리 가 현재 데 이 터 를 배열 할 때 먼저 하위 데 이 터 를 질서 있 게 배열 한 다음 에 현재 의 데 이 터 를 배열 합 니 다.이런 끊임없이 재 귀 호출 하 는 방법 은 바로 재 귀 정렬 이다.재 귀적 으로 정렬 하지 않 는 방법 이 많 습 니 다. 여 기 는 거품 정렬, 삽입 정렬, 힐 정렬 을 소개 합 니 다.재 귀 하 는 방법 도 적지 않다. 여기 서 소개 하 는 방법 은 빠 른 정렬, 병합 정렬 과 정렬 이다.정렬 된 내용 이 매우 많 습 니 다. 본 블 로 그 는 주로 비 재 귀적 정렬 을 소개 하고 재 귀적 정렬 의 내용 은 주로 다음 절 내용 에서 해결 합 니 다.
거품 정렬
컴퓨터 프로 그래 밍 에서 저 는 거품 정렬 이 가장 기본 적 인 정렬 알고리즘 이 라 고 생각 합 니 다. 그 사상 은 매우 간단 합 니 다. 이름 에 따라 우 리 는 정렬 이 크 거나 작은 '튀 어 나 와 야 한 다 는 것 을 알 고 있 습 니 다.주요 사상 절 차 는 다음 과 같다.
1. 서로 인접 한 앞 뒤 두 개의 데 이 터 를 비교 하고 앞의 데이터 가 뒤의 데이터 보다 크 면 두 개의 데 이 터 를 교환 합 니 다.
2. 이렇게 배열 의 0 번 째 데 이 터 를 N - 1 번 데 이 터 를 옮 겨 다 니 면 가장 큰 데 이 터 는 배열 의 N - 1 번 째 위치 로 가 라 앉 습 니 다.
3. N = N - 1, N 이 0 이 아니면 앞의 두 단 계 를 반복 합 니 다. 그렇지 않 으 면 정렬 이 완 료 됩 니 다.

void bubble_sort(int array[], int length)
{
    int inner = 0, outer = 0;
    int median = 0;
                                                                                                                                                     
    if(NULL == array || 0 == length)
        return;
                                                                                                                                                     
    for(outer = length-1; outer >= 1; outer --){
        for(inner = 0; inner < outer; inner ++){
            if(array[inner] > array[inner + 1]){
                median = array[inner];
                array[inner] = array[inner + 1];
                array[inner + 1] = median;
            }
        }
    }
}

이러한 알고리즘 에 있어 서 더 많은 사람들 이 완벽 하 다 고 말 할 수 있 지만 개선 할 점 이 없 습 니까?답 은 긍정 적 이다.지금 만약 한 가지 상황 이 순환 중 에 자 리 를 옮 기 는 현상 이 발생 하지 않 았 다 는 것 을 발견 한다 면 이 정렬 이 끝 날 수 있다 고 판단 할 수 있 습 니까?다시 말 하면 우리 가 정렬 해 야 할 데 이 터 는 원래 질서 있 는 수열 이다. 그러면 우 리 는 순서에 따라 한 걸음 한 걸음 진행 할 필요 가 있 습 니까?NO, 우 리 는 당연히 "NO" 라 고 말 해 야 합 니 다!여기까지 말 하면 여러분 들 이 어떻게 해 야 할 지 이미 알 고 계 실 거 라 고 생각 합 니 다. 개 선 된 코드 를 보 세 요.

void bubble_sort(int array[], int length)
{
    int inner = 0, outer = 0;
    int median = 0;
    int flag = 1;  // flag                 
                                                                                                                                              
    if(NULL == array || 0 == length)
        return;
                                                                                                                                              
    for(outer = length-1; outer >= 1 && flag; outer --){
        flag = 0;
                                                                                                                                              
        for(inner = 0; inner < outer; inner ++){
            if(array[inner] > array[inner + 1]){
                median = array[inner];
                array[inner] = array[inner + 1];
                array[inner + 1] = median;
                                                                                                                                              
                if(flag == 0)
                    flag = 1;
            }
        }
    }
}

이렇게 하면 훨씬 완벽 해 지 는 것 같 지 않 아 요!!
둘째, 삽입 정렬
삽입 정렬 은 간단 하고 직관 적 인 정렬 알고리즘 으로 매번 정렬 할 기록 을 키워드 크기 에 따라 앞 에 정렬 된 하위 시퀀스 의 적당 한 위치 에 삽입 하고 모든 기록 이 완 료 될 때 까지 알 고 있다.한 번 정렬 한 후에 최종 위치 에 기록 되 지 않 았 습 니 다. 이것 은 클래스 정렬 방법 을 삽입 하 는 공 통 된 특징 입 니 다.
그 사상 실현 절 차 는 다음 과 같다.
배열 을 a [0... n - 1] 로 설정 합 니 다.
1. 초기 에 a [0] 는 1 개의 질서 구역 을 만 들 었 고 무질서 구역 은 a [1. n - 1] 이다.령 i = 1
2. a [i] 를 현재 의 질서 구역 a [0... i - 1] 에 합병 하여 a [0. i] 의 질서 구간 을 형성한다.
3. i + + 2 단 계 를 i = n - 1 까지 반복 합 니 다.정렬 완료.

typedef int ElemType;
//       int，            
void InsertSort(ElemType A[], int n)
{
    ElemType x;
    for(int i=1;ix)
        {
            A[j+1]=A[j];
            j--;
            if(j < 0)
                break;
        }
        A[j+1]=x;
    }
}

그럼요. while 를 별로 안 좋아 하고 for 를 더 좋아 하 는 친구 들 이 있 습 니 다. 사실은 똑 같 습 니 다. 코드 는 다음 과 같 습 니 다.

void Insertsort3(int a[], int n)
{
    int i, j;
    for (i = 1; i < n; i++)
        for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)
            Swap(a[j], a[j + 1]);
}

여기 서 딴말 을 하기 전에 한 친구 와 이 야 기 를 나 누 었 습 니 다. 그 는 재 귀 에 대해 비교적 두 려 웠 다 고 말 했 습 니 다. 재 귀 가 어떻게 된 일 인지 알 고 있 는 지 없 는 지 알 고 있다 고 말 했 습 니 다. 그리고 저 는 그 에 게 사실 당신 이 매일 재 귀 를 사용 하고 있 습 니 다. 단지 당신 이 주의 하지 않 았 을 뿐 입 니 다. 그 당시 에 그 와 그의 동료 들 은 모두 놀 랐 습 니 다!확실히 그렇다. 우리 가 평소에 사용 하 는 순환 은 바로 재 귀 이다. 물론 우 리 는 여기 서 인 스 턴 스 를 만 들 수 있다. 예 를 들 어 1 에서 n 을 요구 하 는 것 과 우 리 는 보통 아래 와 같이 프로그램 을 쓴다.

int Fun(int n)
{
    int count = 0;
    if(n < 0)
        return -1;
    for(int i = 0; i <= n; i++)
        count += i;
    return count;
}

이것 은 우리 대부분 이 자주 사용 하 는 방법 일 것 이다. 그러면 재 귀 식 을 사용 하 는 것 은 어 떻 습 니까?다음 과 같다.

int Fun(int n)
{
    if(n == 0)
        return 0;
    else
        return Fun(n - 1) + n;
}

이 럴 때 너 는 문득 크게 깨 닫 게 될 거 야, 확실히 그래!!원래 내 옆 에 있 었 는데 하루 종일 누 워 서 쓰 고 있 었 다. 이번 에는 정말 내 동료 들 과 놀 랐 다!
3. 힐 정렬
힐 정렬, 나 는 개인 적 으로 거품 정렬 의 변종 이 라 고 생각한다.그것 의 기본 사상 은 먼저 하나의 서열 에 따라 점차 줄 이 는 방법 에 따라 순 서 를 매 기 는 것 이다.예 를 들 어 10 개의 데이터 가 있 는데 우 리 는 서열 5, 3, 1 의 순서에 따라 정렬 을 한다.먼저 5 이다. 그러면 우 리 는 1 과 6, 2 와 7, 3 과 8, 4 와 9, 5 와 10 을 배열 한다.2 차 는 3 이다. 그러면 데이터 1, 4, 7, 10 을 배열 하고 2, 5, 8 을 배열 하 며 3, 6, 9 를 배열 한다.3 차 는 거품 정렬 과 마찬가지 로 모든 데 이 터 를 배열 한다.그것 의 장점 은 전체 대기 열 을 기본적으로 질서 있 게 하고 데이터 이동 횟수 를 줄 여 알고리즘 의 계산 복잡 도 를 낮 추 는 것 이다.

void shell_sort(int array[], int length, int step)
{
    int inner = 0;
    int outer = 0;
    int median = 0;
                                                                                            
    if(NULL == array || 0 == length)
        return;
                                                                                            
    for(; step >= 1; step -=2){
        for(int index = 0; index < step; index ++){
            if((length -1) < (index + step))
                continue;
            else{
                outer = index + step;
                while( (outer + step) <= (length - 1))
                    outer += step;
            }
                                                                                            
            for(;  outer >= (index + step);  outer -= step){
                for(inner = index; inner <= outer - step; inner += step){
                    if(array[inner] >= array[inner + step]){
                        median = array[inner];
                        array[inner] = array[inner + step];
                        array[inner + step] = median;
                    }
                }
            }
        }
    }
}