고전 알고리즘 --- 정렬 insert - ort 삽입

7688 단어 알고리즘
시간 복잡 도: O (n 2) O (n ^ 2) O (n2)
알고리즘 서론 에서 '알고리즘 분석' 1 절 은 '정렬 삽입' 을 예 로 들 어 분석 한 것 으로 이미 명확 하 게 분석 되 었 다. 가장 좋 은 상황 에서 순 서 를 배열 한 상황 에서 외층 순환 만 있 기 때문에 시간 복잡 도 는 O (n) O (n) O (n) O (n) O (n) 이지 만 만약 에 역순 이 라면 시간 복잡 도 는 O (n 2) O (n ^ 2) O (n2) O (n2) 이다.
생각:
정렬 할 패 를 가 져 오고 정렬 된 패 (왼쪽 에서 오른쪽으로 순서대로 커지 기) 의 맨 오른쪽 패 와 크기 를 비교 합 니 다. 만약 에 맨 오른쪽 패 가 정렬 할 패 보다 크다 면 정렬 된 패 는 그 보다 작은 패 를 찾 아 오른쪽 에 삽입 할 때 까지 뒤로 이동 합 니 다.
  • C 언어 실현
    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;
    }
    
  • Python 구현
    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]
    
  • 좋은 웹페이지 즐겨찾기