Cara melaksanakan algoritma quicksort dalam Go

Isih cepat ialah algoritma pengisihan klasik Kecekapan pengisihannya sangat tinggi dan kerumitan masa ialah O(n*logn). Di antara pelbagai bahasa pengaturcaraan, bahasa generasi baharu yang diwakili oleh Go juga menyediakan pelbagai pelaksanaan jenis pantas Artikel ini akan memperkenalkan cara melaksanakan algoritma isihan pantas dalam Go.

Idea asas algoritma isihan pantas ialah operasi teras isihan pantas adalah untuk memilih elemen tertentu (x) di antara semua elemen dalam tatasusunan (ia boleh menjadi nombor rawak atau pertama atau terakhir ), dipanggil elemen pangsi. Data yang akan diisih dibahagikan kepada dua bahagian bebas melalui satu laluan pengisihan Semua elemen dalam satu bahagian adalah lebih kecil daripada elemen sempadan, dan semua elemen di bahagian lain adalah lebih besar daripada elemen sempadan.

Secara khusus, kami boleh melaksanakan pengisihan pantas melalui langkah berikut:

• Pilih elemen dalam tatasusunan sebagai elemen perbandingan (pangsi).
• Letakkan elemen kurang daripada atau sama dengan pivot ke kiri dan elemen lebih besar daripada pivot ke kanan.
• Isih cepat secara rekursif masing-masing di sebelah kiri dan kanan.

Kod Golang adalah seperti berikut:

package main

import "fmt"

func QuickSort(arr []int, left, right int) {
    if left < right {
        pivotPos := partition(arr, left, right)
        QuickSort(arr, left, pivotPos-1)
        QuickSort(arr, pivotPos+1, right)
    }
}

func partition(arr []int, left, right int) int {
    pivot := arr[left]
    for left < right {
        for left < right && arr[right] >= pivot {
            right--
        }
        arr[left] = arr[right]
        for left < right && arr[left] <= pivot {
            left++
        }
        arr[right] = arr[left]
    }
    arr[left] = pivot
    return left
}

func main() {
    arr := []int{5, 8, 2, 6, 9, 1, 3, 7, 4}
    QuickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

Kod di atas melaksanakan proses pengisihan pantas. Fungsi partition dalam kod digunakan untuk membahagikan elemen, dan fungsi QuickSort digunakan untuk melaksanakan rekursi isihan pantas. Antaranya, penunjuk kiri dan kanan bergerak ke tengah masing-masing untuk mencari nombor yang perlu diganti, dan menentukan kedudukan baru melalui pertukaran, dan kembali ke kedudukan pangsi.

Dalam fungsi utama, susunan tatasusunan ditakrifkan, dan hasil selepas pengisihan pantas ialah output.

Ringkasnya, artikel ini menyediakan sedikit bantuan untuk kita memahami dan menguasai algoritma isihan pantas dengan memperkenalkan prinsip algoritma asas isihan pantas dan melaksanakan kod isih pantas dalam Golang.

Atas ialah kandungan terperinci Cara melaksanakan algoritma quicksort dalam Go. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!