Python 정렬 알고리즘 삽입 정렬 및 최적화 방안 상세 설명

1.정렬 삽입
삽입 정렬 은 우리 가 평소에 카드 를 치 는 것 과 매우 비슷 하 다.새로 만 진 카드 를 기 존의 카드 에 적당 한 위치 에 삽입 하고 기 존의 카드 는 질서 가 있다.

1.1 실행 절차

(1)실행 과정 에서 정렬 을 삽입 하면 서열 을 2 부분 으로 나 누고 머리 는 이미 정렬 되 어 있 으 며 꼬리 는 정렬 되 어야 한다.
(2)처음부터 모든 요 소 를 스 캔 하고 한 요 소 를 스 캔 할 때마다 머리 에 적당 한 위치 에 삽입 하여 머리 데 이 터 를 질서 있 게 유지 하도록 한다.
1.2 역순
배열<2,3,8,6,1>의 역순 대 는:<2,1>이다.❤️,1><8,1><8,6><6,1>,총 5 개의 역순 대.
정렬 을 삽입 하 는 시간 복잡 도와 역순 의 수량 은 정비례 관계 가 되 고 역순 의 수량 이 많 을 수록 정렬 을 삽입 하 는 시간 이 많이 소모 된다.
역순 이 적 을 때 정렬 을 삽입 하 는 효율 이 매우 높 고 심지어 속도 가 O nlogn 등급 의 빠 른 정렬 보다 빠르다.
1.3 코드 구현
하나의 요 소 를 배열 의 질서 있 는 앞부분 에 삽입 합 니 다.그 삽 입 된 위치 요 소 는 반드시 이 요소 보다 크 고 이 위치 앞의 요 소 는 이 요소 보다 작 습 니 다(또는 이전 요소 가 없 음).그래서 우 리 는 비 교 를 통 해 이 원 소 를 거품 을 일 으 킬 수 있다.만약 에 앞의 원소 가 나 보다 크 면 위 치 를 교환 하고 그렇지 않 으 면 거품 을 멈 출 수 있다.

def insertion_sort_ver1(array):
    n=len(array)
    for right in range(1,n):
        cur=right
        while cur>0 and array[cur-1]>array[cur]:
            array[cur-1],array[cur]=array[cur],array[cur-1]
            cur-=1

전체 코드:

import numpy as np
import time

#      
def orderCheck(array):
    for i in range(len(array)-1):
        if array[i]>array[i+1]:
            print('    ')
            return
    print('    ')
    
def sort(sort_algorithm,ori_array):
    #       ，     
    array = np.copy(ori_array)
    start=time.clock()
    sort_algorithm(array)
    end=time.clock()
    total_time=float(end-start)
    print(sort_algorithm.__name__+" : %0.5f" % total_time)
    orderCheck(array)

def insertion_sort_ver1(array):
    n=len(array)
    for right in range(1,n):
        cur=right
        while cur>0 and array[cur-1]>array[cur]:
            array[cur-1],array[cur]=array[cur],array[cur-1]
            cur-=1
            
array=np.random.randint(0,10000,2000,dtype=int)
sort(insertion_sort_ver1, array)

소모 시간 은 0.82632 초 입 니 다.
1.4 최적화
거품 에서 앞 뒤 cur 와 cur-1 위치 두 요소 의 위 치 를 교환 하려 면 두 번 의 대 가 를 해 야 합 니 다.그러나 거품 이 계속 되면 cur-1 위치의 요 소 는 cur-2 위치의 요소 로 덮 이기 때문에 두 번 의 대 가 는 무의미 합 니 다.이 를 위해 우 리 는 먼저 삽입 위 치 를 찾 은 다음 에 뒤의 요 소 를 통일 적 으로 이동 할 수 있 습 니 다.또는 거품 이 발생 하 는 과정 에서 한 번 만 값 을 부여 합 니 다(이전 요 소 를 뒤쪽 으로 이동 합 니 다).거품 이 끝 날 때 까지 삽입 위 치 를 확인 한 다음 에 삽입 할 요소 의 삽입 을 진행 합 니 다.

#       
def insertion_sort_ver2(array):
    n=len(array)
    for right in range(1,n):
        cur=right
        elem=array[cur]
        while cur>0 and array[cur-1]>elem:
            array[cur]=array[cur-1]
            cur-=1
        array[cur]=elem

