버블 정렬-PHP开发-php.cn

버블 정렬

高洛峰

풀어 주다： 2016-12-19 13:18:19

원래의

1480명이 탐색했습니다.

1. 알고리즘 설명

버블 정렬: 인접한 데이터를 순서대로 비교하여 앞에는 작은 데이터, 뒤에는 큰 데이터를 넣습니다. 즉, 첫 번째 패스에서 1번째와 2번째를 비교합니다. 숫자가 마지막이고 소수가 첫 번째이고, 두 번째 숫자를 세 번째 숫자와 비교하고, 큰 숫자가 마지막이고, 소수가 첫 번째입니다. 그런 식으로 가장 큰 숫자가 두 번째 숫자로 "롤링"됩니다. 한 번 통과하면 다음으로 큰 숫자가 끝에서 두 번째 위치로 스크롤됩니다. n-1(n은 순서가 지정되지 않은 데이터 수) 통과로 정렬이 완료될 수 있습니다.

다음 5개의 정렬되지 않은 데이터를 예로 들어 보겠습니다.

40 8 15 18 12(이 기사에서는 첫 번째 패스의 비교 프로세스만 자세히 설명합니다.)

1차 패스: 8 15 18 12 40

버블 정렬

두 번째 여행: 8 15 12 18 40

세 번째 여행: 8 12 15 18 40

4차 여행: 8 12 15 18 40

2. 알고리즘 분석

평균 시간 복잡도: O(n2)

공간 복잡도: O(1)( 교환에 사용됨) )

안정성: 안정적

3. 알고리즘 구현

//交换data1和data2所指向的整形  
void DataSwap(int* data1, int* data2)  
{  
    int temp = *data1;  
    *data1 = *data2;  
    *data2 = temp;  
}  
  
/******************************************************** 
*函数名称：BubbleSort 
*参数说明：pDataArray 无序数组； 
*          iDataNum为无序数据个数 
*说明：    버블 정렬 
*********************************************************/  
void BubbleSort(int* pDataArray, int iDataNum)  
{  
    for (int i = 0; i < iDataNum - 1; i++)   //走iDataNum-1趟  
        for (int j = 0; j < iDataNum - i - 1; j++)      
            if (pDataArray[j] > pDataArray[j + 1])  
                DataSwap(&pDataArray[j], &pDataArray[j + 1]);  
}

로그인 후 복사

4. 알고리즘 최적화

도 버블 정렬 알고리즘 수행 가능 비교 중에 교환이 있는지 여부를 표시를 사용하여 기록합니다. 교환이 없으면 전체 배열이 순서대로 정렬 프로세스를 종료한 것입니다. 그렇지 않으면 다음 비교를 계속합니다.

/******************************************************** 
*函数名称：BubbleSort 
*参数说明：pDataArray 无序数组； 
*          iDataNum为无序数据个数 
*说明：    버블 정렬 
*********************************************************/  
void BubbleSort(int* pDataArray, int iDataNum)  
{  
    BOOL flag = FALSE;    //记录是否存在交换  
    for (int i = 0; i < iDataNum - 1; i++)    //走iDataNum-1趟  
    {  
        flag = FALSE;  
        for (int j = 0; j < iDataNum - i - 1; j++)      
            if (pDataArray[j] > pDataArray[j + 1])  
            {  
                flag = TRUE;  
                DataSwap(&pDataArray[j], &pDataArray[j + 1]);  
            }  
          
        if (!flag)    //上一趟比较中不存在交换，则退出排序  
            break;  
    }  
}

로그인 후 복사

더 많은 버블정렬 관련 글은 PHP 중국어 홈페이지를 주목해주세요!