Java에서 일반적으로 사용되는 정렬 알고리즘과 구현 방법에 대한 자세한 설명

1. 선택 정렬

선택 정렬은 어떤 데이터를 입력하더라도 시간 복잡도는 O(n²)인 간단하고 직관적인 정렬 알고리즘입니다. 따라서 사용할 때에는 데이터 크기가 작을수록 좋습니다. 유일한 장점은 추가 메모리 공간을 차지하지 않는다는 점일 수 있습니다. 먼저 정렬되지 않은 시퀀스에서 가장 작은(큰) 요소를 찾아 정렬된 시퀀스의 시작 위치에 저장합니다.

정렬되지 않은 나머지 요소 중에서 가장 작은(큰) 요소를 계속 찾아 정렬된 순서의 마지막에 배치합니다.

모든 요소가 정렬될 때까지 두 번째 단계를 반복하세요.

public static void selectSort(int[] arr) {
        //选择排序
        if(arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int minValueIndex = i;
            for (int j = i+1; j < n; j++) {
                minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
            }
            swap(arr,i,minValueIndex);
        }
    }
    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] arr = {7,5,1,9,4,2,6};
        printArray(arr);
        selectSort(arr);
        printArray(arr);
    }

2. 버블 정렬

**버블 정렬 알고리즘의 원리는 다음과 같습니다. **

1. 첫 번째 것이 두 번째 것보다 크면 둘 다 교환하세요.

2. 처음의 첫 번째 쌍부터 끝의 마지막 쌍까지 인접한 요소의 각 쌍에 대해 동일한 작업을 수행합니다. 이때 마지막 요소가 가장 큰 숫자가 되어야 합니다.

3. 마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다.

4. 비교할 숫자 쌍이 없어질 때까지 매번 요소 수를 줄여 위 단계를 계속 반복합니다.

public static void bubbleSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = n-1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                }
            }
        }
    }
     public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void main(String[] args) {
        int[] arr = {14,6,3,10,2};
        printArray(arr);
        bubbleSort(arr);
        printArray(arr);
    }

3. 삽입 정렬

삽입 정렬은 정렬할 요소 중 첫 번째 n-1(n>=2) 숫자가 이미 순서대로 정렬되어 있다고 가정하고 이제 n번째 숫자를 삽입하는 것을 의미합니다. 이전에 정렬되었던 순서를 찾아 적절한 위치를 찾으면 n번째 숫자가 삽입된 순서도 정렬됩니다. 전체 순서가 정해질 때까지 이 방법에 따라 모든 요소를 ​​삽입하는 과정을 삽입 정렬

public static void insertSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int currIndex = i;
            while(currIndex - 1 >= 0 && arr[currIndex-1] > arr[currIndex]) {
                swap(arr,currIndex,currIndex-1);
                currIndex--;
            }
        }
    }

    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void main(String[] args) {
        int[] arr = {3,6,1,5,2};
        printArray(arr);
        insertSort(arr);
        printArray(arr);
    }

삽입 정렬 최적화

public static void insertSort1(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            for (int j = i-1; j >= 0; j--) {
                if(arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                }else {
                    break;
                }
            }
        }
    }

이라고 합니다.

위 내용은 Java에서 일반적으로 사용되는 정렬 알고리즘과 구현 방법에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!