8 대 정렬 의 직접 삽입 정렬

1702 단어
  • 우리 가 처음에 접 한 순 서 는 바로 순 서 를 삽입 하 는 것 이다. 순 서 는 매우 간단 해 보인다. 그러나 그의 세부 사항 을 알 지 못 하면 자신 이 손 으로 순 서 를 삽입 하 는 것 도 여러 가지 잘못 이 생 길 수 있다. 심지어 쓰 지 못 할 수도 있다. 답 을 보고 문득 깨 달 았 다. 오, 그리고 다음 에 도 쓸 수 없다. 말 할 필요 도 없 이 본인 은 이런 상황 을 몇 번 겪 었 다.따라서 간단 하지만 이 가장 기본 적 인 알고리즘 을 제대로 알 아야 한다.

  • 처리 방법
  • 초기 상태: n 개 요소 의 배열 이 정렬 되 어야 합 니 다. 교체 지침 은 처음에 두 번 째 요소 (아래 표 시 는 1) 이 고 이 요 소 를 key 로 설정 합 니 다. key 왼쪽 요 소 는 초기 에 질서 가 있 고 이해 하기 쉽 습 니 다. 처음에 key 왼쪽 에 하나의 요소 만 있 고 하나의 요 소 는 질서 가 있 기 때 문 입 니 다.
  • 교체 상태: key 를 왼쪽 에 질서 있 는 배열 에 삽입 한 다음 에 포인터 오른쪽 으로 한 자 리 를 옮 깁 니 다.
  • 종료 상태: 전체 배열 의 마지막 자리 에 바늘 을 교체 하고 마지막 자 리 를 왼쪽 에 해당 하 는 위치 에 삽입 하여 정렬 이 완료 되 었 습 니 다.

  • 세부 처리
  • 우 리 는 가장 간단 한 정수 로 정렬 하여 예 를 들 자
  • c 는 정수 배열 입 니 다. 변수 i 는 1 부터 len (c) 까지 의 배열 아래 표 시 를 표시 합 니 다. 초기 에는 i = 1, key = c [i] = c [1], 변수 j 는 key 왼쪽 에 질서 있 는 배열 의 아래 표 시 를 표시 합 니 다. 초기 에는 j = 0, c [j] = c [0]
  • 우 리 는 이중 순환 으로 이 정렬 을 처리 해 야 한다. 외층 순환 의 상하 계 는 1 과 len (c) 이 고 왼쪽 에 정렬 된 배열 의 상하 계 는 0 과 j
  • 이다.
  • 다음 코드:
  • c = []
    for i in range(5):
        item = int(raw_input("     :"))
        c.append(item)
    
    length = len(c)
    for i in range(1, length):
        j = i - 1
        key = c[i]
        while j >= 0:
            if key < c[j]:
                c[j], c[j + 1] = c[j + 1], c[j]
            j -= 1
    
    print c
    

    외층 순환 은 앞에서 뒤로 1 - len (c) 을 교체 하고, 내층 순환 은 뒤에서 0 - j 를 교체 하 며, key 가 c [j] 보다 작 으 면 c [j] 와 c [j + 1], j - = 1 을 교환 합 니 다.
    ps
  • python 으로 이 정렬 을 실현 합 니 다. 인터넷 에는 많은 튜 토리 얼 이 있 습 니 다. c [j] 와 c [j + 1] 를 교환 할 때 중간 변 수 를 도 입 했 습 니 다. 예 를 들 어 c 언어, 두 값 을 교환 할 때 중간 변 수 를 도입 해 야 합 니 다. 그러나 python 에 서 는 직접 교환 할 수 있 습 니 다. 위 에 python 이 라 고 쓰 여 있 습 니 다.
  • 좋은 웹페이지 즐겨찾기