C 언어 거품 정렬 & 정렬 선택 & 정렬 삽입

시험 이 필요 하기 때문에 최근 에 C 언어 를 조금 보고 C 언어 에서 흔히 볼 수 있 는 3 대 정렬 알고리즘 을 간단하게 정리 했다.
거품 정렬
거품 서열 에 대해 서 는 주로 인접 수 두 개 를 비교 하 는 사상 을 사용한다.다음 이 이전 보다 크 거나 작다 고 가정 하면 모든 숫자 가 다 비교 될 때 까지 위 치 를 바 꿉 니 다.n 크기 의 배열 을 지정 하면 비교 n-1 번 이 필요 합 니 다. 매번 비교 n-1-i 번, i 는 지난번 순환 에서 이미 비교 한 다음 표 시 를 표시 합 니 다.두 개의 순환 판단 을 쓰 고 교환 이 필요 하 다 면 교환 하고 교환 이 필요 하지 않 으 면 다음 두 개의 수 를 비교 하여 모든 수 를 비교 할 때 까지 한다.

//          
void bubbleSort(int *a, int len) {
    int i, j, temp, count1 = 0, count2 = 0;
    for (i = 0; i < len; i++) {
        for (j = 0; j < len - i - 1; j++) {
            count1++;
            if (a[j] > a[j + 1]) { //                ，       
                count2++;
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
    printf("      %d    , %d    ", count1, count2);
}

int main() {
    int i;
    int nums[10] = {10, 20, 8, 3, 5, 2, 23, 53, 12, 45};
    int len = sizeof(nums) / sizeof(int);

    printf("     : ");
    for (i = 0; i < len; i++) {
        printf("%d ", nums[i]);
    }
    bubbleSort(nums, len);
    printf("
");
    printf("     : ");
    for (i = 0; i < len; i++) {
        printf("%d ", nums[i]);
    }
}

정렬 선택
정렬 을 선택 할 때 먼저 배열 의 첫 번 째 요 소 를 최대 또는 최소 로 가정 합 니 다.이 때 세 개의 변 수 를 이용 하여 요소 의 아래 표 시 를 표시 해 야 합 니 다.하 나 는 현재, 찾 은 최대 또는 최소 의 아래 표 시 를 표시 합 니 다. 하 나 는 순환 할 때마다 최대 값 을 저장 하 는 아래 표 시 를 표시 합 니 다.가장 큰 하 표를 찾 으 면 매번 가장 큰 하 표를 부여 합 니 다.찾 은 후에 가설 한 현재 값 이 이번 순환 의 최대 치 인지 판단 하고 그렇지 않 으 면 최대 와 현재 의 값 을 교환 하여 배열 을 일정한 순서 로 배출 합 니 다.

void choiceSort(int *a, int len) {
    int i, j, temp, min, minIndex, count1 = 0, count2 = 0;
    for (i = 0; i < len; i++) {
        min = a[i]; //    
        minIndex = i;  //      
        for (j = i + 1; j < len; j++) {
            count1 ++;
            if (a[j] < min) { //            ，               min 
                count2 ++;
                min = a[j];
                minIndex = j;
            }
            //     
            temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
    printf("      %d    , %d    ", count1, count2);
}



int main() {
    int i;
    int nums[10] = {10, 20, 8, 3, 5, 2, 23, 53, 12, 45};
    int len = sizeof(nums) / sizeof(int);

    printf("     : ");
    for (i = 0; i < len; i++) {
        printf("%d ", nums[i]);
    }
    choiceSort(nums, len);
    printf("
");
    printf("     : ");
    for (i = 0; i < len; i++) {
        printf("%d ", nums[i]);
    }
}

삽입 정렬
정렬 을 삽입 하면 현재 기본 적 으로 질서 있 는 일부 배열 을 추출 한 다음 에 이 부분 배열 의 가장 오른쪽 에 있 는 요소 의 오른쪽 요 소 를 표시 합 니 다. 이 요 소 를 앞의 기본 적 인 질서 있 는 배열 과 비교 하여 그 보다 조금 큰 요 소 를 찾 고 그 보다 조금 큰 요소 앞으로 이동 합 니 다. 나머지 정렬 되 지 않 은 요 소 는 상기 작업 을 반복 합 니 다.정렬 끝 난 거 알 아 요.그래서 정렬 을 삽입 하 는 시간 복잡 도 는 그의 기본 적 인 질서 있 는 부분의 크기 와 관련 이 있다. 만약 에 배열 이 역순 이 라면 그의 시간 복잡 도 는 심지어 거품 정렬 보다 높 지 않다.

void insertSort(int *a, int len) {
    int i, j, temp, count1 = 0, count2 = 0;
    for (i = 1; i < len; i++) {
        j = i - 1;
        temp = a[i];    //       
        while (temp < a[j] && j >=0) {  //              
            count2 ++;
            a[j+1] = a[j];  //                
            j --;
        }
        count1 ++;
        a[++j] = temp; //     
    }
    printf("      %d    , %d    ", count1, count2);
}

int main() {
    int i;
    int nums[10] = {10, 20, 8, 3, 5, 2, 23, 53, 12, 45};
    int len = sizeof(nums) / sizeof(int);

    printf("     : ");
    for (i = 0; i < len; i++) {
        printf("%d ", nums[i]);
    }
    insertSort(nums, len);
    printf("
");
    printf("     : ");
    for (i = 0; i < len; i++) {
        printf("%d ", nums[i]);
    }
}

적용 필드

거품 정렬: 데이터 양 이 적은 정렬 장면 에 적 용 됩 니 다. 거품 원리 가 간단 하기 때 문 입 니 다

정렬 선택: 대부분의 정렬 장면 에 적용 된다. 비록 그의 비교 횟수 가 비교적 많 지만 데이터 양 이 많 을 때 그의 효율 은 거품 보다 현저히 좋 고 데이터 이동 은 시간 이 많이 걸 리 며 정렬 이동 횟수 가 적다.

삽입 정렬: 삽입 정렬 은 기 존 데이터 의 질서 있 는 상황 에 적용 되 고 질서 있 는 부분 이 클 수록 좋 습 니 다.

================================================================================
읽 어 주 셔 서 감사합니다.
당신 보다 우수한 사람 은 반드시 당신 보다 노력 하고, 당신 보다 노력 한 사람 은 반드시 당신 보다 우수 하 다 는 것 을 기억 하 세 요.
================================================================================