정렬 알고리즘 - 정렬 삽입 (C 언어 구현)

의 원리
기본 배열 의 첫 번 째 데 이 터 는 질서 있 는 배열 이 있 습 니 다. 데이터 가 하나 밖 에 없 기 때문에 질서 있 는 대기 열 이 분명 합 니 다.난서 배열 의 두 번 째 위치 부터 이전의 질서 있 는 배열 의 데이터 와 순서대로 비교 하여 적당 한 위 치 를 찾 아 이 데 이 터 를 질서 있 는 배열 에 삽입 하고 마지막 데 이 터 를 질서 있 는 배열 에 삽입 하여 정렬 이 끝 날 때 까지 합 니 다.
  분석 하 다.
최 악의 경우 질서 있 는 배열 의 데 이 터 는 작업 을 삽입 할 때마다 한 번 씩 비교 되 기 때문에 최 악의 경우 이 정렬 알고리즘 의 시간 복잡 도 는 O (n2) 이다.가장 좋 은 상황 에서 데 이 터 는 기본적으로 질서 가 있 고 그 시간 복잡 도 는 O (n) 이다.원래 배열 에서 작 동 하기 때문에 공간 복잡 도 는 O (1) 이다.
  개선 하 다.
어떤 숫자 를 질서 있 는 배열 에 삽입 할 때 이분법 으로 이 숫자의 적당 한 삽입 위 치 를 찾 을 수 있 습 니 다.
C 언어 구현 (원본 삽입 정렬)
void swap(void *a, void *b, int size)
{
    void *tmp = Malloc(size);
    memcpy(tmp, a, size);
    memcpy(a, b, size);
    memcpy(b, tmp, size);
    free(tmp);
}
Boolean insert(int *arr, int arrlen)
{
    int i = 0, j = 0;

    if(NULL == arr || 0 >= arrlen){
        printf("Invalid input...
");         return FALSE;     }          for(i = 1; i =0; --j){             if(arr[j+1] 



좋은 웹페이지 즐겨찾기