JAVA 고전 정렬 알고리즘 총화

거품 정렬 
세로 로 배 열 된 키워드 서열 을 아래 에서 위로 스 캔 하 는 방향 으로 두 개의 인접 한 키 워드 를 비교 하고  역순 (k j < k j - 1) 이면 두 개의 기록 을 교환 합 니 다.  교환 이 필요 할 때 까지 위 스 캔 정렬 과정 을 반복 합 니 다.

public static void bubbleSort(int[] arr, int size) {    boolean swap = false;    for (int i = 0; i < size - 1; i++) { //     n-1  
        swap = false;        for (int j = size - 1; j > i; j--) { //      
            if (arr[j] < arr[j - 1]) {
                swap(arr, j, j - 1);
                swap = true;
            }
        }        if (!swap) {            break; //      ，    
        }
    }
}

거품 정렬 최적화:  기껏해야 n - 1 번 의 스 캔 이 필요 합 니 다. 만약 에 특정한 스 캔 후에 정렬 기록 이 질서 가 있 으 면 이 스 캔 후에 종료 할 수 있 습 니 다.  불 량 swap 를 도입 할 수 있 습 니 다. 매번 스 캔 전 값 은 false 입 니 다. 정렬 과정 에서 교환 이 발생 하면 true 로 설정 합 니 다.  한 번 스 캔 후에 도 swap 가 false 라면 이번 에는 기록 을 교환 하지 않 았 음 을 나타 내 며 알고리즘 을 종료 할 수 있 습 니 다.
교환 함수

public static void swap(int[] arr, int one, int two) {    int temp = arr[one];
    arr[one] = arr[two];
    arr[two] = temp;
}

빠 른 정렬 
한 번 의 정렬 을 통 해 기록 서열 을 두 개의 하위 서열 로 나 누고,  다시 이 두 개의 하위 서열 을 정렬 하여 전체 서열 의 질서 에 도달 하도록 한다.

//      [start, end],    end public static void quickSort(int[] arr, int start, int end) {    if (start < end) {        int p = partition(arr, start, end);
        quickSort(arr, start, p - 1);
        quickSort(arr, p + 1, end);
    }
}//       ，           public static int partition(int[] arr, int left, int right) {    int pivot = arr[left];    while (left < right) {        while (left < right && arr[right] >= pivot)
            right--;        if (left < right)
            arr[left++] = arr[right];        while (left < right && arr[left] <= pivot)
            left++;        if (left < right)
            arr[right--] = arr[left];
    }
    arr[left] = pivot;    return left;
}

빠 른 정렬 최적화:  기준의 선택 은 빠 른 정렬 의 성능 에 영향 을 미친다. 가장 이상 적 인 상황 은 선택 한 기준 이 정렬 대기 서열 을 두 개의 긴 하위 서열 로 나 눌 수 있다 는 것 이다.
위의 선택 기준 은 고정된 사용 서열 의 첫 번 째 요소 이 고 개선 방향 은 왼쪽, 오른쪽 과 중간 위치 에 있 는 세 가지 요소 의 중위 수 를 기준 으로 하 는 것 이다.
비 귀속 빠 른 정렬 실현  사고방식 은 창고 시 뮬 레이 션 으로 귀착 하 는 것 이다

public static void quickSort(int[] arr, int start, int end) {    int[] stack = new int[end - start + 1]; //      
    int len = 0;    stack[len++] = start; //   
    stack[len++] = end;    while (len > 0) { //       
        int right = stack[--len]; //     --len
        int left = stack[--len];        int p = partition(arr, left, right);        if (p - 1 > left) {            stack[len++] = left;            stack[len++] = p - 1;
        }        if (p + 1 < right) {            stack[len++] = p + 1;            stack[len++] = right;
        }
    }
}

삽입 정렬 
키워드 ki 순서 와 질서 구역 의 키워드 ki-1、k_i-2、··· 、k_비교  삽입 할 위 치 를 찾 아 ki 삽입, 뒤의 순 서 는 뒤로 이동 해 야 합 니 다.

public static void insertSort(int[] arr, int size) {    int temp = arr[0];    for (int i = 1; i < size; i++) {        //   arr[i]              ，       
        if (arr[i] < arr[i - 1]) { 
            temp = arr[i];            int j = i - 1;            while (j >= 0 && temp < arr[j]) {
                arr[j + 1] = arr[j--];
            }
            arr[j + 1] = temp;
        }
    }
}

힐 정렬 
n 보다 시간 효율 이 높 을 때 정렬 삽입 하기;한 그룹의 기록 이 질서정연 할 때 정렬 을 삽입 하 는 알고리즘 의 복잡 도가 가장 좋 은 데, 즉 O (n) 이다.  힐 정렬 은 바로 이 두 가 지 를 바탕 으로 삽입 정렬 을 개선 한 것 이다.
힐 정렬 의 기본 사상: t 개 정수 증 가 량 설정: d1、d_2、···、d_t, 그 중 d1 < n, d_t=1  d1. 증 량 으로 모든 거 리 를 d1 의 기록 을 같은 그룹 에 두 면 d 를 얻 을 수 있 습 니 다.1 개 그룹 은 각 그룹 에 직접 정렬 을 삽입 합 니 다.  그리고 두 번 째 증 량 d2. 상기 그룹 과 정렬 을 반복 하여 증분 d 까지 반복 합 니 다.t=1
증 량 서열 을 설정 할 때 증 량 값 이 1 을 제외 한 공인 자가 없 도록 하려 면 마지막 증 량 값 이 1 이 어야 합 니 다.  힐 의 정렬 시간 복잡 도 는 증 량 서열 의 선택 에 달 려 있다.

