Java의 정렬 방법 예-Java베이스-php.cn

Java의 정렬 방법 예

王林

풀어 주다： 2019-11-12 15:36:28

원래의

4112명이 탐색했습니다.

Java의 정렬 방법 예

버블 정렬

특징: 낮은 효율성, 간단한 구현

아이디어 (작은 것부터 큰 것까지 정렬): 각 패스에서 정렬할 시퀀스의 가장 큰 요소를 끝으로 이동하고 나머지는 정렬할 새 시퀀스입니다. 모든 요소가 정렬될 때까지 위 단계를 반복합니다. 이것은 일종의 버블 정렬일 뿐이며, 물론 뒤에서 앞으로 정렬할 수도 있습니다.

public void bubbleSort(int array[]) {
        int t = 0;        
        for (int i = 0; i < array.length - 1; i++)            
        for (int j = 0; j < array.length - 1 - i; j++)                
        if (array[j] > array[j + 1]) {
                    t = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = t;
                }
    }

로그인 후 복사

정렬 선택

특징: 낮은 효율성, 구현 용이

생각: 모든 정렬할 시퀀스에서 가장 작은 요소를 선택하고 정렬된 시퀀스의 끝에 배치합니다. 정렬이 완료될 때까지 정렬할 시퀀스의 나머지 요소에 대해 위 단계를 반복합니다.

public void selectSort(int array[]) {
        int t = 0;        
        for (int i = 0; i < array.length - 1; i++)            
        for (int j = i + 1; j < array.length; j++)                
        if (array[i] > array[j]) {
                    t = array[i];
                    array[i] = array[j];
                    array[j] = t;
                }
    }

로그인 후 복사

삽입 정렬

특징: 효율성이 낮고 구현이 용이함

아이디어: 배열 두 부분으로 나누고, 뒷부분의 요소를 이전 부분의 요소와 하나씩 비교합니다. 현재 요소 배열[i]이 작으면 교체합니다. 배열을 삽입할 합리적인 위치 찾기[i]

public void insertionSort(int array[]) {
        int i, j, t = 0;        
        for (i = 1; i < array.length; i++) {
            t = array[i];            
            for (j = i - 1; j >= 0 && t < array[j]; j--)
                array[j + 1] = array[j];
            array[j + 1] = t;
        }
    }

로그인 후 복사

quick sort

특징: 높은 효율성, 시간 복잡도는 nlogn입니다. .

분할 정복 방식 채택: 먼저 축 값 피벗을 설정한 다음 이 축 값을 분할 기준으로 사용하여 정렬할 시퀀스를 피벗보다 큰 두 부분으로 나눕니다. 피벗보다 작은 다음 하위 시퀀스가 하나의 요소가 될 때까지 하위 시퀀스에 대해 빠른 정렬 수행을 나눕니다.

public void quickSort(int array[], int low, int high) {// 传入low=0，high=array.length-1;
        int pivot, p_pos, i, t;// pivot->位索引;p_pos->轴值。        
        if (low < high) {
            p_pos = low;
            pivot = array[p_pos];            
            for (i = low + 1; i <= high; i++)                
            if (array[i] > pivot) {
                    p_pos++;
                    t = array[p_pos];
                    array[p_pos] = array[i];
                    array[i] = t;
                }
            t = array[low];
            array[low] = array[p_pos];
            array[p_pos] = t;            // 分而治之
            quickSort(array, low, p_pos - 1);// 排序左半部分
            quickSort(array, p_pos + 1, high);// 排序右半部分
        }

로그인 후 복사