고전 알고리즘 --- 정렬 insert - ort 삽입
7688 단어 알고리즘
알고리즘 서론 에서 '알고리즘 분석' 1 절 은 '정렬 삽입' 을 예 로 들 어 분석 한 것 으로 이미 명확 하 게 분석 되 었 다. 가장 좋 은 상황 에서 순 서 를 배열 한 상황 에서 외층 순환 만 있 기 때문에 시간 복잡 도 는 O (n) O (n) O (n) O (n) O (n) 이지 만 만약 에 역순 이 라면 시간 복잡 도 는 O (n 2) O (n ^ 2) O (n2) O (n2) 이다.
생각:
정렬 할 패 를 가 져 오고 정렬 된 패 (왼쪽 에서 오른쪽으로 순서대로 커지 기) 의 맨 오른쪽 패 와 크기 를 비교 합 니 다. 만약 에 맨 오른쪽 패 가 정렬 할 패 보다 크다 면 정렬 된 패 는 그 보다 작은 패 를 찾 아 오른쪽 에 삽입 할 때 까지 뒤로 이동 합 니 다.
int insert_sort(int a[], int len)
{
int i, j, key;
for(j = 1; j < len; j++)// 0 。 。
{
key = a[j];
i = j-1;
while(i >= 0 && a[i] > key)
{
a[i+1] = a[i];
i--;
}
a[i+1] = key;
}
return 0;
}
import random
# 、 list
def arr_init(len=10):
lst = [random.randrange(100) for i in range(len)]
return lst
def insert_sort(alist):
list1 = alist
for index, value in enumerate(list1):
if index==0:
continue
key = value
i = index-1
while(i>=0 and list1[i]>key):
list1[i+1]=list1[i]
i-=1
list1[i+1]=key
#
def insert_sort_test():
list1 = arr_init(10)
print(" :", list1)
insert_sort(list1)
print(" :", list1)
if __name__ == '__main__':
#1、
insert_sort_test()
출력 : [6, 6, 75, 33, 74, 28, 17, 55, 43, 63]
: [6, 6, 17, 28, 33, 43, 55, 63, 74, 75]
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.