C/C++빠 른 정렬 알고리즘 의 사고방식 과 원리 해석 실현

빠 른 정렬
1.알고리즘 사상
빠 른 정렬 의 기본 사상:한 번 의 정렬 을 통 해 대기 기록 을 독립 된 두 부분 으로 나 눌 수 있 습 니 다.그 중에서 일부 기록 의 키 워드 는 모두 다른 부분의 키워드 보다 작 으 면 이 두 부분의 기록 을 계속 정렬 하여 전체 서열 의 질 서 를 달성 할 수 있 습 니 다.
2.실현 원리
2.1.두 개의 변 수 를 low,high 로 설정 하고 정렬 을 시작 할 때:low=0,high=size-1.
2.2 전체 배열 은 기준 이 정확 한 위 치 를 찾 고 모든 요 소 는 기준 보다 작은 것 을 기준 앞 에 놓 으 며 모든 요 소 는 기준 보다 큰 것 을 기준 뒤에 놓는다.
4.567917.기본 배열 의 첫 번 째 수 는 기준 데이터 이 고 key,즉 key=array[low]에 값 을 부여 합 니 다

기본 배열 의 첫 번 째 수 를 기준 으로 하기 때문에 뒤에서 부터 앞으로 검색(highC)하고 key 보다 작은 array[high]를 찾 으 면 array[high]를 array[low],즉 array[low]=array[high]에 부여 합 니 다.(순환 조건 은 array[high]>=key;종료 시 array[high]

이때 앞에서 부터 뒤로 검색(low+)하고 key 보다 큰 array[low]를 찾 으 면 array[low]를 array[high],즉 array[high]=array[low]에 부여 합 니 다.(순환 조건 은 array[low]<=key;종료 시 array[low]>key)

4.567917.2-3 단 계 를 순환 하여 low=high 까지 이 위 치 는 기준 위치 입 니 다4.567917.기준 데 이 터 를 현재 위치 에 부여 합 니 다2.3.첫 번 째 로 찾 은 기준 위 치 는 다음 의 경계 점 으로 한다.
2.4 재 귀적 호출(recursive)분계 점 앞 과 분계 점 뒤의 하위 배열 순 서 는 2.2,2.3,2.4 의 절 차 를 반복 한다.
2.5.최종 적 으로 정렬 된 배열 을 얻 을 수 있 습 니 다.
3.동적 프레젠테이션


4.전체 코드
세 함수
기본 삽입 함수:int getStandard(int array[],int low,int high)
(기준 위치 아래 표 시 를 되 돌려 줍 니 다)
재 귀적 정렬 함수:void quickSort(int array[],int low,int high)
주 함수:int main()

#include <stdio.h>
#include <stdlib.h>

void display(int* array, int size) {
  for (int i = 0; i < size; i++) {
    printf("%d ", array[i]);
  }
  printf("
");
}

int getStandard(int array[], int i, int j) {
  //     
  int key = array[i];
  while (i < j) {
    //             ，         
    //                 ,        j   
    while (i < j && array[j] >= key) {
      j--;
    }
    //      array[i]    ，       array[j]    
    if (i < j) {
      array[i] = array[j];
    }
    //                ,        i   
    while (i < j && array[i] <= key) {
      i++;
    }
    //      array[j]    ，       array[i]    
    if (i < j) {
      array[j] = array[i];
    }
  }
  //       i   j   ,    i   j    key        
  //            
  array[i] = key;
  return i;
}

void QuickSort(int array[], int low, int high) {
  //         low
  if (low < high) {
    //       
    int standard = getStandard(array, low, high);
    //       
    //     
    QuickSort(array, low, standard - 1);
    //     
    QuickSort(array, standard + 1, high);
  }
}

//          
// void QuickSort(int array[], int low, int high) {
//   if (low < high) {
//     int i  = low;
//     int j  = high;
//     int key = array[i];
//     while (i < j) {
//       while (i < j && array[j] >= key) {
//         j--;
//       }
//       if (i < j) {
//         array[i] = array[j];
//       }
//       while (i < j && array[i] <= key) {
//         i++;
//       }
//       if (i < j) {
//         array[j] = array[i];
//       }
//     }
//     array[i] = key;
//     QuickSort(array, low, i - 1);
//     QuickSort(array, i + 1, high);
//   }
// }

int main() {
  int array[] = {49, 38, 65, 97, 76, 13, 27, 49, 10};
  int size  = sizeof(array) / sizeof(int);

  //     
  printf("%d 
", size);
  QuickSort(array, 0, size - 1);
  display(array, size);

  // int size   = 20;
  // int array[20] = {0};         //      
  // for (int i = 0; i < 10; i++) {    //     
  //   for (int j = 0; j < size; j++) { //     
  //     array[j] = rand() % 1000;  //         0~999
  //   }
  //   printf("     ：");
  //   display(array, size);
  //   QuickSort(array, 0, size - 1);
  //   printf("     ：");
  //   display(array, size);
  //   printf("
");
  // }

  return 0;
}

5.결과 전시
(재 귀적 호출,매번 정렬 결 과 를 보 여주 기 어렵 습 니 다)

6.알고리즘 분석
시간 복잡 도:
가장 좋 은:O(n l o g 2 n)O(n log {2} n) O(nlog2​n) 최 악:O(n 2)O(n^2)O(n2)평균:O(n l o g 2 n)O(n log {2} n) O(nlog2​n) 공간 복잡 도:O(n l o g 2 n)O(n log {2} n) O(nlog2​n)
안정성:불안정
여기 서 C/C++빠 른 정렬 알고리즘 을 실현 하 는 사고 와 원리 해석 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++빠 른 정렬 알고리즘 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!