빠른 정렬의 간단한 실현

빠른 정렬은 왜 빠를 수 있습니까?
분치 전략을 결합하여 빠른 정렬에서 하나의 기준 요소를 선택하여 두 부분으로 나누면 기준 원소보다 크고 기준 원소보다 작다.매번 이런 효율로 나누면 우리가 취한 기준이 매번 정렬을 기다리는 전체 원소의 중심이 된다는 것을 알 수 있다.
  T(n)=T(n/2)+T(n/2)+O(n)
T(n) = O(nlgn)
최악의 경우
  T(n)=T(n-1)+T(0)+O(n)
이때 T(n) = O(n^2)
명확한 차이는 어떻게 기준을 잘 선택하는가가 빠른 배열에 있어서는 그 효율과 직결된다.
다음은 가장 간단한 방식으로 빠른 정렬을 실현하고자 합니다. 사상은 일치하는 것이 다르고 기준 원소를 선택하는 방식만 다릅니다. 여기서 가장 간단한 것을 취합니다. 매번 고정 테이프 정렬의 마지막 원소를 취합니다.

            
        int partition(int *A,int p,int r)
        {
          int temp=A[r-1];
          int i=p,j=p;
          for(;j<r-1;j++)
          {
              if(A[j]<temp)
              {
                 swap(A[i],A[j]);
                 i++;
              }
          }
          swap(A[i],A[r-1]);
        }
        void qsort(int *A,int p,int r)
        {
               
               if(p<r)
               {
                  int q=partition(A,p,r);
                  qsort(A,p,q-1);
                  qsort(A,q+1,r);          
                }
         }
       

만약 빠른 정렬의 효율이 높아진다면, 대략적인 중위수 방식을 사용할 수 있다. 즉, 한 번씩 차이가 많지 않은 중간의 수를 뽑거나 무작위 수를 직접 뽑아도 된다.