알고리즘 (4) - 정렬

1. 정렬 분류
다음 과 같은 네 가지 정렬 을 간단하게 쓰 십시오.
정렬 알고리즘
평균 시간 복잡 도
공간 복잡 도
안정성
거품 정렬
O(n2)
O(1)
안정시키다
정렬 선택
O(n2)
O(1)
불안정
삽입 정렬
O(n2)
O(1)
안정시키다
빠 른 정렬
O(nlogn)
O(logn)
불안정
둘째, 정렬 소개
2.1 거품 정렬
사고: 비교적 인접 한 요소.첫 번 째 가 두 번 째 보다 크 면 두 사람 을 교환 하 세 요.매 라운드 에서 가장 크 거나 가장 작은 원 소 를 만들어 낸다.

public static int[] bubbleSort(int[] arr) {
   for (int i = 0; i < arr.length; i++) {
       for (int j = i + 1; j < arr.length; j++) {
           if (arr[i] > arr[j]) {
               int tmp = arr[i];
               arr[i] = arr[j];
               arr[j] = tmp;
           }
       }
   }
   return arr;
}

거품 정렬
2.2 정렬 선택
사고: 첫 번 째 라운드 에서 최소 요 소 를 찾 아 0 번 요소 와 교환 하고 두 번 째 라운드 에서 두 번 째 작은 요소 와 1 번 요 소 를 찾 아 교환 하 는 것 을 유추 합 니 다.

public static int[] selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int min = i;
       for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
           }
        }
        if (min != i) {
            int tmp = arr[i];
           arr[i] = arr[min];
           arr[min] = tmp;
       }
    }
    return arr;
}

정렬 선택
2.3 정렬 삽입
사고: 배열 을 옮 겨 다 니 며 뒤의 모든 사람 은 앞에서 정렬 된 배열 과 스 캔 을 하고 해당 하 는 순서 위 치 를 확정 하 며 삽입 하 며 나머지 요 소 는 모두 1 자리 뒤로 이동 합 니 다.

public static int[] insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int cur = arr[i];
        int j;
        for (j = i-1; j >= 0; j--) { //          
           if(cur < arr[j]){
               arr[j+1] = arr[j];//          
           }else {
               break;
           }
        }
        //         （      j--，    +1   ）
        arr[j+1] = cur;
    }
    return arr;
}

삽입 정렬
2.4 빠 른 정렬
사고: 분 치 + 재 귀 는 먼저 수열 에서 하나의 수 를 key 값 으로 하고 좌우 양쪽 지침 은 중간 으로 가 며 왼쪽 은 기준 보다 큰 수 를 찾 고 오른쪽 은 기준 보다 작은 수 를 찾 아 이들 을 교환 합 니 다.좌우 포인터 가 교차 하면 이 위치 값 은 기준 위치 와 교환 된다.그리고 현재 기준 위치의 왼쪽 부분 과 오른쪽 부분 을 차례대로 돌려 줍 니 다.최종 적 으로 모든 작은 수열 은 질서 가 있 고 전체 질서 있 는 수열 을 이룬다.

    public static void quickSort(int[] arr, int low, int high) {
        if (low > high) {
            return;
        }
        int i = low;
        int j = high;
        int key = arr[low];

        while (i < j) {
            while (key <= arr[j] && i < j) {
                j--;
            }

            while (key >= arr[i] && i < j) {
                i++;
            }

            if (i < j) {
                int tmp = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;
            }
        }

        //        i j       
        arr[low] = arr[i];
        arr[i] = key;

        //         
        quickSort(arr, low, j - 1);
        //         
        quickSort(arr, j + 1, high);
    }

빠 른 정렬
미 완성 계속...
움 직 이 는 그림 출처:https://www.jianshu.com/p/c4217456c224