Beherrschen Sie gängige Sortieralgorithmen in C++

C++ ist eine in der Computerprogrammierung weit verbreitete Programmiersprache, und Sortieralgorithmen gehören zu den am häufigsten verwendeten Algorithmen in der Programmierung. Das Beherrschen von Sortieralgorithmen kann Ihre Fähigkeit verbessern, effiziente Programme zu schreiben und Ihre Programmierkenntnisse zu verbessern. In diesem Artikel werden häufig verwendete Sortieralgorithmen in C++ vorgestellt.

1. Bubble Sort

Bubble Sort ist ein grundlegender Sortieralgorithmus, der die Sortierung durch den Vergleich benachbarter Elemente in der Reihenfolge und den Austausch größerer Elemente am Ende der Sequenz erreicht. Insbesondere vergleicht die Blasensortierung die Größe benachbarter Elemente in jeder Runde und tauscht größere Elemente rückwärts aus, bis das letzte Element sortiert ist.

Der C++-Code lautet wie folgt:

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. Auswahlsortierung

Auswahlsortierung ist ein einfacher Sortieralgorithmus, der jedes Mal das kleinste Element im unsortierten Teil auswählt und es am Ende des sortierten Teils einfügt, also implementieren Sortierung. Insbesondere wählt die Auswahlsortierung das kleinste Element in jeder Runde aus und tauscht es mit dem Element an der aktuellen Position aus.

Der C++-Code lautet wie folgt:

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. Einfügungssortierung

Einfügungssortierung ist ein einfacher und intuitiver Sortieralgorithmus, der ein Element in eine bereits sortierte Sequenz einfügt, um eine längere sortierte Sequenz zu erhalten. Konkret fügt jede Runde der Einfügungssortierung ein Element in das sortierte Subarray ein und verschiebt die übrigen Elemente nach hinten.

Der C++-Code lautet wie folgt:

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. Schnellsortierung

Schnellsortierung ist ein effizienter Sortieralgorithmus, der die Sequenz in zwei Teile aufteilt, indem er ein Pivotelement auswählt, wobei ein Teil kleiner als das Pivotelement ist und der Der andere Teil ist größer als das Pivotelement und sortiert die beiden Teilsequenzen rekursiv. Insbesondere wählt die Schnellsortierung in jeder Runde ein Pivot-Element aus und platziert Elemente, die kleiner als das Pivot-Element sind, links vom Pivot-Element und Elemente, die größer als das Pivot-Element sind, rechts vom Pivot-Element. Dann werden die linken und rechten Teilsequenzen auf die gleiche Weise rekursiv sortiert.

Der C++-Code lautet wie folgt:

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-Sortierung

Merge-Sortierung ist ein klassischer Divide-and-Conquer-Sortieralgorithmus. Er unterteilt die Sequenz in zwei Teilsequenzen, sortiert jede Teilsequenz separat und führt die beiden Sequenzen schließlich zusammen . Insbesondere teilt die Zusammenführungssortierung die Sequenz zunächst in zwei Teilsequenzen auf, sortiert die beiden Teilsequenzen rekursiv und führt dann die beiden geordneten Teilsequenzen zu einer geordneten Sequenz zusammen.

Der C++-Code lautet wie folgt:

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);
    }
}

Die oben genannten sind die fünf Sortieralgorithmen, die häufig in C++ verwendet werden. Obwohl Algorithmen langweilig erscheinen mögen, sind sie ein wichtiger Teil der Programmierung. Durch das Erlernen von Sortieralgorithmen können wir die Effizienz und Qualität der Programmierung verbessern.

Das obige ist der detaillierte Inhalt vonBeherrschen Sie gängige Sortieralgorithmen in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!