Java 정렬 InsertionSort 삽입 정렬 예

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

처음으로 클럽 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

성능 분석　최악의 시나리오는 매번 뽑는 카드가 가장 작다는 것입니다. 이때 매번 tail에서 head까지 순회해야 합니다. 시간은 N^2에 비례합니다

　가장 좋은 상황은 정리가 되었다는 것입니다. 이미 정리되어 있기 때문입니다. 따라서 매번 뽑는 카드를 정렬할 필요가 없습니다. 시간은 N에 비례합니다

위 내용은 Java 정렬 InsertionSort 삽입 정렬 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!