C++에서 퀵 정렬 알고리즘을 사용하는 방법

C++에서 빠른 정렬 알고리즘을 사용하는 방법

빠른 정렬 알고리즘은 일반적으로 사용되는 정렬 알고리즘으로, 정렬할 시퀀스를 두 개의 작은 하위 시퀀스와 큰 하위 시퀀스로 연속적으로 나눈 후 하위 시퀀스를 재귀적으로 정렬하는 것입니다. , 궁극적으로 전체 시퀀스를 정렬합니다. 이 기사에서는 C++에서 빠른 정렬 알고리즘을 사용하는 방법을 소개하고 구체적인 코드 예제를 제공합니다.

빠른 정렬 알고리즘의 구현 아이디어는 다음과 같습니다.

1. 순서의 모든 요소가 될 수 있는 참조 요소 피벗을 선택합니다. 일반적으로 첫 번째 또는 마지막 요소가 기본으로 선택됩니다.
2. 피벗보다 작은 순서의 요소는 피벗 왼쪽에 배치하고, 피벗보다 큰 요소는 오른쪽에 배치합니다.
3. 왼쪽 및 오른쪽 하위 시퀀스를 재귀적으로 빠르게 정렬합니다.

다음은 C++를 사용하여 빠른 정렬 알고리즘을 구현하는 코드 예제입니다.

#include <iostream>
using namespace std;

// 交换两个元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 快速排序的划分函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = (low - 1);  // i代表小于基准的元素的最右边界
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);  // 将小于基准的元素放在左边
        }
    }
    swap(&arr[i + 1], &arr[high]);  // 将基准元素放在合适的位置
    return (i + 1);
}

// 快速排序的递归函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // 划分数组
        quickSort(arr, low, pi - 1);  // 对左子数组进行递归排序
        quickSort(arr, pi + 1, high);  // 对右子数组进行递归排序
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "原始数组：";
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    cout << "排序后的数组：";
    printArray(arr, n);
    return 0;
}

위 코드를 실행하면 다음과 같은 출력이 표시됩니다.

原始数组：10 7 8 9 1 5 
排序后的数组：1 5 7 8 9 10 

이 코드는 빠른 정렬 알고리즘을 구현하고 먼저 마지막 요소를 선택합니다. 그런 다음 파티션 기능을 사용하여 배열을 나누어 기준선보다 작은 요소를 왼쪽에 배치하고 기준선보다 큰 요소를 오른쪽에 배치합니다. 그런 다음 전체 배열이 정렬될 때까지 왼쪽 및 오른쪽 하위 배열이 재귀적으로 정렬됩니다.

요약:
빠른 정렬은 효율적인 정렬 알고리즘입니다. 평균 시간 복잡도는 O(n log n)입니다. C++를 사용하여 퀵 정렬 알고리즘을 구현하는 것은 비교적 간단합니다. 위의 코드 예제를 통해 퀵 정렬 알고리즘의 기본 원리와 구현 방법을 이해할 수 있으며, 실제 응용에서도 유연하게 사용할 수 있습니다.

위 내용은 C++에서 퀵 정렬 알고리즘을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!