// shellSort(origins, origins.length, new int[] { 5, 3, 1 });public static void shellSort(int[] arr, int size, int[] d) {    for (int k = 0; k < d.length; k++) {        int gap = d[k];        for (int j = 0; j < gap; j++) { //       gap，   gap  ，0~gap-1
            for (int i = j + gap; i < size; i++) {                if (arr[i] < arr[i - gap]) { //     ，       
                    int pivot = arr[i];                    int t = i - gap;                    while (t >= 0 && pivot < arr[t]) {
                        arr[t + gap] = arr[t];
                        t = t - gap;
                    }
                    arr[t + gap] = pivot;
                }
            }
        }
    }
}

정렬 
병합 의 의 미 는 두 개 또는 두 개 이상 의 질서 표를 하나의 새로운 질서 표 로 통합 하 는 것 이다.  정렬 을 병합 하 는 사고방식 은:  초기 표 에 n 개의 기록 이 포함 되 어 있다 고 가정 하면 n 개의 질서 있 는 하위 표 로 볼 수 있 고 모든 하위 표 의 길 이 는 1 이 며 그 다음 에 두 개의 병합 으로 볼 수 있다.  n / 2 개의 길이 가 2 인 질서정연 한 서브 테이블 을 얻 고 두 개 를 더 합치 면 길이 가 n 인 질서정연 한 서브 테이블 을 얻 을 때 까지 반복 된다.
두 개의 질서 표 병합:

//  arr[low]~arr[center] arr[center+1]~arr[right]      public static void merge(int[] arr, int left, int center, int right) {    int[] result = new int[right - left + 1];    int i = left, j = center + 1, k = 0;    while (i <= center && j <= right) {        if (arr[i] < arr[j])
            result[k++] = arr[i++];        else
            result[k++] = arr[j++];
    }    while (i <= center)
        result[k++] = arr[i++];    while (j <= right)
        result[k++] = arr[j++];
    System.arraycopy(result, 0, arr, left, right - left + 1);
}

한 번 병합:  길이 가 n 인 정렬 대기 서열 에서 모든 질서 표 의 길 이 는 step 이 고 병합 하기 전에 n / step 키 서열 이 있 습 니 다.  arr [0] ~ arr [step - 1], arr [step] ~ arr [step * 2 - 1], · ·, 한 번 에 합쳐서 인접 한 한 한 쌍 의 질서 표를 합치다.  세 가지 상황 을 고려 해 야 한다.

질서 표 의 개 수 는 짝수 이 고 길 이 는 모두 step

이다.

질서 표 의 개 수 는 짝수 이지 만 마지막 질서 표 의 길 이 는 step

보다 작다.

질서 표 의 개 수 는 홀수 (윤 공, 병합 필요 없 음)

//        step，         public static void mergePass(int[] arr, int step) {    int length = arr.length;    int i = 0;    //   ，      step       
    for (; i + step * 2 - 1 < length; i += step * 2) {
        merge(arr, i, i + step - 1, i + step * 2 - 1);
    }    if (i + step < length)
        merge(arr, i, i + step - 1, length - 1);    //   :   i + step >= length,         ，    }

정렬 을 병합 할 때 질서 표 의 초기 길 이 는 1 이 고 매번 병합 후 질서 표 의 길 이 는 배로 커진다.  여러 번 병합 한 후, 질서 표 의 길이 > = n, 정렬 이 끝 났 습 니 다.

public static void mergeSort(int[] arr, int size) {    for (int i = 1; i < size; i *= 2) {
        mergePass(arr, i);
    }
}

직접 정렬 선택 
알고리즘 사고방식: 첫 번 째 정렬 은 정렬 대기 기록 arr [0] ~ arr [n - 1] 을 무질서 구역 으로 하고 그 중에서 가장 작은 기록 을 찾아내 고 무질서 구역 과  첫 번 째 기록 arr [0] 교환, 이때 질서 구역 은 arr [0] 이 고 무질서 구역 은 arr [1] ~ arr [n - 1] 입 니 다.  두 번 째 순 서 는 arr [1] ~ arr [n - 1] 에서 가장 작은 기록 을 선택 하여 arr [1] 과 교환 합 니 다.  상기 과정 반복...

public static void selectSort( int[] arr, int size) {     for ( int i = 0; i < size; i++) {         int min = i;         for ( int j = i + 1; j < size; j++) {             if (arr[j] < arr[ min])                 min = j;        }         if ( min != i)            swap(arr, min, i);    } }

：http://blog.csdn.net/qq_35101189/article/details/53333066