상용 정렬 알고리즘 요약 분석

정렬 선택
n 으로 규 모 를 정 한 배열 은 n 개의 숫자 에서 가장 작은 하 나 를 찾 은 다음 0 위의 숫자 와 교환 한 다음 n - 1 개의 숫자 에서 가장 작은 것 을 찾 아 첫 번 째 위치의 숫자 와 교환 합 니 다.i 번 을 교환 한 후에 배열 왼쪽 의 i 개의 숫자 는 질서 가 있 고 오른쪽 n - i 개의 숫자 는 순서 가 없다.그리고 n - i 숫자 에서 가장 작은, i 위치 와 의 숫자 교환 위 치 를 찾 습 니 다.n 번 교환 한 후에 전체 배열 이 질서 가 있 습 니 다.
시간 복잡 도: O (n)²)
실현:

public class Selection{
    public static void sort(int[] a) {
        int t;
        for(int i=0;i<a.length;i++){
            int index=i;//                  
            for(int j=i+1;j<a.length;j++){
                if(a[index]>a[j]){//          
                    index=j;
                }
            }
            //           
            t=a[i];
            a[i]=a[index];
            a[index]=t;
        }
    }

}

삽입 정렬
n 규모 의 배열 을 지정 하고 i 번 (i) 을 지정 합 니 다.

public class Insertion{
    public static void sort(int[] a) {
        int t=0;
        for(int i=1;i<a.length;i++){
            int v=a[i],k;
            for(k=i-1;k>=0&&v<a[k];k--){//     a[i]       ，  。
                a[k+1]=a[k];
            }
            a[k+1]=v;// a[i]   a[i]       
        }
    }
}

힐 정렬
삽입 정렬 에 따라 n 개 요소 중 가장 작은 숫자 가 오른쪽 끝 에 있다 면 n - 1 번 을 비교 해 야 목표 위치 에 도달 할 수 있 습 니 다. 요소 의 크기 를 하나씩 비교 하기 때 문 입 니 다. 각각 1 개 를 비교 하고 이동 하 며 1 개 를 비교 하고 이동 하 며 h 개 를 비교 하고 이동 하면 가장 오른쪽 요소 가 목표 위치 로 이동 하 는 횟수 를 비교 합 니 다.큰 폭 으로 줄 어 듭 니 다. 따라서 h 개의 요 소 를 비교 이동 한 후에 n 개의 수 는 n / h 개의 질서 있 는 쌍 이 나타 납 니 다. 그들 은 서로 h 를 사이 에 두 고 h – 를 비교 한 다음 에 h = 1 까지 이동 한 후에 정렬 이 끝 납 니 다. 정렬 을 삽입 하면 h = 1 의 힐 정렬 입 니 다. 시간 복잡 도: 알 수 없 는 적용 범위: 데이터 규모 가 크 고 데이터 가 분 산 됩 니 다.실현:

public class Shell {
    public static void sort(int[] a){
        int h=1,t=0;
        h=a.length/2;
        while(h>=1){//       1 ，        
            for(int i=h-1,j;i<a.length;i++){// i    ，      h          ，    h-1  ，    h   ，          
                int base=a[i];//      
                for(j=i-h;j>=0&&a[j]>base;j-=h){//                   ，          ，   h   
                        a[j+h]=a[j];
                }
                a[j+h]=base;//               
            }
            h/=2;//        
        }
// display(a);
    }
}

