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++빠 른 정렬 알고리즘 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!

    좋은 웹페이지 즐겨찾기