Java 정렬 InsertionSort 삽입 정렬 예-java지도 시간-php.cn

Java 정렬 InsertionSort 삽입 정렬 예

黄舟

풀어 주다： 2017-09-16 10:34:20

원래의

1635명이 탐색했습니다.

삽입 정렬은 이중 버클과 같은 내기와 같습니다. 카드를 뽑을 때, 한 번에 한 장씩 가져와서 이 카드를 이전 카드와 하나씩 비교하세요. 이 카드를 삽입할 위치를 선택하고 순서를 정한 후 카드를 보다 원활하게 플레이하세요. 그렇지 않으면 하나씩 찾는 것이 번거로울 것입니다. 이는 또한 카드 놀이의 전반적인 상황에 도움이 되지 않습니다. 아래 그림을 보세요

처음으로 클럽 7개를 그린다고 가정하면 정렬할 필요가 없습니다. 카드는 하나뿐이니까

　 그럼 클럽 10개

를 그렸어요. 10은 7보다 크므로 정렬할 필요가 없습니다.

　 그럼 계속해서 카드를 뽑아보세요. 5개의 클럽을 그린 것을 발견했습니다 . 이때는 망설이지 마세요. 2시는 정말 별거 아니거든요. 결정적인 접기

그럼 5와 10을 비교해보겠습니다. 5는 10보다 작으므로 장소를 바꿔보세요.

5를 선택하고 7과 비교하세요. 5는 7보다 작습니다. 따라서 를 얻으려면 5와 7의 위치를 바꾸세요.

　이때 이미 정리가 되어있습니다. 원리는 이렇습니다.

　비교적 간단하기 때문이죠. 코드를 직접 붙여넣으세요

// O(n^2) 最坏的情况
    // 最好的情况 O(n)
    public static void sort(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            for (int j = i ; j > 0; j--) {
                if (less(a[j], a[j - 1])) 
                    exch(a, j, j - 1);
                else
                    break;
            }
        }
    }
    
    public static void sort(Comparable[] a, int low, int hi) {
        for (int i = low; i <= hi ; i++) {
            for (int j = i ; j > low; j--) {
                if (less(a[j], a[j - 1])) 
                    exch(a, j, j - 1);
                else
                    break;
            }
        }
    }

InsertSort

로그인 후 복사