정렬
재 귀적 인 방식 을 통 해 n 개의 요소 등 을 두 부분 으로 나 눈 다음 에 이 두 부분 등 을 네 부분 으로 나 누 었 다. 이런 식 으로 유추 하면 n 개의 요 소 를 n 개의 단독 그룹 으로 나 누 는 것 을 알 수 있다. 이 n 개의 그룹 은 하나의 요소 만 있 기 때문에 질서 가 있다. 그리고 그 중에서 인접 한 두 그룹 을 합병 시 키 고 합병 후의 그룹 도 질서 가 있어 n / 2 개의 그룹 을 형성 했다. 그 다음 에 인접 한 두 그룹 을 합병 시 켰 다.조합 하여 n / 4 개의 그룹 을 만 듭 니 다. 이 를 통 해 하나의 그룹 으로 합 쳐 정렬 이 완료 되 었 음 을 알 수 있 습 니 다. 두 그룹 을 합 쳤 을 때 두 개의 바늘 을 두 배열 의 첫 번 째 위 치 를 가리 키 고 크기 를 비교 하여 작은 것 을 임시 배열 에 넣 은 다음 이 지침 을 뒤로 이동 할 수 있 습 니 다. 그 중 한 배열 의 바늘 이 가장 오른쪽 에 있 으 면 다른 배열 의 나머지 요 소 를 임 의 배열 로 복사 할 수 있 습 니 다.시간 배열. 과정 은 다음 과 같다. 시간 복잡 도: O (nlgn) 단점: 원래 배열 과 같은 크기 의 보조 배열 을 열 어야 한다.

public class Merge {
    static int[] temp=null;
    public static void sort(int[] a){
        int start,end;
        temp=new int[a.length];
        start=0;
        end=a.length-1;
        merge(a,start,end);
// display(a);
    }
    public static void merge(int[] a,int start,int end){
        if(start==end)
            return;
        int mid=(start+end)/2;

        merge(a,start,mid);//       ，    
        merge(a,mid+1,end);
        if(a[mid]<a[mid+1])//                      ，             ，        
            return;
        mergeSort(a,start,end);
    }
    public static void mergeSort(int[] a,int start,int end){
        int mid=(start+end)/2;
        for(int i=start,j=mid+1,k=start;k<=end;k++){//i，j              （         ，          ）
            if(i>mid)   temp[k]=a[j++];//           ，                    
            else if(j>end)  temp[k]=a[i++];//           ，                    
            else if(a[i]<a[j])  temp[k]=a[i++];//       i       ，  a[i]       ，  i  
            else    temp[k]=a[j++];//       j       ，  a[j]       ，  j  
        }
        System.arraycopy(temp, start, a, start, end-start+1);//               
    }
    public static void display(int[] a){
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+" ");
        System.out.println();
    }
}

빠 른 정렬
1. n 개 수 를 정 하고 start 에서 end 까지 정렬 2. 왼쪽 에서 오른쪽으로 i 만족 a [i] > a [start] 3 을 찾 습 니 다. 오른쪽 에서 왼쪽으로 j 만족 a [j] > a [start] 4 를 찾 습 니 다. a [i] 와 a [j] 5 를 교환 하고 3, 4 를 반복 합 니 다. i > = j 6, 교환 a [start] 와 a [j] 를 찾 습 니 다. 이때 만족 a [0 ~ j - 1] 는 a [j] 보다 작 습 니 다. a [j + 1, end] 는 모두 a [j] 보다 큽 니 다.7. 1 에서 다시 실행 합 니 다. 이때 start = start, end = j - 1 과 start = j + 1, end = end 까지 start > = end 프로 세 스 그림: 시간 복잡 도 (평균): O (nlgn) 적용 범위: 중복 숫자 가 적 고 질서 있 는 숫자 가 적 습 니 다.

public class Quick {
    public static void sort(int[] a) {
        sort(a, 0, a.length - 1);
    }

    private static void sort(int[] a, int start, int end) {
        if (start >= end)
            return;
        int i = partition(a, start, end);//       ，  i       [start,i-1]，  [i+1,end]
        sort(a, start, i - 1);
        sort(a, i + 1, end);
    }

    private static int partition(int[] a, int start, int end) {//                  ，                 
        int i = start + 1, j = end;
        i = start;
        j = end + 1;
        int value=a[start];
        while (true) {
            while (a[++i] < value)
                //      a[start]   
                if (i == end)
                    break;
            while (a[--j] > value);//      a[start]   ,       a[start]，  j>start   

// if (j == start)
// break;
            if (i >= j)//   i，j   i>j，     
                break;
            swap(a, i, j);
        }
        // j    a[j]      ，         
        //   a[j]      a[start]  j  start
        // a[i]      a[start]  i  end
        //        ，i j        ，a[j]    a[start]     ，       a[i]， a[i]    a[start]
        //   a[j]>a[start]，    j     （  j        a[start]    ，          ，       ）
        //           a[start]    ，  a[j]       a[start]
        swap(a, j, start);
        return j;

    }

