빠른 정렬 알고리즘 이해(Java 예제 포함)

QuickSort 알고리즘에 대한 자세한 설명: 효율적인 정렬 도구

QuickSort는 분할 정복 전략을 기반으로 하는 효율적인 정렬 알고리즘입니다. 분할 정복 방법은 문제를 더 작은 하위 문제로 분해하고 이러한 하위 문제를 개별적으로 해결한 다음 하위 문제의 솔루션을 결합하여 최종 솔루션을 얻는 방법입니다. 빠른 정렬에서는 배열의 분할 지점을 결정하는 파티션 요소를 선택하여 배열을 나눕니다. 분할하기 전에 분할 요소의 위치는 자신보다 큰 요소 앞, 작은 요소 뒤가 되도록 재배열됩니다. 왼쪽 및 오른쪽 하위 배열은 각 하위 배열에 단 하나의 요소만 포함될 때까지 이러한 방식으로 반복적으로 분할되며, 이 지점에서 배열이 정렬됩니다.

빠른 정렬 작동 방식

예를 들어 다음 배열을 오름차순으로 정렬해 보겠습니다.

1단계: 피벗 요소 선택

마지막 요소를 피벗으로 선택합니다.

2단계: 피벗 요소 재배열

피벗 요소는 그보다 큰 요소 앞과 그보다 작은 요소 뒤에 배치됩니다. 이를 위해 배열을 반복하고 피벗을 그 이전의 각 요소와 비교합니다. 피벗보다 큰 요소가 발견되면 해당 요소에 대한 두 번째 포인터를 만듭니다.

피벗보다 작은 요소가 발견되면 두 번째 포인터로 바꿉니다.

이 프로세스를 반복하여 피벗보다 큰 다음 요소를 두 번째 포인터로 설정하고 피벗보다 작은 요소가 발견되면 교체합니다.

배열 끝에 도달할 때까지 이 프로세스를 계속하세요.

요소 비교가 완료된 후 피벗보다 작은 요소가 오른쪽으로 이동한 다음 피벗을 두 번째 포인터로 바꿉니다.

3단계: 배열 나누기

파티션 인덱스에 따라 배열을 나눕니다. 배열을 arr[start..end]으로 표현하면 배열을 파티션으로 나누어 왼쪽 하위 배열 arr[start..partitionIndex-1]을 얻을 수 있고 오른쪽 하위 배열 arr[partitionIndex 1..end].

각 하위 배열에 하나의 요소만 포함될 때까지 이런 방식으로 하위 배열을 계속 나눕니다.

이 시점에서 배열이 정렬되었습니다.

빠른 정렬 코드 구현

import java.util.Arrays;

public class QuickSortTest {
    public static void main(String[] args){
        int[] arr = {8, 6, 2, 3, 9, 4};
        System.out.println("未排序数组: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println("已排序数组: " + Arrays.toString(arr));
    }

    public static int partition(int[] arr, int start, int end){
        // 将最后一个元素设置为枢轴
        int pivot = arr[end];
        // 创建指向下一个较大元素的指针
        int secondPointer = start-1;

        // 将小于枢轴的元素移动到枢轴左侧
        for (int i = start; i < end; i++){
            if (arr[i] < pivot){
                secondPointer++;
                // 交换元素
                int temp = arr[secondPointer];
                arr[secondPointer] = arr[i];
                arr[i] = temp;
            }
        }
        // 将枢轴与第二个指针交换
        int temp = arr[secondPointer+1];
        arr[secondPointer+1] = arr[end];
        arr[end] = temp;
        // 返回分区索引
        return secondPointer+1;
    }

    public static void quickSort(int[] arr, int start, int end){
        if (start < end){
            // 找到分区索引
            int partitionIndex = partition(arr, start, end);
            // 递归调用快速排序
            quickSort(arr, start, partitionIndex-1);
            quickSort(arr, partitionIndex+1, end);
        }
    }
}

코드 해석

quickSort 메서드: 먼저 partition 메서드를 호출하여 배열을 두 개의 하위 배열로 나눈 다음 quickSort를 재귀적으로 호출하여 왼쪽 및 오른쪽 하위 배열을 정렬합니다. 이 프로세스는 모든 하위 배열에 정확히 하나의 요소가 포함될 때까지 계속되며, 이 시점에서 배열이 정렬됩니다.

partition 방법: 배열을 두 개의 하위 배열로 나누는 역할을 담당합니다. 먼저 피벗과 포인터를 다음으로 큰 요소로 설정한 다음 배열을 반복하여 피벗보다 작은 요소를 왼쪽으로 이동합니다. 그런 다음 피벗을 두 번째 포인터로 바꾸고 파티션 위치를 반환합니다.

위 코드를 실행하면 콘솔에 다음이 출력됩니다.

정렬되지 않은 배열: [8, 6, 2, 3, 9, 4] 정렬된 배열: [2, 3, 4, 6, 8, 9]

시간복잡도

최상의 경우(O(n log n)): 피벗이 배열을 매번 거의 동일한 두 부분으로 분할할 때 최상의 경우가 발생합니다.

평균 사례(O(n log n)): 평균 사례에서 피벗은 배열을 동일하지 않은 두 부분으로 분할하지만 재귀 깊이와 비교 횟수는 여전히 n log n에 비례합니다.

최악의 경우(O(n²)): 피벗이 항상 배열을 매우 불평등한 부분으로 분할할 때 최악의 경우가 발생합니다(예: 한 부분에는 요소가 하나만 있고 다른 부분에는 n-1 요소가 있음). 예를 들어 배열을 역순으로 정렬하고 피벗을 제대로 선택하지 않은 경우 이런 일이 발생할 수 있습니다.

공간 복잡도(O(log n)): 퀵 정렬은 일반적으로 내부에서 구현되며 추가 배열이 필요하지 않습니다.

위 내용은 빠른 정렬 알고리즘 이해(Java 예제 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!