빠른 정렬은 고전적인 정렬 알고리즘으로 정렬 효율성이 매우 높으며 시간 복잡도는 O(n*logn)입니다. 다양한 프로그래밍 언어 중에서 Go로 대표되는 차세대 언어도 다양한 퀵 정렬 구현을 제공합니다. 이 글에서는 Go에서 퀵 정렬 알고리즘을 구현하는 방법을 소개합니다.
빠른 정렬 알고리즘의 기본 아이디어는 빠른 정렬의 핵심 작업이 배열의 모든 요소 중에서 특정 요소(x)(난수 또는 첫 번째 또는 마지막 요소일 수 있음)를 선택하는 것입니다. , 이를 분할 요소(피벗)라고 합니다. 정렬할 데이터는 원패스 정렬을 통해 두 개의 독립적인 부분으로 나누어집니다. 한 부분의 모든 요소는 경계 요소보다 작고, 다른 부분의 모든 요소는 경계 요소보다 큽니다.
구체적으로 다음 단계를 통해 빠른 정렬을 구현할 수 있습니다.
Golang 코드는 다음과 같습니다.
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) }
위 코드는 빠른 정렬 프로세스를 구현합니다. 코드의 분할 함수는 요소를 분할하는 데 사용되며 QuickSort 함수는 빠른 정렬 재귀를 구현하는 데 사용됩니다. 그 중 왼쪽 포인터와 오른쪽 포인터가 각각 중앙으로 이동하여 교체해야 할 번호를 찾고, 교체를 통해 새로운 위치를 결정한 후 피벗 위치로 돌아옵니다.
메인 함수에는 배열 arr을 정의한 후 퀵 정렬 후의 결과를 출력합니다.
요약하자면, 이 글은 퀵 정렬의 기본 알고리즘 원리를 소개하고 Golang의 코드를 통해 퀵 정렬을 구현함으로써 퀵 정렬 알고리즘을 이해하고 익히는 데 도움이 됩니다.
위 내용은 Go에서 퀵 정렬 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!