정렬 알고리즘 (3) 정렬 직접 삽입

1. 정렬 알고리즘 직접 삽입
1. 정렬 알고리즘 (Straight Insertion Sort) 을 직접 삽입 하 는 기본 동작 은 하나의 기록 을 정렬 된 질서 표 에 삽입 하여 새로운 기록 수 에 하 나 를 추가 하 는 질서 표를 얻 는 것 입 니 다.그것 은 정렬 을 삽입 하 는 방법 에 속한다.
2. 다음 과 같은 코드 를 실현 합 니 다.

#include <stdio.h>

//          
typedef int RecordType;

/**
 *            i   j         
 */
void Swap(RecordType *rs, int i, int j)
{
    RecordType tmp = *(rs + i);
    *(rs + i) = *(rs + j);
    *(rs + j) = tmp;
}
/**
 *          
 */
void PrintRs(RecordType rs[])
{
    int i, count = rs[0];

    for (i = 1; i <= count; i++)
    {
        printf("%d ", rs[i]);
    }
    printf("
");
}

/**
 *              
 */
void StraightInsertionSort(RecordType *rs)
{
    int i, j, count = rs[0];
    for (i = 2; i <= count; i++)
    {
        if (*(rs + i) < *(rs + i - 1))
        {
            *rs = *(rs + i);   //    0          
            for (j = i - 1; *(rs + j) > *rs; j--)  //  j=1 ，          ，         ，             j >= 1   
            {
                *(rs + j + 1) = *(rs + j);
            }
            *(rs + j + 1) = *rs;
        }
    }
    *rs = count;   //     0           
}

int main()
{
    RecordType rs[] = {5, 1, 5, 3, 2, 4};
    printf("          ：\t\t");
    PrintRs(rs);
    StraightInsertionSort(rs);
    printf("       ，       ：");
    PrintRs(rs);
    return 0;
}

3. 시간 복잡 도
공간의 복잡 도 측면 에서 볼 때, 그것 은 기록 의 보조 공간 (아래 표 시 된 0 의 위치) 만 필요 하 다.시간 복잡 도 측면 에서 볼 때 가장 좋 은 상황 은 정렬 할 기록 목록 자체 가 질서 가 있다 는 것 이다. 그러면 n - 1 차 비교 만 할 뿐 이동 하지 않 고 시간 복잡 도 는 O (n) 이다.최 악의 경 우 는 정렬 대기 목록 이 거꾸로 배열 되 어 있 습 니 다. 이때 2 + 3 +... + n = (n + 2) (n - 1) / 2 회 를 비교 해 야 합 니 다. 기 록 된 이동 횟수 는 최대 치 3 + 4 +... + (n + 1) = (n + 4) (n - 1) / 2 회 에 달 합 니 다.따라서 정렬 기록 이 무 작위 라면 확률 이 같은 원칙 에 따라 평균 비교 와 이동 횟수 는 약 (n ^ 2) / 4 회 이 므 로 정렬 알고리즘 을 직접 삽입 하 는 시간 복잡 도 는 O (n ^ 2) 입 니 다.마찬가지 로 O (n ^ 2) 의 시간 복잡 도 입 니 다. 정렬 알고리즘 을 직접 삽입 하 는 것 이 거품 알고리즘 과 정렬 알고리즘 을 간단하게 선택 하 는 것 보다 성능 이 좋 습 니 다.
참고서: 《 큰소리 데이터 구 조 》