Java에서 빠른 정렬 알고리즘을 구현한다는 아이디어는 무엇입니까?

1. 퀵 정렬 알고리즘이란?

사실 퀵 정렬(Quicksort)은 버블 정렬을 개선한 것입니다.

2. 빠른 정렬 알고리즘의 아이디어

한 번의 정렬을 통해 정렬할 데이터를 두 개의 독립적인 부분으로 나눈 다음 이를 사용합니다. 데이터를 정렬하는 방법 두 부분의 데이터를 개별적으로 신속하게 정렬하고 전체 정렬 프로세스를 반복적으로 수행하여 전체 데이터가 정렬된 시퀀스가 ​​되도록 할 수 있습니다.

(추천 영상 튜토리얼: java 영상 튜토리얼)

3. 구현 아이디어

(1) 첫 번째 키워드 K 1 을 제어어로 사용하고, [K 1 ,K 2 ,…,K n ]을 다음과 같이 나눕니다. 두 개의 하위 영역, 왼쪽 영역의 모든 키워드를 K 1 이하로 만들고, 오른쪽 영역의 모든 키워드를 K 1 이상으로 만들고, 마지막으로 제어 단어를 중앙의 적절한 위치에 배치합니다. 두 개의 하위 영역. 하위 영역의 데이터는 여전히 정렬되지 않은 상태입니다. ;

(2) 왼쪽 영역을 전체적으로 처리하여 (1)의 단계를 사용하여 처리하고 오른쪽 영역에도 동일한 처리를 수행합니다. (즉, 재귀)

(3) 왼쪽 영역이 처리될 때까지 (1), (2) 단계를 반복합니다.

4. 구현 코드

static void quicksort(int n[], int left, int right) {
        int dp;
        if (left < right) {
            dp = partition(n, left, right);
            quicksort(n, left, dp - 1);
            quicksort(n, dp + 1, right);
        }
    }
 
    static int partition(int n[], int left, int right) {
        int pivot = n[left];
        while (left < right) {
            while (left < right && n[right] >= pivot)
                right--;
            if (left < right)
                n[left++] = n[right];
            while (left < right && n[left] <= pivot)
                left++;
            if (left < right)
                n[right--] = n[left];
        }
        n[left] = pivot;
        return left;
    }

추천 튜토리얼: java 입력 프로그램

위 내용은 Java에서 빠른 정렬 알고리즘을 구현한다는 아이디어는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!