무차별 대입을 사용하여 버블 정렬 해결

버블 정렬은 무차별 방식의 또 다른 고전적인 구현입니다.

알고리즘 아이디어: 목록에서 인접한 요소를 비교하고 역순이면 위치를 바꿉니다. 여러 번 반복한 후에 가장 큰 요소가 마지막에 순위가 매겨집니다. 두 번째 작업은 두 번째 요소를 두 번째 위치로 이동하고 n-1번까지 비교를 계속하여 전체 목록이 정렬됩니다.

다음은 내 코드 구현입니다. C++

으아악

알고리즘 분석: 입력의 크기는 N에 의해 ​​완전히 결정됩니다. 기본 연산은 비교입니다: Arr[j]>Arr[j+1], 시간 복잡도 C(n)=Θ(n2).

그러나 키 교환 횟수는 특정 입력에 따라 다릅니다. 이때, 키 교환 횟수 = 키 비교 횟수 = Θ(n2)입니다.

그러나 일부 입력 상황에서 목록을 비교한 후 요소의 위치가 교환되지 않으면 목록이 이미 순서대로 정렬되어 있으므로 알고리즘을 중지할 수 있습니다. 구체적인 개선 버전은 다음과 같습니다.

으아악

그러나 최악의 경우에도 시간 복잡도는 여전히 Θ(n2)입니다.

위 내용은 무차별 대입을 사용하여 버블 정렬 해결의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!