알고리즘 시리즈 - 정렬 알고리즘 (3) 정렬 선택

정의.          정렬 선택: 말 그대로 조건 에 맞 는 요 소 를 선택 하여 배열 이 완 료 될 때의 위치 에 직접 놓 는 것 입 니 다.현재 집합 중 가장 값 을 선택 할 때마다        선 택 된 요 소 는 한 번 의 비 교 를 통 해 자신의 위 치 를 직접 찾 을 수 있 습 니 다.'정렬 선택' 과 '거품 정렬' 은 모두 '상위 5 명', '후 5 명' 에 적합 하 다.도해
        (1) 배열 에서 가장 작은 요소 값 과 위 치 를 선택 하고 기본 첫 번 째 [3] 은 최소 값 입 니 다.
3
1
4
2
5
8
7
        (2) 、 【 3 】 은 최소 값 으로 뒤로 비교 합 니 다. 【 1 】 < 【 3 】, 최소 값 은 【 1 】 아래 표 시 【 1 】 로 변 합 니 다.
3
1
4
2
5
8
7
        (3) 、 【 1 】 은 최소 값 으로 뒤로 비교 하고 배열 의 마지막 요소 까지 그 동안 커서 만 변 했 을 뿐 배열 요 소 는 이동 하지 않 았 습 니 다.
3
1
4
2
5
8
7
        (4) 그 다음 에 교환 [1] 에서 그 당시 의 시작 위치 와 데이터 교환 (몇 위 부터 누구 와 교환 하 는 지 비교 하고 비교 과정 은 선택 한 값 이 전체 범위 에서 가장 높 은 값 임 을 확인 하 는 것 이다).
1
3
4
2
5
8
7
       이상 은 한 번 의 선택 과정 이 고 정렬 을 선택 하 는 것 도 여러 번 선택 하여 구성 해 야 합 니 다.
       매번 선택 결 과 는 다음 과 같다.
3
1
4
2
5
8
7
1
3
4
2
5
8
7
1
2
4
3
5
8
7
1
2
3
4
5
8
7
1
2
3
4
5
8
7
1
2
3
4
5
8
7
1
2
3
4
5
7
8
       다음은 시간의 복잡 도 를 계산한다.       위의 그림 과 같이 N 개 요소 의 배열 은 (N - 1) 번 의 선택 과정 이 필요 합 니 다. 매번 감소 하 는 비교 횟수 는 첫 번 째 와 같 습 니 다. (N - 1) 번 의 비교 가 필요 합 니 다.       (N - 1) + (N - 2) +... + 1 = N (N - 1) / 2 이기 때문에 시간 복잡 도 O (N ^ 2).
       신경 쓰 이 는 사람 이 있어 요. 안정성, 그러면 어떤 상황 에서 요소 가 위 치 를 바 꾸 고 불안정 한 상황 이 발생 할 수 있 는 지 스스로 생각해 보 세 요.       물론 입 니 다. 다른 요 소 를 다시 이동 할 때 해당 위치 에 있 는 요 소 를 교환 합 니 다. 이 럴 때 교환 이 발생 할 수 있 습 니 다.하지만 꼭 일어 날 까요?       아 닙 니 다. 같은 요소 가 현재 정렬 할 요소 라면 교환 되 지 않 습 니 다.       즉, "한 번 에 선택 하 는 과정 은 두 개의 같은 요소 의 위 치 를 교환 하지 않 고 여러 번 에 반드시 그렇지 않 기 때문에 순 서 를 선택 하 는 것 은 불안정 하 다!"
약간 얇 은 코드 추가:

    /**
     *     
     *
     * @param array     
     * @param flag    -0   -1
     * @return    
     */
    public static int[] selectSort(int[] array, boolean flag) {
        for (int i = 0; i < array.length - 1; i++) {
            int index = i, min = array[i];
            for (int j = i + 1; j < array.length; j++) {
                if (min > array[j] ^ flag) {
                    min = array[j];
                    index = j;
                }
            }
            if (index != i) {
                array[index] = array[i];
                array[i] = min;
            }
        }
        return array;
    }

       하루 에 하나의 알고리즘 을 오늘 이 걸 나 눠 서...