So verwenden Sie den Quicksort-Algorithmus in C++

So verwenden Sie den Schnellsortierungsalgorithmus in C++

Der Schnellsortierungsalgorithmus ist ein häufig verwendeter Sortieralgorithmus. Seine Kernidee besteht darin, die zu sortierende Sequenz kontinuierlich in zwei kleinere und größere Teilsequenzen zu unterteilen und diese dann rekursiv zu sortieren , wodurch letztendlich die gesamte Sequenz geordnet wird. In diesem Artikel wird die Verwendung des Schnellsortierungsalgorithmus in C++ vorgestellt und spezifische Codebeispiele bereitgestellt.

Die Implementierungsidee des Schnellsortierungsalgorithmus lautet wie folgt:

1. Wählen Sie einen Referenzelement-Pivot aus, der ein beliebiges Element in der Sequenz sein kann. Normalerweise wird das erste oder letzte Element als Basis gewählt.
2. Platzieren Sie die Elemente in der Reihenfolge, die kleiner als der Drehpunkt sind, links vom Drehpunkt, und die Elemente, die größer als der Drehpunkt sind, werden rechts platziert.
3. Sortieren Sie die linken und rechten Teilsequenzen schnell rekursiv.

Das Folgende ist ein Codebeispiel mit C++ zur Implementierung des Schnellsortierungsalgorithmus:

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

Nachdem Sie den obigen Code ausgeführt haben, erhalten Sie die folgende Ausgabe:

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

Dieser Code implementiert den Schnellsortierungsalgorithmus, indem zuerst das letzte Element ausgewählt wird als Basis und verwenden Sie dann die Partitionsfunktion, um das Array zu teilen, indem Sie Elemente, die kleiner als die Grundlinie sind, links und Elemente, die größer als die Grundlinie sind, rechts platzieren. Anschließend werden die linken und rechten Unterarrays rekursiv sortiert, bis das gesamte Array sortiert ist.

Zusammenfassung:
Schnellsortierung ist ein effizienter Sortieralgorithmus. Seine durchschnittliche Zeitkomplexität beträgt O(n log n). Es ist relativ einfach, den Schnellsortierungsalgorithmus mit C++ zu implementieren. Anhand der obigen Codebeispiele können Sie die Grundprinzipien und Implementierungsmethoden des Schnellsortierungsalgorithmus verstehen und ihn auch in praktischen Anwendungen flexibel verwenden.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den Quicksort-Algorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!