버블 정렬 방법에 대한 자세한 설명

버블 정렬 방법

HTML5 Academy-Coder: 이번 호에서는 계속해서 알고리즘인 버블 정렬 방법을 소개합니다. 버블 정렬 알고리즘은 비교적 간단하고 사용하기 쉬우며 비교적 안정적이며 이해하기 쉬우며 면접관들이 자주 질문하는 알고리즘 중 하나입니다.

Tips: "알고리즘"과 "정렬"에 대한 기본 지식은 이전 "선택 정렬 방법"에서 자세히 설명했습니다. 기사 마지막에 해당 기사 링크를 클릭하면 볼 수 있습니다. 여기서 반복하지 마세요.

버블 정렬의 원리

기본 원리

시퀀스의 선두부터 탐색을 시작하여 2개씩 비교하고 전자가 후자보다 크면 마지막으로 가장 큰 숫자(이 정렬에서 가장 큰 숫자)가 될 때까지 위치를 바꿉니다. ) 순서가 지정되지 않은 시퀀스의 끝으로 교체되어 순서가 지정된 시퀀스의 일부가 됩니다.

다음 번에 순회할 때 이전 순회 이후의 최대 숫자는 더 이상 정렬에 참여하지 않습니다.

이 작업을 여러 번 반복합니다. 순서 정렬이 완료되었습니다.

정렬 과정에서 작은 숫자는 항상 앞쪽에 배치되고, 큰 숫자는 뒤쪽에 배치되는 현상이 마치 거품이 점차 위로 떠오르는 것과 유사하기 때문에 이를 버블 정렬이라고 합니다.

원리 다이어그램

팁: 파란색은 정렬 라운드에서 교환 대기를 나타내고, 검은색은 이번 정렬에서 교환이 완료되었음을 나타내며, 빨간색은 정렬이 완료되었음을 나타냅니다.

버블링 단계 분해

루프에 사용 정렬 횟수 결정하기

정렬할 순서에 숫자가 하나만 남으면 순서를 결정할 수 있으므로 따로 정렬할 필요가 없으므로 정렬 횟수는 순서 길이 – 1이 됩니다.

정렬별 비교 횟수를 제어하세요

정렬별로 시퀀스의 여러 숫자를 쌍으로 비교해야 하며, for 문을 사용하여 다중 비교를 구현해야 합니다. 이 for 루프는 정렬된 시간의 for 루프 내에 중첩됩니다(이중 for 중첩 형성).

팁: j는 len - i - 1보다 작게 설정해야 합니다. i를 빼는 이유는 정렬된 숫자가 더 이상 비교에 포함되지 않기 때문입니다. 1을 빼는 이유는 배열 첨자 인덱스 때문입니다. 값은 0부터 시작합니다.

핵심 기능 - 쌍을 비교하고 상황에 따라 위치를 교환합니다

두 숫자의 크기를 비교하여 전자가 후자보다 크면 값을 교환합니다.

버블 정렬 방법 전체 코드

버블 정렬 방법 최적화

시퀀스의 데이터가 [0, 1, 2, 3, 4, 5];

위를 사용하세요. 버블 정렬 방법 버블 정렬로 얻은 결과에는 확실히 문제가 없습니다. 그러나 정렬할 순서가 순서대로 되어 있으므로 이론적으로 정렬을 순회할 필요는 없습니다.

현재 알고리즘은 초기 순서가 올바른지 여부에 관계없이 순회 정렬을 수행하므로 효율성이 상대적으로 낮으므로 현재 정렬 알고리즘을 최적화해야 합니다.

다음 알고리즘에서는 각 정렬 전에 스왑 변수가 도입되어 false로 초기화됩니다. 두 숫자가 위치를 교환하면 이를 true로 설정합니다.

각 정렬이 끝나면 swap이 false인지 확인합니다. 거짓이면 해당 시퀀스가 ​​정렬되었거나 시퀀스 자체가 정렬된 시퀀스이며 다음 정렬이 수행되지 않음을 의미합니다.

이 방법을 통해 불필요한 비교와 위치 교환이 줄어들어 알고리즘의 성능이 더욱 향상됩니다.

버블 정렬 방법의 효율성

시간 복잡도

최상의 상태: 정렬되는 시퀀스 자체가 정렬된 시퀀스입니다. 최적화된 코드에 따르면 정렬 횟수는 n-1번이라고 결론을 내릴 수 있습니다. , 그리고 시간 복잡성은 O(n)입니다.

최악의 경우: 정렬할 순서가 역순이므로 1 + 2 +3...(n - 1) = n(n - 1)/2회

시간 복잡도는 O(n^2)입니다.

공간 복잡도

버블 정렬 방법은 요소의 위치를 ​​교환하기 위해 추가 공간(임시 변수)이 필요하므로 공간 복잡도는 O(1)입니다.

알고리즘의 안정성

인접한 요소가 같으면 위치를 바꿀 필요가 없고, 같은 요소의 순서도 바뀌지 않으므로 안정적인 정렬입니다.

O란 무엇인가요? !

시간 복잡도는 문제의 크기가 계속 증가함에 따라 알고리즘의 시간 증가 곡선을 더 정확하게 설명합니다. 따라서 이러한 크기 증가는 정확한 성능 평가가 아니며 근사치로 이해될 수 있습니다. (공간 복잡도도 마찬가지입니다.)

O(n?)은 n이 클 때 복잡도가 Cn?와 거의 같다는 것을 의미합니다. 간단히 말해서, n이 충분히 크면 n이 선형이 되기 때문에 C는 특정 상수입니다. 성장 복잡성은 2차적으로 증가합니다.

O(n)은 n이 매우 클 때 복잡도가 Cn과 거의 같고 C는 특정 상수라는 의미입니다. 즉, n이 선형적으로 증가함에 따라 복잡성도 선형 규모로 증가합니다.

O(1)은 n이 클 때 기본적으로 복잡성이 증가하지 않는다는 것을 의미합니다. 즉, n이 선형적으로 증가함에 따라 복잡성은 n의 영향을 받지 않고 일정한 수준(여기서 상수는 1)을 따라 증가합니다.

팁: 그림에서 O(1)은 X축에 가까워서 명확하게 보이지 않습니다.

팁: 이 사진은 "Stack Overflow" 웹사이트에서 가져온 것입니다.

관련 기사 링크

정렬 방법 선택

매일 행복하세요

삶이 힘들고 코딩도 쉽지 않지만, 웃는 것도 잊지 마세요!

위 내용은 버블 정렬 방법에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!