C 언어 버블 정렬 알고리즘 및 코드

버블 정렬은 명확한 아이디어와 간결한 코드를 갖춘 정렬 알고리즘으로 대학생을 위한 컴퓨터 강좌에서 자주 사용됩니다.

"버블"이라는 이름은 더 큰 요소가 교환을 통해 시퀀스의 맨 위로 천천히 "부유"한다는 사실에서 유래되었습니다.

작은 것부터 큰 것 순으로 정렬하는 예입니다.

기본 아이디어 및 예제

버블 정렬의 기본 아이디어는 인접한 두 숫자를 지속적으로 비교하여 더 큰 요소가 계속 뒤로 이동하도록 하는 것입니다. 한 번의 비교 후에는 가장 큰 숫자가 선택되고, 두 번째 비교 후에는 두 번째로 큰 숫자가 선택됩니다.

다음은 버블정렬 3 2 4 1에 대한 설명입니다.

1차 분류 과정
3 2 4 1(초기)
2 3 4 2(3과 2를 비교, 교환)
2 3 4 1(3과 4를 비교하지 않음) Swap)
2 3 1 4 (4와 1 비교, swap)
첫 번째 라운드가 끝났고, 가장 큰 숫자인 4가 이미 끝에 있으므로 두 번째 정렬에서는 처음 세 숫자만 비교하면 됩니다. 다시.

2차 분류 과정
2 3 1 4(1차 분류 결과)
2 3 1 4(2와 3 비교, 교환 없음)
2 1 3 4(3 비교) 그리고 1, 교환
두 번째 라운드가 종료되고, 두 번째로 큰 숫자가 마지막에서 두 번째로 순위가 매겨졌으므로 세 번째 라운드에서는 처음 두 요소만 비교하면 됩니다.

세 번째 정렬
2 1 3 4 (2차 정렬 결과)
1 2 3 4 (2와 1 비교, 교환)
정렬이 끝났습니다

요약 및 구현 알고리즘

N개의 요소가 있는 배열 R[n]의 경우 최대 N-1 라운드의 비교를 수행합니다.

첫 번째 라운드에서는 (R[1], R[ 2]) 하나씩, (R[2], R[3]), (R[3], R[4]), …. (R[N-1], R[N]); R[N] 으로 이동됩니다.

두 번째 라운드에서는 (R[1], R[2]), (R[2], R[3]), (R[3]을 비교합니다. , R[4]), .... (R[N-2], R[N-1]); 전체 배열이 될 때까지 두 번째로 큰 요소가 R[N-1]로 이동됩니다.

버블 정렬의 일반적인 구현과 최적화된 구현은 배열 정렬 여부에 관계없이 1회 비교를 수행합니다. 최적화된 구현은 배열이 정렬되면 비교를 조기에 종료하여 알고리즘의 시간 복잡도를 줄입니다

#include<stdio.h>
#include<stdlib.h>

#define N 8

void bubble_sort(int a[],int n);


//一般实现
void bubble_sort(int a[],int n)//n为数组a的元素个数
{
//一定进行N-1轮比较
for(int i=0; i<n-1; i++)
{
//每一轮比较前n-1-i个，即已排序好的最后i个不用比较
for(int j=0; j<n-1-i; j++)
{
if(a[j] > a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1]=temp;
}
}
}
}

//优化实现
void bubble_sort_better(int a[],int n)//n为数组a的元素个数
{
//最多进行N-1轮比较
for(int i=0; i<n-1; i++)
{
bool isSorted = true;
//每一轮比较前n-1-i个，即已排序好的最后i个不用比较
for(int j=0; j<n-1-i; j++)
{
if(a[j] > a[j+1])
{
isSorted = false;
int temp = a[j];
a[j] = a[j+1];
a[j+1]=temp;
}
}
if(isSorted) break; //如果没有发生交换，说明数组已经排序好了
}
}


int  main()
{
int num[N] = {89, 38, 11, 78, 96, 44, 19, 25};

bubble_sort(num, N); //或者使用bubble_sort_better(num, N);

for(int i=0; i<N; i++)
printf("%d  ", num[i]);

printf("\n");


system("pause");
return 0;
}

C언어 버블정렬 알고리즘 및 코드에 대한 더 많은 글은 PHP 중국어 홈페이지

를 참고해주세요.