Java 배열에 요소를 삽입하고 빠르게 정렬하는 방법

1. 배열의 두 번째 요소에서 연산합니다. 앞에 있는 요소가 그보다 크다면 cur가 가리키는 요소가 이전 요소보다 크거나 같을 때까지 앞에 있는 요소를 뒤로 이동합니다. . 이때 cur 가리키는 위치 는 삽입할 요소가 삽입되어야 하는 위치입니다.

static int[] insertSort2(int[] array){
 
    int len = array.length;
 
    for (int begin = 1; begin < len; begin++){
 
        int cur = begin;
 
        int tmp = array[cur];
 
        while (cur > 0 && array[cur] < array[cur-1]){
 
            array[cur] = array[cur-1];
 
            cur--;
 
        }
 
        array[cur] = tmp;
 
    }
 
    return array;
 
}

2. 이진 검색은 비교 횟수, 즉 cmp 함수 호출 횟수를 줄이고, 스왑 함수 호출 횟수도 줄입니다. 현재 요소를 삽입해야 할 위치를 찾아 이동하는 것이 더 빠르므로 효율성이 향상됩니다.

static int[] insertSort3(int[] array){
 
        int len = array.length;
 
 
 
        for (int begin = 1; begin < len; begin++){
 
            int v = array[begin];
 
            int insertIndex = search(array,begin);
 
            // 将 [insertIndex, begin) 范围内的元素往右边挪动一个单位
 
            for (int i = begin; i > insertIndex; i--){
 
                array[i] = array[i-1];
 
            }
 
            array[insertIndex] = v;
 
        }
 
        return array;
 
    }
 
    static int search(int[] array, int index){
 
        int begin = 0;
 
        int end = index;
 
        while(begin < end){
 
            int mid = (begin+end) >> 1;
 
            if (array[index] < array[mid]){
 
                end = mid;
 
            }else{
 
                begin = mid+1;
 
            }
 
        }
 
        return begin;
 
}

위 내용은 Java 배열에 요소를 삽입하고 빠르게 정렬하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!