[Lajittele-Pikalajittelu]

[Lajittele - Pikalajittelu]

2024-07-12

Quick Sort on tehokas lajittelualgoritmi, joka perustuu hajota ja hallitse -strategiaan. Tämän lajittelualgoritmin ydinajatuksena on valita vertailuelementti, jakaa taulukko kahteen osaan siten, että vasemmalla olevat elementit ovat pienempiä tai yhtä suuria kuin vertailuelementit ja oikealla olevat elementit ovat suurempia kuin tai yhtä suuri kuin vertailuelementti ja käytä sitten rekursiivisesti pikalajittelua kahteen osaan.

Algoritmin vaiheet:

Valitse peruselementti : Valitse elementti taulukosta pivotiksi. Yleensä perustaksi valitaan ensimmäinen, viimeinen elementti tai satunnainen elementti.
Osio : Järjestä taulukko uudelleen siten, että peruselementtiä pienemmät elementit ovat peruselementin vasemmalla puolella ja peruselementtiä suuremmat elementit oikealla puolella. Samanaikaisesti pohjaelementti on lopullisessa lajittelupaikassa.
rekursiivinen lajittelu: Lajittele viiteelementin vasemmalla ja oikealla puolella olevat aliryhmät nopeasti rekursiivisesti.

Käyttöönoton vaiheet:

Seuraavassa on koodi nopean lajittelun toteuttamiseksi C-kielellä:

#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

Koodianalyysi:

vaihtotoiminto: Käytetään taulukon kahden elementin arvojen vaihtamiseen.
osiotoiminto: Valitse taulukon viimeinen elementti pohjaksi, jaa taulukko kahteen osaan ja palauta peruselementin lopullinen sijaintiindeksi.
QuickSort-toiminto : Rekursiivinen algoritmi nopean lajittelun toteuttamiseksi. Jokaisessa rekursiossa osiofunktiota käytetään ensin taulukon osiointiin, ja sitten kaksi ositettua osaa lajitellaan rekursiivisesti.
printArray-toiminto: Käytetään taulukon elementtien tulostamiseen lajittelutulosten helpottamiseksi.
päätoiminto: Testaa pikalajittelun toteutusta ja tulosta taulukko ennen lajittelua ja sen jälkeen.

aika monimutkaisuus:

Pikalajittelun aikamonimutkaisuus riippuu pääasiassa osiotoiminnan aikamonimutkaisuudesta ja rekursiivisten kutsujen määrästä. Pikalajittelun aikamonimutkaisuus on pahimmassa tapauksessa O(n^2), mutta keskimääräisessä tapauksessa O(n log n), mikä tekee siitä tehokkaan lajittelualgoritmin.

Yhteenveto:

Nopea lajittelu mahdollistaa tehokkaan lajittelun hajota ja hallitse -strategian ja osiotoimintojen avulla. Se ei vaadi ylimääräistä tallennustilaa (paitsi pinotilaa rekursiivisia puheluita varten) ja sen suorituskyky on hyvä keskimääräisissä olosuhteissa. Siksi pikalajittelu on yksi käytännön sovelluksissa yleisesti käytetyistä lajittelualgoritmeista, joka soveltuu erityisesti suurten tietojoukkojen lajittelutehtäviin.

Teknologian jakaminen