정렬 알고리즘 소개: 버블 정렬

개발 중에는 일련의 데이터를 순서대로 정렬해야 하는 경우가 많으므로 여러 가지 또는 그 이상의 정렬 알고리즘을 반드시 숙지해야 합니다.

이 기사에서는 정렬을 소개합니다. 더 간단한 알고리즘 중 하나: 버블 정렬

먼저 가장 간단한 아이디어를 사용하여 정렬을 구현해 보고 버블 정렬을 비교하고 배우십시오.

문제: 크기가 10인 배열 내의 데이터가 있는 배열이 있다고 가정합니다. 요소(int str[10])는 순서가 없습니다. 이제 이 정렬되지 않은 배열을 작은 것부터 큰 것까지 정렬된 배열(아래 첨자 0부터 시작)로 프로그래밍해야 합니다.

아이디어: 질문의 요구 사항에 따르면 올바른 결과는 다음과 같아야 한다는 데는 의심의 여지가 없습니다. 1 2 3 4 5 6 7 8 9 10 이렇게 하려면 가장 간단하고 직접적으로 생각할 수 있는 방법은 비교하고 교환하는 것입니다.

먼저 10개의 숫자 중 가장 작은 숫자를 첨자가 0인 위치에 놓습니다(str[0]).

비교하여 표시된 숫자를 교환합니다. 0(str[0])으로 나머지 9개의 숫자(아래 첨자 0이 있는 위치에 더 작은 숫자 배치)를 사용하여 10개 중에서 가장 작은 숫자를 얻을 수 있습니다.

가장 작은 10개의 숫자가 결정된 후 , 다음 단계는 나머지 9개의 가장 작은 숫자를 찾는 것입니다.

최소 숫자가 정해져 있으므로 str[0]을 건드리지 말고 str[1]부터 바로 시작해서 나머지 8개 숫자와 비교하고 교환한 뒤 9개 숫자 중 가장 작은 숫자를 찾아보세요. 아래 첨자 1이 있는 위치에 있는 숫자(str[1])

이 아이디어를 계속 따르면 이 10개의 숫자를 순서가 지정된(작은 것부터 큰 것까지) 배열로 바꿀 수 있습니다

코드:

#include <stdio.h>  
  
void swap(int *a, int *b); //交换两个数  
  
int main()  
{  
    int     str[10];  
    int     i, j;  
    //初始化数组为10 9 8 7 6 5 4 3 2 1  
    for (i = 0; i < 10; i++)  
    {  
        str[i] = 10 - i;  
    }  
    //排序，从a[0]开始排，从小到大  
    for (i = 0; i < 10; i++)  
    {  
        for (j = i + 1; j < 10; j++)  
        {  
            if (str[i] > str[j])  
            {  
                swap(&str[i], &str[j]);  
            }  
        }  
    }  
        //将十个数输出  
    for (i = 0; i < 10; i++)  
        printf("%d\n", str[i]);  
    return    0;  
}  
void swap(int *a, int *b)  
{  
    int     c;  
     c = *a;  
    *a = *b;  
    *b =  c;  
}

이 방법이 생각하기 쉽습니다. 하지만 단점이 있습니다. 원래 앞쪽에 있던 더 작은 숫자가 뒤쪽으로 바뀌었습니다.

시연:

시작: 9 4 5 6 8 3 2 7 10 1 (아래 첨자는 왼쪽에서 오른쪽으로 각각 0~9입니다.) 위의 절차에 따라 비교하고 교환하세요

처음 : 4 9 5 6 8 3 2 7 10 1

두 번째 : 4 9 5 6 8 3 2 7 10 1

. . . : (교환 없음)

5번째 : 3 9 5 6 8 4 2 7 10 1

6번째 : 2 9 5 6 8 3 4 7 10 1

. . . : (교환 없음)

10번째 : 1 9 5 6 8 3 4 7 10 2

한 번 교환하면 원래 작은 숫자가 앞에 오는 것을 알 수 있습니다. 그러면 뒤쪽에 넣어주세요

그럼 이 단점을 어떻게 해결할까요? 버블 정렬을 사용할 수 있습니다

버블 정렬이란 무엇인가요?

이렇게 이해할 수 있습니다. (작은 것부터 큰 것까지 정렬) 다양한 크기의 버블 10개가 있고, 작은 버블을 아래에서 위로 점차적으로 위쪽으로 이동하여 한 번 순회한 후 가장 작은 버블이 는 맨 위(첨자 0)까지 올라갔다가 다시 아래에서 위로 올라가며 10개의 거품이 순서대로 나타날 때까지 순환이 계속됩니다.

버블 정렬에서 가장 중요한 아이디어는 둘을 비교하고 더 작은 것을 승격시키는 것입니다.

버블 정렬의 최악의 시간 복잡도는 O(n²)

코드:

#include <stdio.h>  
void swap(int *a, int *b);  
int main()  
{  
    int    array[10] = {15, 225, 34, 42, 52, 6, 7856, 865, 954, 10};  
    int    i, j;  
    for (i = 0; i < 10; i++)  
    {  
        //每一次由底至上地上升  
        for (j = 9; j > i; j--)  
        {  
            if (array[j] < array[j-1])  
            {  
                    swap(&array[j], &array[j-1]);  
            }  
        }  
    }  
    for (i = 0; i < 10; i++)  
    {  
        printf("%d\n", array[i]);  
    }  
    return    0;  
}  
void swap(int *a, int *b)  
{  
    int    temp;  
    temp = *a;  
      *a = *b;  
      *b = temp;  
}

버블 정렬 알고리즘은 더 작은 숫자를 위로만 점진적으로 밀어올리므로 기사 앞부분에서 언급한 단점이 발생하지 않으므로 여기서는 설명하지 않습니다.

정렬 알고리즘 및 버블 정렬 시작과 관련된 더 많은 기사를 보려면 PHP 중국어 웹사이트를 주목하세요!