Python 거품 정렬 알고리즘 구현

1466 단어 Python
거품 정렬 (bubble sort):
  • 원리:
  • 반복 적 으로 정렬 할 수열 을 옮 겨 다 니 며 한 번 에 두 요 소 를 비교 합 니 다. 만약 에 우리 가 지정 한 조건 을 만족 시 키 지 않 으 면 두 요소 의 위 치 를 교환 하고 옮 겨 다 닐 때 까지 이 알고리즘 이름 의 유래 는 작은 요소 일수 록 수열 의 맨 위 에 천천히 떠 있 기 때 문 입 니 다
    • .
  • 거품 정렬 알고리즘 은 다음 과 같다.
  • 모든 인접 요소 에 대해 똑 같은 일 을 하고 마지막 에 마지막 요소 가 가장 크다
    • .
  • 모든 요소 에 대해 상기 절 차 를 반복 하고 마지막
    • 을 제외 합 니 다.
  • 매번 점점 적어 지 는 요소 에 대해 위의 절 차 를 반복 하고 그 어떠한 대수 도 비교 할 필요 가 없 을 때 까지
  • 서로 인접 한 요 소 는 오름차 가 있 을 때 첫 번 째 가 두 번 째 보다 크 면 이 두 요소 의 위치
    • 를 교환 합 니 다.
  • 그 시간 복잡 도:
  • 가장 좋 은 시간 복잡 도: O (n) (한 번 에 교환 할 수 있 는 요소 가 없 음 을 발견 하고 정렬 이 끝 났 음 을 나타 낸다.)
  • 최 악의 시간 복잡 도: O (n2)
  • 안정성: 안정
  • 코드 는 다음 과 같다. 
    • #!/usr/bin/python3
# coding=utf-8
def bubble_sort(a_list):
    """    """
    n = len(a_list)
    #               
    for i in range(n-1):
        # i: [0, 1, 2, ...n-2]
        count = 0
        #              
        for j in range(0, n-1-i):
            if a_list[j] > a_list[j+1]:
                a_list[j], a_list[j+1] = a_list[j+1], a_list[j]
                count += 1
        if 0 == count:
            break


if __name__ == '__main__':
    list1 = [54, 26, 77, 17, 77, 31, 44, 55, 20]
    print('   :%s' % list1)
    bubble_sort(list1)
    print('   :%s' % list1)


#     :
   :[54, 26, 77, 17, 77, 31, 44, 55, 20]
   :[17, 20, 26, 31, 44, 54, 55, 77, 77]

    python 함수 설명 (1)
    mex 외부 라이브러리 호출 방법(OpenCV의 경우)

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage