데이터 구조의 python 삽입 정렬 실현 (InsertionSort)

1 정렬 사상 삽입
첫 번 째 숫자 가 질서 가 있다 고 생각 하고 뒤에서 하나의 수 를 꺼 내 앞 과 질서 가 있 습 니 다. * 핵심: * * 후속 데 이 터 를 해당 하 는 위치 에 어떻게 삽입 합 니까?
  • 질서 있 는 서열 을 구축 하여 정렬 되 지 않 은 서열 의 요 소 를 순서대로 추출 하고 정렬 된 서열 에서 뒤로 비교 하여 해당 하 는 위 치 를 찾 아 삽입 합 니 다.
  • 뒤에서 앞으로 스 캔 하 는 과정 에서 정렬 된 요 소 를 뒤로 옮 겨 최신 요소 에 삽입 공간 을 제공 해 야 합 니 다.
  • 2 코드 구현
        def InsertionSort(li):
            n = len(li)
            #         ,       ,        
            for j in range(1,n):
                #     , 1  n-1  
                #            ,      ,   
                for i in range(j,0,-1):
                    if li[i] < li[i-1]:
                        li[i],li[i-1] = li[i-1],li[i]
                    else:
                        break
        
        if __name__ == '__main__':
            li = [3,1,4,5,2]
            ss = InsertionSort(li)
            print(li)
    
    

    3 복잡 도 분석
  • 안정성: 안정 적 이 고 데이터 가 인접 교환 이 아니라면 모두 불안정 하 다
  • 최 악의 시간 복잡 도 O (n ^ 2)
  • 최 우선 시간 복잡 도 O (n) 순환 최 외층, 내층 매번 break
  • 4 응용 장면
    데이터 가 대부분 질서 가 있 으 면 삽입 정렬 효율 이 가장 높다.
    이상 의 내용 은 개인의 총 결 을 대표 하 는 것 일 뿐 입 니 다. 잘못된 점 이 있 으 면 비판 하고 지적 해 주 십시오. 여러분 이 함께 공부 하 는 것 을 환영 합 니 다!

    좋은 웹페이지 즐겨찾기