빠 른 정렬, 병합 정렬, 정렬 선택, 정렬 삽입 자바 구현

빠 른 정렬

    빠 른 정렬 은 분 치 법 (Divide and conquer) 정책 을 사용 하여 하나의 직렬 (list) 을 두 개의 하위 직렬 (sub - lists) 로 나 눕 니 다.
빠 른 정렬 은 일종 의 분할 통치 사상 이 정렬 알고리즘 에서 의 전형 적 인 응용 이다.본질 적 으로 빠 른 정렬 은 거품 정렬 을 바탕 으로 하 는 재 귀 분 치 법 이 라 고 할 수 있다.
평균 상황 에서 n 개 항목 을 정렬 하려 면Ο차 비교.최 악의 경우 에는Ο(n2) 차 비교, 그러나 이런 상황 은 흔 하지 않다.사실 빠 른 정렬 은 보통 다른 것 보다 뚜렷 하 다.Ο(nlogn) 알고리즘 이 더 빠 릅 니 다. 내부 순환 (inner loop) 은 대부분의 구조 에서 효율 적 으로 이 루어 질 수 있 기 때 문 입 니 다.
빠 른 정렬 을 위 한 주요 논리:
1. 확정 치 비교 의 시작 및 기준 치
2. 왼쪽 구간 쾌속 배열
3. 오른쪽 구간 쾌속 줄
4. 정렬 완료 로 재 귀적
Java 구현:

public static void quickSortFromSmallToLarge(int[] arr, int low, int high){
      int left,right,pivot,temp;
      if(low>high){
         return;
      }
      left=low;
      right=high;
      pivot = arr[low];

      while (left=arr[left]&&left

병합 정렬

    병합 정렬 (Merge sort) 은 병합 작업 에 있어 서 효과 적 인 정렬 알고리즘 입 니 다.이 알고리즘 은 분 치 법 (Divide and Conquer) 을 사용 한 매우 전형 적 인 응용 이다.
전형 적 인 분할 통치 사상의 알고리즘 응용 으로서 정렬 의 실현 은 두 가지 방법 에 의 해 이 루어 진다.
위 에서 아래로 재 귀 (모든 재 귀 방법 은 교체 로 다시 쓸 수 있 기 때문에 두 번 째 방법 이 있다).아래 에서 위로 의 교체

public static int[] mergeSortFromSmallToLarge(int[] array) {
        int[] arr = Arrays.copyOf(array, array.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(mergeSortFromSmallToLarge(left), mergeSortFromSmallToLarge(right));
    }

    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

정렬 선택

    정렬 을 선택 하 는 것 은 간단 하고 직관 적 인 정렬 알고리즘 으로 어떤 데이터 가 들 어가 도 O (n) 이다.²) 시간 복잡 도 입 니 다. 따라서 사용 할 때 데이터 규모 가 작 을 수록 좋 습 니 다. 유일한 장점 은 추가 메모리 공간 을 차지 하지 않 는 것 일 수도 있 습 니 다.

우선 정렬 되 지 않 은 시퀀스 에서 최소 (큰) 요 소 를 찾 아 정렬 시퀀스 의 시작 위치 에 저장 합 니 다

나머지 정렬 되 지 않 은 요소 에서 최소 (큰) 요 소 를 계속 찾 은 다음 정렬 된 서열 의 끝 에 놓 습 니 다.

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

자바 구현 은 다음 과 같 습 니 다.

    public static void  selecrSortFromSmallToLarge(int [] array,int index){
       if (index>=array.length){
           return;
       }
        int small=array[index];
       for (int i=index;i

정렬 삽입

삽입 정렬 은 가장 간단 하고 직관 적 인 정렬 알고리즘 으로 그의 작업 원 리 는 질서 있 는 서열 을 구축 하고 정렬 되 지 않 은 데이터 에 대해 이미 정렬 된 서열 에서 뒤에서 스 캔 하여 해당 하 는 위 치 를 찾 아 삽입 하 는 것 이다.

첫 번 째 정렬 대기 서열 의 첫 번 째 요 소 를 질서 있 는 서열 로 보고 두 번 째 요 소 를 마지막 요소 까지 정렬 되 지 않 은 서열 로 간주한다.

정렬 되 지 않 은 시퀀스 를 처음부터 끝까지 차례대로 스 캔 하고 스 캔 된 모든 요 소 를 질서 있 는 시퀀스 의 적당 한 위치 에 삽입 합 니 다. (삽입 할 요소 가 질서 있 는 시퀀스 의 특정한 요소 와 같 으 면 삽입 할 요 소 를 같은 요소 뒤에 삽입 합 니 다.)

자바 구현:

   public static  void insertSortFromSmallToLarge(int[] array){
        for(int i = 1;i < array.length;i++) {
            int temp = array[i];
            int index = i-1;
            while(index >= 0 && array[index] > temp) {
                array[index + 1] = array[index];
                index--;
            }
            array[index+1] = temp;

        }
    }

    public static void insertSortFromlargeToSmall(int[] array){

        for (int i=1;i=0&&temp>array[index]){
                array[index+1]=array[index];
                index--;
            }
            array[index+1]=temp;
        }
    }