정렬 알고리즘: 삽입 정렬 및 쉘 정렬

오늘은 두 가지 고전적인 정렬 방법인 삽입 정렬과 쉘 정렬에 대해 이야기하겠습니다. 쉘 정렬은 삽입 정렬의 업그레이드 버전으로 생각할 수 있습니다.

Insertion Sort

Insertion-Sort의 알고리즘 설명은 매우 간단하고 직관적인 정렬 알고리즘입니다. 복잡성은 버블 정렬과 유사합니다. 작동 원리는 정렬되지 않은 데이터의 경우 정렬된 시퀀스의 뒤에서 앞으로 스캔하여 해당 위치를 찾아 삽입하는 것입니다.

인터넷에서 다음과 같은 애니메이션을 찾았습니다.

과정은 다음과 같습니다.

• 정렬되었다고 간주할 수 있는 첫 번째 요소부터 시작합니다.

• 다음 요소를 꺼냅니다. 요소가 정렬된 후 요소 순서를 뒤에서 앞으로 스캔합니다.

• (정렬된) 요소가 새 요소보다 큰 경우 요소를 다음 위치로 이동합니다.

• 3단계를 반복합니다. 새 요소의 위치보다 작거나 같은 정렬된 요소를 찾습니다.

• 새 요소를 이 위치에 삽입한 후

• 2~5단계를 반복합니다.

코드 구현(여기서는 C 언어를 사용함):

void insort (int arr[], int len)
{
    int i,current,preindex;
    for (i = 1; i < len; i++) {
        preindex = i - 1;
        current = arr[i];
        while (preindex >= 0 && current < arr[preindex]) {
            arr[preindex + 1] = arr[preindex];
            preindex --;
        }
        arr[preindex + 1] = current;
    }
}

쉘 정렬

삽입 정렬을 이해하고 나면 쉘 정렬을 이해하기 쉽습니다.

쉘 정렬 알고리즘은 D.L. Shell이 ​​1959년에 발명했습니다. 기본 아이디어는 멀리 있는 요소를 먼저 비교하여 많은 수의 무질서한 상황을 신속하게 줄여 후속 작업을 쉽게 만드는 것입니다. 비교된 요소 사이의 거리는 1로 줄어들 때까지 점차적으로 감소하며, 이때 정렬은 인접한 요소의 교환이 됩니다.

힐 정렬은 테이블의 특정 증분에 따라 레코드를 그룹화하고, 증분이 점차 감소함에 따라 직접 삽입 정렬 알고리즘을 사용하여 각 그룹에 포함되는 키워드가 1로 감소하는 것입니다. 전체 파일이 하나의 그룹으로 나누어지고 알고리즘이 종료됩니다.

프로세스 데모(이 사진은 온라인에서도 찾을 수 있음):

코드 구현(여기서는 C 언어가 사용됨):

void shell_sort (int arr[], int len)
{
    int gap,i,current,preindex;
    for (gap = len / 2; gap > 0; gap /= 2) {
        for (i = gap; i < len; i++) {
            preindex = i - gap;
            current = arr[i];
            while (preindex >= 0 && current < arr[preindex]) {
                arr[preindex + gap] = arr[preindex];
                preindex -= gap;
            }
            arr[preindex + gap] = current;
        }
    }
}

위 내용은 정렬 알고리즘: 삽입 정렬 및 쉘 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!