c+빠 른 정렬 알고리즘[프로 세 스 도해]

첫째,알고리즘 설명
빠 른 정렬 은 C.A.R.Hoare 가 1962 년 에 제 기 했 는데 이 알고리즘 은 현재 실천 에서 가장 자주 사용 되 고 실 용적 이 며 효율 적 인 가장 좋 은 정렬 알고리즘 이다.
빠 른 정렬 알고리즘 은 사상 을 나 누 는 알고리즘 을 사용 하고 알고리즘 은 세 단계 로 나 뉜 다.
1.배열 에서 하나의 요 소 를 기수 v(우 리 는 경계 요소 라 고 부른다)로 추출 하고 보통 첫 번 째,마지막 요소 나 중간 요 소 를 취한 다.
2.남 은 요소 중 v 보다 작은 요 소 를 v 의 왼쪽 으로 이동 시 키 고 v 보다 큰 요 소 를 v 의 오른쪽 으로 이동 합 니 다.
3.모든 요소 가 정렬 될 때 까지 좌우 두 개의 파 티 션 을 반복 합 니 다.
둘째,알고리즘 실현

/*      */
int partition(int a[], int p, int r) {
  int key = a[r];//     
  int i = p - 1;
  for (int j = p; j < r; j++)
  { 
    if (a[j] <= key)
    {     
      i++;
      //i      key         ，     key  a[j]  ，i+1         
      exchange(&a[i], &a[j]);
    }   
  } 
  exchange(&a[i + 1], &a[r]);// key      ，     key ，     key  。
  return i + 1;
}
 
void quickSort(int a[], int p, int r) {
  int position = 0;
  if (p<r)
  {
    position = partition(a,p,r);//           
    quickSort(a,p,position-1);//      
    quickSort(a, position + 1,r);//      
  } 
}
 
void main() {
  int d[] = { 6,4,1,8,7,5 };
  cout << "     { 6,4,1,8,7,5 } " << endl; 
  quickSort(d, 0, 5);
  print_arr(d, 6);
 
}

두 개의 보조 함수:

void exchange(int * a, int* b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}
void print_arr(int *a, int size) //     
{
  cout << "    ：";
  for (int i = 0; i<size; i++)  //     
  {
    cout << a[i] << " ";
  }
  cout << endl << endl;
}

테스트 출력:

셋째,알고리즘 도해 분석
프로그램 이 어떻게 돌아 가 는 지 구체 적 으로 분석 해 보 겠 습 니 다.
quickSort(d, 0, 5);가장 큰 원소 5 를 기수 로 하고,
프로그램 초기 화 시 p=0,r=5,i=-1,j=0,key=5

위의 그림 을 통 해 우 리 는 관찰 했다.
1.i 가 점점 증가 합 니 다.이것 은 key=5 보다 작은 마지막 요 소 를 대표 합 니 다.j 도 메 인 키 에서 증가 하여 key 앞의 요소 가 멈 출 때 까지 합 니 다.
2.이때 마지막 요소 7 까지 순환 되 었 고 5 를 기수 로 하 는 순환 이 끝 났 습 니 다.이때 i=1,a[i+1]=6,교환 6 과 5 교환 을 통 해 이번 순환 을 완성 합 니 다.
i+1=2 를 되 돌려 주 고 색인 2 를 분계선 으로 2 개의 배열 로 나 누 어 재 귀 순환 에 들 어가 위의 그림 과 유사 한 작업 을 수행 합 니 다.
넷 째,총결산
빠 른 정렬 이 빠 른 이 유 는 거품 정렬 에 비해 그의 교환 은 점프 식 이다.그의 최 악의 시간 복잡 도 는 O(N2)와 거품 이 발생 하 는 것 과 같 지만 그의 평균 시간 복잡 도 는 O(nlog2N)이 고 현지 정렬 알고리즘 이다.
다른 사람 이 쓴 알고리즘 소 개 를 많이 보 았 지만 아직도 뚜렷 하지 않 아서 자신 이 박문 을 한 편 쓰기 로 결정 했다.필요 한 사람 이 신속하게 이해 할 수 있 도록 도와 주 고 글 의 용 도 는 자신 이 그린 것 이다.
이상 의 c++빠 른 정렬 알고리즘[과정 도해]은 바로 편집장 이 여러분 에 게 공유 한 모든 내용 입 니 다.여러분 에 게 참고 가 되 고 저희 도 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.