소모 시간 은 0.45987 초 로 눈 에 띄 게 빨 라 졌 다.
최적화
이전에 우 리 는 삽 입 된 위 치 를 찾 을 때 큰 것 부터 작은 것 까지 순서대로 옮 겨 다 니 는 방법 을 사용 했다.질서 있 는 배열 에서 삽 입 된 위 치 를 찾 기 때문에 우 리 는 반드시 찾 는 방법 을 생각 할 것 이다.2 분 찾기.2 분 검색 을 통 해 우 리 는 O(logn)등급 의 비교 와 O(n)등급 의 요소 이동 을 통 해 정렬 작업 을 완성 할 수 있 습 니 다.그 전에 우리 가 진행 한 비교 와 이동 은 모두 O(n)등급 입 니 다.
1.5.1 일반 2 점 찾기
일반적인 2 분 검색 은 매우 간단 합 니 다.중간 위치 요소 의 크기 에 따라 양 단 색인 위 치 를 업데이트 하면 됩 니 다.이 두 단의 색인[left,right)은 왼쪽 닫 고 오른쪽 열 리 는 방식 을 사용 합 니 다.이렇게 요 소 를 찾 지 못 하 는 조건 은 매우 간단 합 니 다.구간 이 왼쪽 닫 히 고 오른쪽 열 리 기 때문에 left def binary_search(array,target):#[left,right) left=0 right=len(array) while left<right:# left<right， ， left==right, right ， middle = (left + right) >> 1 if target<array[middle]: right=middle elif array[middle]<target: left=middle+1 else: return middle return -1 1.5.2 2 점 삽입 위치 찾기
삽입 위치 에 있 는 2 점 찾기 는 일반 2 점 과 다 릅 니 다.여기 서 좌우 점 이동 의 조건 과 이동 방식 을 수정 합 니 다.이 좌우 단점 은 여전히 왼쪽 에서 닫 고 오른쪽 에서 열 립 니 다.만약 에 array[middle]가 요소 target 보다 작 거나 같 으 면 middle 은 위치 삽입 이 불가능 하고 middle 위치의 요소 도 필요 하지 않 습 니 다.left 는 middle+1 이 어야 합 니 다.한편,array[middle]가 target 보다 크 면 middle 은 삽 입 된 위치 일 수 있 습 니 다(삽 입 된 위치 가 target 보다 크 면 이전 요소 가 존재 하면 target 보다 작 아야 합 니 다).middle 을 유지 해 야 하기 때문에 right=middle.그러나 구간 은 왼쪽 닫 고 오른쪽 열 리 며 right 는 취 할 수 없습니다.right=middle 이라도 middle 은 얻 을 수 없 지 않 습 니까?그러나 array[middle]는 어떤 값 을 취하 든(크 든,같 든,작 든)좌우 점 left,right 의 변 화 를 초래 할 것 이다.또한 배열 에서 좌우 점 대표 구간 의 크기 는 계속 줄 어 들 고 최종 적 으로 좌우 점 이 겹 치 며 이때 의 위 치 는 삽 입 된 위치 이다.
다음은 찾 은 예제 입 니 다.





코드 는 다음 과 같 습 니 다:

def binary_search(array,index):
    left=0
    right=index
    while left<right:
        middle=(left+right)>>1
        if array[middle]>array[index]:#    ，        ， right  
            right=middle
        else:#    ，        ，  left middle+1
            left=middle+1
    return left #       

1.5.3 2 분 의 삽입 정렬 사용
삽입 위 치 를 찾 으 면 위치 뒤의 요 소 를 이동 하고 요 소 를 삽입 하면 됩 니 다.

#            ，        
def insertion_sort_ver3(array):
    n=len(array)
    for right in range(1,n):
        index=binary_search(array,right)
        elem=array[right]
        for i in range(right,index,-1):
            array[i]=array[i-1]
        array[index]=elem

이전 삽입 정렬 보다 속도 가 높 아 졌 음 을 알 수 있 습 니 다.
1.6 시간 공간 복잡 도
최 악,평균 시간 복잡 도:O(n^2),최 적 시간 복잡 도:O(n),공간 복잡 도:O(1).
1.7 안정성
정렬 을 삽입 하면 뒤의 요 소 를 뒤에서 앞으로 삽입 하고 뒤쪽 과 같은 요 소 는 왼쪽 과 같은 요소 의 오른쪽 에 삽입 합 니 다.원래 의 위 치 를 바 꾸 지 않 고 안정 적 인 정렬 에 속 합 니 다.
파 이 썬 정렬 알고리즘 의 삽입 정렬 및 최적화 방안 에 대한 상세 한 설명 은 여기까지 입 니 다.더 많은 파 이 썬 삽입 정렬 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 바 랍 니 다!