빠 른 정렬 + 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 로 되 돌 릴 수 있 습 니까?
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
WebView2를 Visual Studio 2017 Express에서 사용할 수 있을 때까지Evergreen .Net Framework SDK 4.8 VisualStudio2017에서 NuGet을 사용하기 때문에 패키지 관리 방법을 packages.config 대신 PackageReference를 사용해야...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.