Python 에서 실 현 된 더미 정렬 알고리즘 예시
쌓 아 올 리 는 사상:쌓 아 올 리 는 것 은 일종 의 데이터 구조 로 쌓 아 올 리 는 것 을 완전한 이 진 트 리 로 볼 수 있다.이 이 진 트 리 는 만족 하고 그 어떠한 비 엽 노드 의 값 도 좌우 아이의 노드 의 값 보다 크 지 않다(또는 작 지 않다).하나의 무질서 한 서열 을 하나의 더미 로 조정 하면 이 서열 의 최대 값(또는 최소 값)을 찾 을 수 있다.그리고 찾 은 이 값 을 서열 의 마지막 값 으로 교환 하면 질서 있 는 서열 은 요소 가 하 나 를 증가 하고 무질서 한 서열 요 소 는 하 나 를 줄 이 며 새로운 무질서 한 서열 에 대해 이런 조작 을 반복 하면 정렬 을 실현 할 수 있다.
쌓 기 정렬 의 실행 과정:
1.무질서 한 서열 에 의 해 확 정 된 완전 이 진 트 리 의 첫 번 째 비 잎 노드 부터 시작 하여 오른쪽 에서 왼쪽,아래 에서 위로 모든 노드 를 조정 하면 최종 적 으로 큰 지붕 더 미 를 얻 을 수 있다.
노드 를 조정 하 는 방법:현재 노드(a 로 가정)의 값 과 아이 노드 를 비교 하고 a 보다 큰 값 의 아이 노드 가 존재 하면 그 중에서 가장 큰 하 나 를 선택 하여 a 와 교환 합 니 다.a 가 다음 층 에 올 때 상기 과정 을 반복 하고 a 의 아이 노드 의 값 이 a 보다 작 을 때 까지 반복 합 니 다.
2.현재 무질서 서열 중의 첫 번 째 요소(숫자 에 반 영 된 것 은 루트 노드 b)를 무질서 서열 중의 마지막 요소 와 교환(c 로 가정)하고 b 는 질서 있 는 서열 에 들 어가 최종 위치 에 도착한다.무질서 서열 요 소 는 1 개 감소 하고 질서 있 는 서열 요 소 는 1 개 증가 합 니 다.이때 노드 c 만 더미 의 정 의 를 만족 시 키 지 못 하고 이 를 조정 할 수 있 습 니 다.
3.무질서 한 서열 의 요소 가 하나 남 을 때 까지 2 의 과정 을 반복 합 니 다.
# -*- coding:utf-8 -*-
#
from collections import deque
# 1
# ,
# 0 0,
L = deque([49,38,65,97,76,13,27,49])
L.appendleft(0)
#L = [0,49,38,65,97,76,13,27,49]
def element_exchange(numbers,low,high):
temp = numbers[low]
# j low (cheer!)
i = low
j = 2*i
while j<=high:
# , j
if j<high and numbers[j]<numbers[j+1]:
j = j+1
if temp<numbers[j]:
# numbers[j]
numbers[i] = numbers[j]
i = j
j = 2*i
else:
break
#
numbers[i] = temp
def top_heap_sort(numbers):
length = len(numbers)-1
#
#
#
# cheer up!
first_exchange_element = length/2
#
print first_exchange_element
for x in range(first_exchange_element):
element_exchange(numbers,first_exchange_element-x,length)
# ,
# length-1
for y in range(length-1):
temp = numbers[1]
numbers[1] = numbers[length-y]
numbers[length-y] = temp
element_exchange(numbers,1,length-y-1)
if __name__=='__main__':
top_heap_sort(L)
for x in range(1,len(L)):
print L[x],
실행 결과:PS:정렬 에 관 한 프 리 젠 테 이 션 도 구 를 추천 합 니 다.참고 하 시기 바 랍 니 다.
온라인 애니메이션 프레젠테이션 삽입/선택/거품/병합/힐/빠 른 정렬 알고리즘 프로 세 스 도구:
http://tools.jb51.net/aideddesign/paixu_ys
Python 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 논문 에서 말 한 것 이 여러분 의 Python 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Python의 None과 NULL의 차이점 상세 정보그래서 대상 = 속성 + 방법 (사실 방법도 하나의 속성, 데이터 속성과 구별되는 호출 가능한 속성 같은 속성과 방법을 가진 대상을 클래스, 즉 Classl로 분류할 수 있다.클래스는 하나의 청사진과 같아서 하나의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.