정렬 편 (7) -- 빠 른 정렬

힐 정렬 은 정렬 을 직접 삽입 하 는 업그레이드 에 해당 합 니 다. 정렬 을 삽입 하 는 클래스 에 속 합 니 다. 정렬 을 간단하게 선택 하 는 업그레이드 에 해당 합 니 다. 정렬 을 선택 하 는 클래스 에 속 합 니 다. 다음 에 설명 할 빠 른 정렬 은 거품 정렬 의 업그레이드 이 고 모두 교환 정렬 류 에 속 합 니 다.
1. 빠 른 정렬
기본 사상: 한 번 의 정렬 을 통 해 대기 기록 을 독립 된 두 부분 으로 나 누 었 는데 그 중에서 일부 기록 의 키 워드 는 모두 다른 부분 에 기 록 된 키워드 보다 작 으 면 이 두 부분 기록 에 대해 계속 정렬 하여 전체 서열 이 질서 있 는 목적 을 달성 할 수 있다.
2. 빠 른 정렬 알고리즘 실현

package Sort;

/**
 * Created by LKL on 2017/3/4.
 */
public class TestQuickSort {
    public static void main(String[] args){
        int[] adj = new int[]{5,1,9,8,3,7,4,6,2};
        print(adj);
        QuickSort(adj);
    }
    public static void QuickSort(int[] adj){
        QSort(adj,0,adj.length-1);
    }
    public static void QSort(int[] adj,int low,int high){
        int pivot;
        if(low//        ，     
            pivot = Partition(adj,low,high);
            //        
            QSort(adj,low,pivot-1);
            //        
            QSort(adj,pivot+1,high);
            //         
            print(adj);
        }
    }
    /*
    *           ，         ，
    *           ，       ，      （pivot）
    *
    * */
    public static int Partition(int[] adj,int low,int high){
        int pivotkey;
        pivotkey=adj[low];
        //            
        while(lowwhile(low=pivotkey){
                high--;
            }
            swap(adj,low,high);//             
            while(low//             
        }
        return low;
    }
    public static void swap(int[] adj,int low,int high){
        int temp;
        temp=adj[low];
        adj[low]=adj[high];
        adj[high]=temp;
    }
    public static void print(int[] data) {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + "\t");
        }
        System.out.println();

    }
}

실행 결 과 는 다음 과 같 습 니 다.

5   1   9   8   3   7   4   6   2   
1   2   3   4   5   7   8   6   9   
1   2   3   4   5   7   8   6   9   
1   2   3   4   5   6   7   8   9   
1   2   3   4   5   6   7   8   9   
1   2   3   4   5   6   7   8   9

3. 빠 른 정렬 최적화
상기 코드 로 인해 우 리 는 가설 적 인 조작 이 있 습 니 다. 즉, pivot 가 low 와 high 의 중간 에 있다 고 가정 하 는 것 입 니 다. 사실은 이렇게 우연 하지 않 습 니 다. {9, 1, 3, 5, 2, 4, 7, 6, 8} 이 나 타 났 을 때 pivot 는 9 이 고 전환 한 후에 실질 적 인 최적화 가 발생 하지 않 았 기 때문에 '3 수 취 중 법', 즉 세 개의 키 워드 를 먼저 정렬 하 는 것 이 생각 났 습 니 다.중간 수 를 중심 축 으로 하 는 것 은 일반적으로 왼쪽 끝, 오른쪽 끝 과 중간 세 개의 수 를 취한 다.이때 pivot 는 적어도 가장 크 거나 가장 작 지 는 않 을 것 이다.주로 Patition 방법 을 수 정 했 는데 먼저 pivot 가 최대 도, 최소 도 아니 라 고 판정 했다.

 /*
    *           ，         ，
    *           ，       ，      （pivot）
    *
    * */
    public static int Partition(int[] adj,int low,int high){
        int pivotkey;
        int m=low +(high-low)/2;
        if(adj[low]>adj[high]){
            swap(adj,low,high);
        }
        if(adj[m]>adj[high]){
            swap(adj,high,m);
        }
        if(adj[m]>adj[low]){
            swap(adj,m,low);
        }
        pivotkey=adj[low];
        //            
        while(lowwhile(low=pivotkey){
                high--;
            }
            swap(adj,low,high);//             
            while(low//             
        }
        return low;
    }

4. 빠 른 정렬 복잡 도 분석
(1) 빠 른 정렬 이 가장 좋 은 시간 복잡 도
빠 른 정렬 이 가장 좋 은 경 우 는 매번 얻 은 요소 가 전체 배열 을 똑 같이 나 누 는 것 이다 (위의 것 이 아 닌 것 이 분명 하 다).이때 의 시간 복잡 도 공식 은 T [n] = 2T [n / 2] + f (n) 이다.T [n / 2] 는 평 분 된 하위 배열 의 시간 복잡 도 이 고 f [n] 는 이 배열 을 나 눌 때 걸 리 는 시간 입 니 다.다음은 가장 좋 은 상황 에서 빠 른 정렬 시간 복잡 도 계산 (교체 법 으로) 을 추산 한다.

       T[n] =  2T[n/2] + n       ------                                                                             

령: n = n / 2 = 2 {2 T [n / 4] + (n / 2)} + n - 두 번 째 귀속

            =  2^2 T[ n/ (2^2) ] + 2n

령: n = n / (2 ^ 2) = 2 ^ 2 {2 T [n / (2 ^ 3)] + n / (2 ^ 2)} + 2 n - 세 번 째 귀속

            =  2^3 T[  n/ (2^3) ]  + 3n

            ......................................................................................                        

             ：n = n/(  2^(m-1) )    =  2^m T[1]  + mn                                                  ---------------- m   (m    )
                        ，             ，     T[1] ，            （T[1]    ）。

획득: T [n / (2 ^ m)] = T [1] = = > n = 2 ^ m = = = > > m = logn;T[n] = 2^m T[1] + mn ；그 중 m = logn;

           T[n] = 2^(logn) T[1] + nlogn  =  n T[1] + nlogn  =  n + nlogn  ；  n     

또 n > = 2 시: nlogn > = n (즉 logn > 1) 이 므 로 뒤의 nlogn 을 가 져 옵 니 다.

               ：                ：O( nlogn )。

(2) 최 악의 경우 시간 복잡 도

                      /   ，             (             ),       O(n^2)。

(3) 평균 시간 복잡 도 는 O (nlogn)
(4) 공간 복잡 도:

            ：O(logn)；           ；
            ：O( n )；          。

글 은 단지 자신의 학습 노트 로 서 인터넷 의 많은 사례 를 참고 하 였 을 뿐 입 니 다. 만약 에 여유 가 있다 고 생각한다 면 많이 교류 하고 싶 습 니 다. 여기 서 감 사 드 립 니 다.