C++의 일반적인 정렬 알고리즘을 마스터하세요.

C++는 컴퓨터 프로그래밍에서 널리 사용되는 프로그래밍 언어이며, 정렬 알고리즘은 프로그래밍에서 일반적으로 사용되는 알고리즘 중 하나입니다. 정렬 알고리즘을 익히면 효율적인 프로그램 작성 능력을 향상하고 프로그래밍 기술을 향상시킬 수 있습니다. 이 기사에서는 C++에서 일반적으로 사용되는 정렬 알고리즘을 소개합니다.

1. 버블 정렬

버블 정렬은 인접한 요소를 순서대로 비교하고 더 큰 요소를 순서의 끝 부분으로 교환하여 정렬을 수행하는 기본 정렬 알고리즘입니다. 특히 버블 정렬은 각 라운드에서 인접한 요소의 크기를 비교하고 마지막 요소가 정렬될 때까지 더 큰 요소를 뒤로 바꿉니다.

C++ 코드는 다음과 같습니다.

void bubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

2. 선택 정렬

선택 정렬은 정렬되지 않은 부분에서 가장 작은 요소를 매번 선택하여 정렬된 부분의 마지막에 배치하는 간단한 정렬 알고리즘입니다. 정렬. 구체적으로 선택 정렬은 각 라운드에서 가장 작은 요소를 선택하여 현재 위치의 요소와 교환합니다.

C++ 코드는 다음과 같습니다.

void selectionSort(int arr[], int n)
{
    int minIndex, temp;
    for (int i = 0; i < n - 1; i++) {
        minIndex = i; // 记录最小元素的位置
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                // 更新最小元素的位置
                minIndex = j;
            }
        }
        // 交换元素
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

3. 삽입 정렬

삽입 정렬은 이미 정렬된 시퀀스에 요소를 삽입하여 더 긴 정렬 시퀀스를 얻는 간단하고 직관적인 정렬 알고리즘입니다. 특히, 삽입 정렬의 각 라운드는 정렬된 하위 배열에 요소를 삽입하고 나머지 요소를 뒤로 이동합니다.

C++ 코드는 다음과 같습니다.

void insertionSort(int arr[], int n)
{
    int key, j;
    for (int i = 1; i < n; i++) {
        key = arr[i]; // 待插入的元素
        j = i - 1;
        // 将大于待插入元素的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        // 将待插入元素插入到正确的位置
        arr[j+1] = key;
    }
}

4. 빠른 정렬

빠른 정렬은 효율적인 정렬 알고리즘입니다. 피벗 요소를 선택하여 시퀀스를 두 부분으로 분할합니다. 한 부분은 피벗 요소보다 작습니다. 다른 부분은 피벗 요소보다 크고 두 하위 시퀀스를 재귀적으로 정렬합니다. 구체적으로 말하면, 퀵 정렬은 각 라운드에서 피벗 요소를 선택하고 피벗 요소보다 작은 요소를 피벗 요소 왼쪽에 배치하고 피벗 요소보다 큰 요소를 오른쪽에 배치합니다. 그런 다음 왼쪽 및 오른쪽 하위 시퀀스가 ​​동일한 방식으로 재귀적으로 정렬됩니다.

C++ 코드는 다음과 같습니다.

void quickSort(int arr[], int left, int right)
{
    int i = left, j = right;
    int pivot = arr[(left + right) / 2]; // 选择枢纽元素
    while (i <= j) {
        // 找到左侧大于枢纽元素的元素
        while (arr[i] < pivot) {
            i++;
        }
        // 找到右侧小于枢纽元素的元素
        while (arr[j] > pivot) {
            j--;
        }
        // 交换左右元素
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    // 递归排序左侧和右侧的子序列
    if (left < j) {
        quickSort(arr, left, j);
    }
    if (i < right) {
        quickSort(arr, i, right);
    }
}

5. Merge sort

Merge sort는 시퀀스를 두 개의 하위 시퀀스로 나누고 각 하위 시퀀스를 별도로 정렬한 다음 마지막으로 두 하위 시퀀스를 병합하는 정렬 알고리즘입니다. . 특히 병합 정렬은 먼저 시퀀스를 두 개의 하위 시퀀스로 분할하고 두 개의 하위 시퀀스를 재귀적으로 정렬한 다음 두 개의 정렬된 하위 시퀀스를 하나의 정렬된 시퀀스로 병합합니다.

C++ 코드는 다음과 같습니다.

void merge(int arr[], int left, int mid, int right)
{
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];

    // 将数据拷贝到两个临时数组中
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    i = 0; // 左侧子数组的索引
    j = 0; // 右侧子数组的索引
    k = left; // 合并后的数组的索引
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 将左侧子数组的剩余元素拷贝到合并后的数组中
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    // 将右侧子数组的剩余元素拷贝到合并后的数组中
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right)
{
    if (left < right) {
        int mid = left + (right - left) / 2;
        // 递归排序左侧和右侧的子序列
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        // 合并两个有序子数组
        merge(arr, left, mid, right);
    }
}

위는 C++에서 일반적으로 사용되는 5가지 정렬 알고리즘입니다. 알고리즘은 지루해 보일 수도 있지만 정렬 알고리즘을 학습하면 프로그래밍의 효율성과 품질을 향상시킬 수 있는 중요한 부분입니다.

위 내용은 C++의 일반적인 정렬 알고리즘을 마스터하세요.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!