빠 른 정렬 k 대수 구하 기

표 병 을 빨리 이용 하 는 사상 이지 만 매번 범위 의 크기 를 비교 하고 정확 한 순 서 를 매기 지 못 한다.

역시 정성 이 필요 한 범위 문 제 를 신속하게 해결 하 는 데 적용 된다. 예 를 들 어 k 가 크다 (앞 뒤 를 크기 로 정 하지만 정렬 하지 않 는 다).

구 해 제 k 대: 판단 을 통 해 표 시 를 하고 k 의 절반 만 계산한다.

빠 른 줄 은 넓 은 것 에서 좁은 것 으로 돌아 가 는 것 이다.

빠 른 배열: a. 중추 가 돌아 가 려 고 합 니 다. b. i 는 항상 큰 값 을 가리 키 고 있 습 니 다.

void quick_sort(int *A, int x, int y)//    
{
if(x < y)//  1 0      
{
  int i = x;
  int j = y;
//   ，      ,      ，4%~5%。
  int m = x + (y-x)/2;
  if(A[x] > A[m])
      if(A[x] > A[y])
          if(A[m] > A[y])
              swap(A[m],A[y]);
      else
          swap(A[x],A[y]);
  else//A[x]<A[m]
      if(A[x] > A[y])
          swap(A[x],A[y]);
      else
          if(A[y] > A[m])
              swap(A[m],A[y]);
//    
  int key = A[y];

  while(true)
  {
      while(i < j && A[i] <= key)//         ，  A[i]       
          ++i;
      while(i < j && A[j] >= key)
          --j;
      if(i < j)
          swap(A[i],A[j]);
      else
          break;
      ++i;//    --j,    bug。
  }
  swap(A[i],A[y]);//     

  quick_sort( A,x, i-1);
  quick_sort( A,i+1, y);
}
}

빠 른 정렬 k 대수 구하 기

좋은 웹페이지 즐겨찾기