초급 정렬 알고리즘

초급 정렬 알고리즘
먼저 두 가지 개념 을 소개 한다.

내부 정렬: 정렬 작업 은 메모리 에서 완료 할 수 있 습 니 다

외부 정렬: 데이터 양 이 너무 많아 메모리 에서 완성 할 수 없고 디스크 에서 완성 해 야 할 정렬

정렬 선택

배열 에서 가장 작은 요 소 를 찾 습 니 다

배열 의 첫 번 째 요소 와 위 치 를 교환 합 니 다 (첫 번 째 가 가장 작다 면 자신 과 교환 합 니 다)

남 은 요소 에서 가장 작은 요 소 를 찾 아 배열 의 두 번 째 요소 와 위 치 를 교환 합 니 다

전체 배열 의 정렬 이 완 료 될 때 까지 상기 절 차 를 반복 합 니 다.

특징:

운행 시간 은 입력 과 무관 합 니 다

데이터 이동 이 가장 적다

시간 복잡 도: O (n2)

공간 복잡 도: O (1)

    /**
     *     
     * 
     * @param array     
     */
    private static int[] selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i + 1; j < array.length; j++) {
                int min = i;
                if (array[j] < array[min]) {
                    //                 
                    min = j;
                }
            }
            if (i != min) {
                int tmp = array[i];
                array[i] = array[min];
                array[min] = tmp;
            }
        }
        System.out.println(Arrays.toString(array));
        return array;
    }

거품 정렬

서로 인접 한 요소 입 니 다. 첫 번 째 가 두 번 째 보다 크 면 두 개 를 교환 하 세 요.

모든 인접 요소 에 대해 똑 같은 일 을 하고 첫 번 째 쌍 부터 마지막 쌍 까지 한다. 이 단계 가 끝나 면 마지막 요소 가 가장 클 것 이다.

모든 요소 에 대해 상기 절 차 를 반복 하고 마지막

을 제외 합 니 다.

한 쌍 의 숫자 를 비교 할 필요 가 없 을 때 까지 매번 점점 적어 지 는 요소 에 대해 위의 절 차 를 반복 한다

.
특징:

운행 시간 은 입력 과 무관 합 니 다

시간 복잡 도: O (n2)

공간 복잡 도: O (1)

    private static int[] bubbleSort(int[] array) {
        boolean notChange = false;
        for (int i = 1; i < array.length; i++) {
            for (int j = 0; j < array.length - i; j++) {
                if (array[j] > array[j + 1]) {
                    int flag = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = flag;
                } else {
                    notChange = true;
                }
            }
            if (!notChange)
                break;
        }
        System.out.println(Arrays.toString(array));
        return array;
    }

삽입 정렬

첫 번 째 요소 부터 이 요 소 를 정렬 된 요소 로 여 긴 다

다음 요 소 를 새로운 요소 로 추출 하고 정렬 된 요소 대기 열 에서 뒤로 스 캔

이 요소 (정렬 됨) 가 새 요소 보다 크 면 이 요 소 를 다음 위치 로 이동 합 니 다

정렬 된 요소 가 새 요소 보다 작 거나 같은 위 치 를 찾 을 때 까지 3 단 계 를 반복 합 니 다

새 요 소 를 이 위치 에 삽입 한 후

중복 2 - 5

정렬 에 필요 한 시간 은 입력 요소 의 초기 순서 에 달 려 있 습 니 다. 예 를 들 어 크 고 요소 가 질서 있 는 배열 은 무 작위 순서 인 배열 보다 훨씬 빠 를 것 입 니 다.
삽입 정렬 을 선택 할 때

배열 의 모든 요 소 는 최종 위치 에서 멀 지 않다

질서 있 는 큰 배열 과 작은 배열

배열 에서 몇 개의 요소 만 위치 가 정확 하지 않다

즉, 부분 질서 있 는 배열 은 삽입 정렬 을 선택 할 수 있 습 니 다.

    private static int[] insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            //         
            int tmp = array[i];
            int j = i;
            while (j > 0 && tmp < array[j - 1]) {
                array[j] = array[j - 1];
                j--;
            }
            if (j != i) {
                array[j] = tmp;
            }
        }
        System.out.println(Arrays.toString(array));
        return array;
    }

빠 른 정렬

배열 에서 원 소 를 선택 하여 기준 치 (pivot)

라 고 합 니 다.

배열 배열 배열: 모든 기준 치 보다 작은 요 소 는 기준 치 앞 에 놓 고 기준 치 보다 큰 요 소 는 기준 치 뒤에 놓 습 니 다. 이 분할 이 끝 난 후에 이 기준 치 는 배열 의 중간 위치 에 있 습 니 다. 이것 을 분할 작업 (partition)

이 라 고 합 니 다.

재 귀적 (recursively) 은 기준 치보다 작은 요소 의 하위 배열 과 기준 치보다 큰 요소 의 하위 배열 을 정렬 합 니 다.

public static int[] quickSort(int arr[], int start, int end) {
        int pivot = arr[start];
        int i = start;
        int j = end;
        while (i < j) {
            while ((i < j) && (arr[j] > pivot)) {
                j--;
            }
            while ((i < j) && (arr[i] < pivot)) {
                i++;
            }
            if ((arr[i] == arr[j]) && (i < j)) {
                i++;
            } else {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        if (i - 1 > start) {
            arr = quickSort(arr, start, i - 1);
        }
        if (j + 1 < end) {
            arr = quickSort(arr, j + 1, end);
        }
        return (arr);
    }

최 악의 시간 복잡 도: O (n2)
최 적 시간 복잡 도: O (nlogn)
평균 시간 복잡 도: O (nlogn)
공간 복잡 도: O (log n)