[Sortieren-Schnellsortieren]

2024-07-12

Quick Sort ist ein effizienter Sortieralgorithmus, der auf der Divide-and-Conquer-Strategie basiert. Die Kernidee dieses Sortieralgorithmus besteht darin, ein Benchmark-Element auszuwählen und das Array in zwei Teile aufzuteilen, sodass die Elemente auf der linken Seite kleiner oder gleich dem Benchmark-Element und die Elemente auf der rechten Seite größer oder gleich sind gleich dem Benchmark-Element und wenden Sie dann rekursiv eine Schnellsortierung auf die beiden Teile an.

Algorithmusschritte:

Basiselement auswählen : Wählen Sie ein Element aus dem Array als Drehpunkt aus. Als Basis wird meist das erste Element, das letzte Element oder ein zufälliges Element gewählt.
Partition : Ordnen Sie das Array neu an, sodass sich Elemente, die kleiner als das Basiselement sind, auf der linken Seite des Basiselements befinden und Elemente, die größer als das Basiselement sind, auf der rechten Seite. Gleichzeitig befindet sich das Basiselement an der endgültigen Sortierposition.
rekursive Sortierung: Sortieren Sie die Subarrays auf der linken und rechten Seite des Referenzelements schnell und rekursiv.

Umsetzungsschritte:

Das Folgende ist der Code zum Implementieren der Schnellsortierung in der C-Sprache:

#include <stdio.h>

// 函数：交换数组中两个元素的值
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;  // 初始化分区索引，比基准元素小的元素会放在左边

    for (int j = low; j < high; 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++) {
        printf("%d ", arr[i]);
    }
    printf("n");
}

// 主函数：测试快速排序的实现
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("排序后的数组: n");
    printArray(arr, n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

Code-Analyse:

Swap-Funktion: Wird verwendet, um die Werte zweier Elemente in einem Array auszutauschen.
Partitionsfunktion: Wählen Sie das letzte Element im Array als Basis aus, teilen Sie das Array in zwei Teile und geben Sie den endgültigen Positionsindex des Basiselements zurück.
QuickSort-Funktion : Implementiert einen rekursiven Algorithmus zur schnellen Sortierung. Bei jeder Rekursion wird zunächst die Partitionsfunktion zum Partitionieren des Arrays verwendet, und dann werden die beiden partitionierten Teile rekursiv sortiert.
printArray-Funktion: Wird zum Drucken von Array-Elementen zur einfachen Anzeige der Sortierergebnisse verwendet.
Hauptfunktion: Testen Sie die Implementierung der Schnellsortierung und drucken Sie das Array vor und nach der Sortierung.

Zeitkomplexität:

Die zeitliche Komplexität der Schnellsortierung hängt hauptsächlich von der zeitlichen Komplexität der Partitionsoperation und der Anzahl der rekursiven Aufrufe ab. Die Zeitkomplexität von Quicksort beträgt im schlimmsten Fall O(n^2), im Durchschnitt jedoch O(n log n), was es zu einem effizienten Sortieralgorithmus macht.

Zusammenfassen:

Die schnelle Sortierung ermöglicht eine effiziente Sortierung durch die Divide-and-Conquer-Strategie und Partitionsoperationen. Es erfordert keinen zusätzlichen Speicherplatz (außer Stapelspeicher für rekursive Aufrufe) und bietet unter durchschnittlichen Umständen eine gute Leistung. Daher ist die schnelle Sortierung einer der in praktischen Anwendungen am häufigsten verwendeten Sortieralgorithmen und eignet sich besonders für Sortieraufgaben großer Datenmengen.

Technologieaustausch