빠 른 정렬 알고리즘 및 C\#버 전의 실현 예 시 를 점차적으로 설명 하 다

알고리즘 사상
빠 른 정렬 은 C.R.A.Hoare 가 1962 년 에 제기 한 구분 교환 정렬 이다.그것 은 일반적으로 분 치 법(Divide-and-ConquerMethod)이 라 고 부 르 는 분 치 전략 을 채택 했다.
이 방법의 기본 사상 은:
1.먼저 수열 에서 하나의 수 를 꺼 내 기준 수로 한다.
2.파 티 션 과정 은 이 숫자 보다 큰 수 를 모두 오른쪽 에 놓 고 작 거나 같은 수 를 모두 왼쪽 에 놓 습 니 다.
3.좌우 구간 에 두 번 째 단 계 를 반복 하여 각 구간 에 한 개의 수 만 있 을 때 까지 한다.
빠 른 정렬 을 분 치 법 이 라 고 하지만 분 치 법 이라는 세 글 자 는 빠 른 정렬 의 모든 절 차 를 잘 요약 할 수 없다.그래서 저 는 빠 른 정렬 에 대해 진일보 한 설명 을 했 습 니 다.구 덩이 를 파 는 수량+분 치 법:
먼저 실례 를 살 펴 보고 정 의 를 내 린 다음 에(자신의 말로 정 의 를 정리 하 는 것 이 코드 를 실현 하 는 데 도움 이 될 것 입 니 다).
하나의 배열 을 예 로 들 어 구간 의 첫 번 째 수 를 기준 으로 한다.

초기,i=0;  j = 9;   X = a[i] = 72
a[0]의 수 를 X 에 저 장 했 기 때문에 배열 a[0]에 구 덩이 를 파 서 다른 데 이 터 를 여기에 채 울 수 있다 고 이해 할 수 있 습 니 다.
j 부터 앞으로 X 보다 작 거나 X 와 같은 수 를 찾 아 라.j=8,조건 에 부합 되면 a[8]를 파 서 위의 구덩이 a[0]에 채 웁 니 다.a[0]=a[8]; i++;  이렇게 하나의 구덩이 a[0]가 해결 되 었 지만 또 하나의 새로운 구덩이 a[8]가 형성 되 었 습 니 다.어떻게 합 니까?간단 합 니 다.다시 숫자 를 찾 아 a[8]이 구 덩이 를 채 웁 니 다.이번 에는 i 부터 뒤로 X 이상 의 수 를 찾 습 니 다.i=3 이 조건 에 부합 되면 a[3]를 파 서 이전 구덩이 에 a[8]=a[3]를 채 웁 니 다.j--;
배열 변경:

i = 3;   j = 7;   X=72
위의 절 차 를 반복 하고 먼저 뒤에서 앞으로 찾 은 다음 에 앞에서 뒤로 찾 습 니 다.
j 부터 앞으로 찾 습 니 다.j=5 가 조건 에 부합 되면 a[5]를 파 서 위의 구덩이 에 채 웁 니 다.a[3]=a[5];i++;
i 부터 뒤로 찾 습 니 다.i=5 시 i==j 로 인해 종료 합 니 다.
이때 i=j=5,a[5]는 마침 지난번 에 판 구덩이 이기 때문에 X 를 a[5]에 채 웁 니 다.
배열 변경:

이 를 통 해 알 수 있 듯 이 a[5]앞의 숫자 는 모두 그것 보다 작고 a[5]뒤의 숫자 는 모두 그것 보다 크다.따라서 a[0...4]와 a[6...9]두 구간 에 대해 상술 한 절 차 를 반복 하면 된다.
굴착 매 립 수 를 총 결 하 다.
1．i =L; j = R; 기준 수 를 파 서 첫 번 째 구 덩이 를 만들다.
2.j-뒤에서 그것 보다 작은 수 를 찾 아 이 수 를 파 서 앞의 구덩이 a[i]에 채 웁 니 다.
3.i+는 앞에서 뒤로 그 보다 큰 수 를 찾 고 찾 은 후에 도 이 수 를 파 서 앞의 구덩이 a[j]에 채 웁 니 다.
4.i==j 까지 2,3,2 단 계 를 반복 해서 실행 하고 기준 수 를 a[i]에 입력 합 니 다.
C\#예시 구현

namespace QuickSort
{
  public class QuickSortClass
  {
    public int Division(List<int> list, int left, int right)
    {
      //          
      int baseNum = list[left];
      while (left < right)
      {
        //           ，     base      (  base   )
        while (left < right && list[right] >= baseNum)
          right = right - 1;
        //      baseNum    ，            base   
        list[left] = list[right];
        //           ，     base      （  base   ）
        while (left < right && list[left] <= baseNum)
          left = left + 1;
        //      baseNum    ，                  
        list[right] = list[left];
      }
      //     baseNum   left   
      list[left] = baseNum;
      //  ，    left          left ，left       left 
//  ，          
      return left;
    }

    public void QuickSort(List<int> list, int left, int right)
    {
      //          ，      
      if (left < right)
      {
        //       ，           
        int i = Division(list, left, right);

        // “    “              ，             
        QuickSort(list, left, i - 1);

        // “    “              ，             
        QuickSort(list, i + 1, right);
      }
    }
  }
}