    private static void swap(int[] a, int p, int q) {
        int t = a[p];
        a[p] = a[q];
        a[q] = t;
    }
}

더미 정렬
(이 진 트 리) 질서 있 는 정의: 이 진 트 리 에서 모든 부모 노드 가 하위 노드 보다 작 지 않 으 면 이 이 진 트 리 는 질서 있 는 잠수 작업 정의 이다. 만약 에 한 부모 노드 가 두 개의 키 노드 나 하위 노드 중의 하나 보다 크 면 부모 노드 와 하위 노드 중의 큰 위 치 를 교환 한 다음 에 이전의 부모 노드 를(현재 하위 노드 의 위치 로 교환 되 었 습 니 다) 새로운 하위 노드 와 비교 하고 교환 합 니 다. 이 노드 가 하위 노드 보다 크다 는 것 을 알 면 작업 을 끝 냅 니 다. 이 조작 을 하 잠 작업 이 라 고 합 니 다.
질서 있 는 더미 에 대해 서 는 번호 가 0 인 노드 가 가장 큰 요소 일 것 입 니 다. 이 요 소 를 제거 하고 마지막 요 소 를 0 위치 에 두 면 이 더 미 는 무질서 한 더미 가 됩 니 다. 그 다음 에 0 노드 에 대해 잠수 작업 을 한 다음 에 이 더 미 는 질서 있 는 더미 가 되 었 습 니 다. 그 다음 에 계속 제거 하고 정렬 을 한 다음 에 이 더미 의 크기 는 0 이 고 원래 배열 의 위 치 는 질서 있 는 순서 로 바 뀌 었 습 니 다. 이 더 미 는 질서 있 는 순서 로 바 뀌 었 습 니 다.그림 은 질서 있 게 쌓 인 최대 요 소 를 제거 하고 정렬 하여 최종 적 으로 질서 있 는 수열 을 얻 는 과정 입 니 다. 그러면 다음 문 제 는 무질서 한 더 미 를 어떻게 질서 있 게 쌓 느 냐 하 는 것 입 니 다. 한 더 미 를 아래 에서 위로 내 려 오 면 최종 적 으로 질서 있 는 더 미 를 만 드 는 것 입 니 다. 마지막 노드 는 하위 노드 가 없 기 때문에 내 려 오 는 작업 을 할 필요 가 없습니다. 꼴찌 2 층 에서마지막 노드 에서 잠수 작업 을 시작 하고 첫 번 째 요 소 를 알 면 질서 있 는 더 미 를 형성 할 수 있다. 과정 은 다음 과 같다.
알고리즘 복잡 도: O (nlgn)
실현:

public class Heap {
    //               
    //
    // 0
    // 1 2
    // 3 4 5 6
    //
    //         ，   n       （    ）   n/2⌉-1,    （    ）   n*2+1 n*2+2
    //     n   ，                (n+1)/2⌉+1

    public static void sort(int[] a) {
        int n = a.length;
        for (int k = (int) (Math.ceil((double) (n + 1) / 2) + 1); k >= 0; k--)
            //                  
            sink(a, k, n);
        while (n > 1) {
            swap(a, 0, --n);
            sink(a, 0, n);
        }
    }

    public static void sink(int[] a, int k, int n) {//     
        while (k * 2 + 2 < n) {
            int j = k * 2 + 1;// j        
            if (a[j] < a[j + 1])//                 
                j++;//   j        
            if (a[k] > a[j])//             ，             ，         
                break;
            swap(a, k, j);//             
            k = j;
        }
    }

    private static void swap(int[] a, int p, int q) {
        int t = a[p];
        a[p] = a[q];
        a[q] = t;
    }
}