Java에서 간단한 정렬을 구현하는 방법

정렬은 데이터 처리에서 매우 일반적이고 핵심적인 작업이지만 실제 프로젝트 개발에서 수동으로 구현해야 할 가능성은 적습니다. 결국 각 언어 클래스에는 여러 정렬 알고리즘이 구현되어 있습니다. 도서관. 그러나 이러한 미묘한 개념을 이해하는 것은 여전히 ​​우리에게 큰 유익이 됩니다. 이 기사에서는 가장 기본적인 세 가지 유형의 알고리즘인 선택, 버블링 및 삽입을 간략하게 검토합니다.

먼저 정렬 중에 호출할 수 있는 배열 요소를 교환하는 함수를 정의합니다.

/**
     * 交换数组元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a,int b){
        arr[a] = arr[a]+arr[b];
        arr[b] = arr[a]-arr[b];
        arr[a] = arr[a]-arr[b];
    }

간단한 선택 정렬

간단한 선택 정렬은 가장 간단하고 직관적인 알고리즘입니다. 기본 아이디어는 데이터 요소에서 가장 작은 값을 선택하는 것입니다. 각 패스에서 정렬되는(또는 가장 큰) 요소는 모든 요소가 정렬될 때까지 첫 번째 요소로 사용됩니다. 단순 선택 정렬은 불안정한 정렬입니다.

알고리즘이 구현되면 최소 요소가 결정될 때마다 지속적인 비교 및 ​​교환을 통해 첫 번째 위치가 현재 최소값이 됩니다. 교환은 상대적으로 시간이 많이 걸리는 작업입니다. 실제로 현재의 최소 요소가 완전히 결정되기 전에는 이러한 교환이 의미가 없다는 것을 쉽게 알 수 있습니다. 각 비교에 대해 더 작은 요소의 배열 첨자만 저장하도록 변수 min을 설정할 수 있습니다. 루프가 끝나면 이 변수는 현재 가장 작은 요소의 첨자를 저장한 다음 교환 작업을 수행합니다. 코드 구현은 매우 간단합니다. 살펴보겠습니다.

코드 구현

/**
     * 简单选择排序
     *
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;//每一趟循环比较时，min用于存放较小元素的数组下标，这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标，避免每次遇到较小元素都要进行交换。
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            //进行交换，如果min发生变化，则进行交换
            if (min != i) {
                swap(arr,min,i);
            }
        }
    }

위에서 단순 선택 정렬을 최적화한 후에는 교환 작업을 위해 배열의 원래 배열에 관계없이 비교 횟수가 변경되지 않습니다. 가장 좋은 경우 배열이 완전히 정렬되면 교환 이동이 없습니다. , 최악의 경우, 즉 배열이 역순일 경우 교환 횟수는 n-1입니다. 정리하자면, 시간 복잡도는 O(n2)

버블 정렬

버블 정렬의 기본 아이디어는 인접한 요소를 쌍으로 비교하고 이를 역순으로 교환하는 것입니다. 이렇게 하면 각 패스에서 가장 작은 값을 얻게 됩니다. 또는 가장 큰 요소가 맨 위로 "떠서" 마침내 완전한 순서에 도달합니다

코드 구현

버블 정렬 과정에서 배열과 같은 교환 작업 없이 특정 패스가 완료되면 [5,4 ,1,2,3], 두 개의 버블링을 실행한 후, 즉 두 개의 외부 루프를 수행한 후 5와 4가 각각 최종 위치 [1,2,3,4,5]로 조정됩니다. 이때 세 번째 루프를 실행한 후 단일 교환이 수행되지 않았습니다. 이는 나머지 시퀀스가 ​​이미 순서대로 정렬되어 있으며 코드를 살펴보겠습니다

/**
     * 冒泡排序
     *
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true;//设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已然完成。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j+1);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

에 따르면. 위 위험 버블 구현에서는 원래 배열 자체가 정렬된 경우(최상의 경우) n-1개 비교만 완료할 수 있습니다. 역순인 경우 비교 횟수는 n-1+n-2+입니다. ..+1=n (n-1)/2, 교환 횟수와 비교 횟수는 동일합니다. 따라서 시간 복잡도는 여전히 O(n2)입니다. 전반적으로 버블 정렬의 성능은 위의 선택 정렬보다 여전히 약간 나쁩니다.

직접 삽입 정렬

직접 삽입 정렬의 기본 아이디어는 모든 요소가 삽입될 때까지 각 단계에서 이전에 정렬된 순서대로 정렬할 레코드를 삽입하는 것입니다.

코드 구현

/**
     * 插入排序
     *
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                swap(arr,j,j-1);
                j--;
            }
        }
    }

간단한 삽입 정렬 최선의 경우 요소 교환 없이 n-1번 비교해야 하며, 최악의 경우 시간 복잡도는 O(n)입니다. 여전히 O(n2)입니다. 그러나 배열 요소가 무작위로 배열된 경우 삽입 정렬이 위의 두 정렬보다 여전히 좋습니다.

위 내용은 Java에서 간단한 정렬을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!