빠 른 정렬 + c \ # 기반 구현

1724 단어 C#알고리즘정렬
최근 에 알고리즘 서론 을 배우 고 빠 른 배열 법 에 대해 정 리 를 했 습 니 다.
빠 른 배열 의 특징:
최 악의 경우 n 개 수의 정렬 에 걸 리 는 시간 은 O (n ^ 2) 입 니 다.비록 이 결 과 는 비교적 나 쁘 지만 빠 른 정렬 은 정렬 에 사용 하 는 가장 좋 은 실 용적 인 선택 이다. 왜냐하면 평균 성능 이 상당히 좋 기 때문이다. 기대 하 는 운행 시간 은 O (nlgn) 이 고 O (nlgn) 에 포 함 된 인자 가 비교적 작 기 때문이다. 또한 현지에서 정렬 할 수 있다 (즉, 중간 데이터 저장 을 위해 별도의 배열 공간 을 열 필요 가 없다).가상 환경 에서 도 잘 일 할 수 있다.
빠 른 배열 의 원리:
public static void QuickSort(int[] arr, int p, int r)
{
    if (p < r)
    {
        int q = Partition(arr, p, r);
        QuickSort(arr, q+1, r);
        QuickSort(arr, p, q - 1);
    }
}
/// 
        ///       p r    ,      (  q ),
        ///           arr[q],       arr[q]
        /// 
        /// 
        /// 
        /// 
        /// 
        public static int Partition(int[] arr, int p, int r)
        {
            int i = p - 1;
            int tmp;
            for (int j = p; j <= r - 1; j++)
            {
                if (arr[j] <= arr[r])
                {
                    i++;
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
            tmp = arr[i + 1];
            arr[i + 1] = arr[r];
            arr[r] = tmp;
            return i + 1;
        }

관건 은 바로 Partition 방법 입 니 다. 다음 예 를 들 어 빠 른 정렬 Partition 의 절 차 를 살 펴 보 겠 습 니 다.
int[] arr = new int[8] { 2, 8, 7,1,3, 5,6,4}; QuickSort.Partition(arr,0,7);
이 운행 과정 을 본 후에 빠 른 정렬 사상 을 기본적으로 이해 했다 고 믿는다.이제 사고 문 제 를 드 리 겠 습 니 다.
만약 배열 p 에서 r 의 요소 가 모두 같다 면 Partition 의 반환 값 은 얼마 입 니까?어떻게 해야만 그것 을 (p + r) / 2 로 되 돌 릴 수 있 습 니까?

좋은 웹페이지 즐겨찾기