Sorting algorithm golang implementation

The sorting algorithm is one of the most basic algorithms in the field of computer science. It is the process of rearranging a set of data in a specific order. Common sorting algorithms include bubble sort, selection sort, insertion sort, quick sort, etc. This article will take the golang language as an example to introduce the implementation of several common sorting algorithms.

1. Bubble Sort

Bubble Sort is a simple and intuitive sorting algorithm. It repeatedly traverses the sequence to be sorted and compares two elements at a time. If they If the order is wrong, swap positions. The specific implementation process is as follows:

func bubbleSort(arr []int) []int {

n := len(arr)
for i := 0; i < n-1; i++ {
    for j := 0; j < n-i-1; j++ {
        if arr[j] > arr[j+1] {
            arr[j], arr[j+1] = arr[j+1], arr[j]
        }
    }
}
return arr

}

2. Selection sorting

Selection sorting ( Selection Sort) is a simple and intuitive sorting algorithm. Its implementation process sequentially selects the smallest (or largest) element from the data elements to be sorted, stores it at the starting position of the sequence, and then selects the remaining unsorted elements. Continue to find the smallest (or largest) element in the sequence and place it at the end of the sorted sequence. The specific implementation process is as follows:

func selectionSort(arr []int) []int {

n := len(arr)
for i := 0; i < n-1; i++ {
    minIndex := i
    for j := i + 1; j < n; j++ {
        if arr[j] < arr[minIndex] {
            minIndex = j
        }
    }
    arr[i], arr[minIndex] = arr[minIndex], arr[i]
}
return arr

}

3. Insertion sort

Insertion sort ( Insertion Sort) is a simple and intuitive sorting algorithm. Its basic idea is to insert the data elements to be sorted into an already sorted sequence according to their key size. Initially, it is assumed that the first data element It forms an ordered sequence by itself, and the remaining data elements are unordered. The specific implementation process is as follows:

func insertionSort(arr []int) []int {

n := len(arr)
for i := 1; i < n; i++ {
    tmp := arr[i]
    j := i - 1
    for ; j >= 0 && arr[j] > tmp; j-- {
        arr[j+1] = arr[j]
    }
    arr[j+1] = tmp
}
return arr

}

4. Quick sort

Quick sort ( Quick Sort) is an efficient sorting algorithm that decomposes data elements into smaller sets of independent elements in a self-recursive manner to achieve sorting purposes. The specific implementation process is as follows:

func quickSort(arr []int) []int {

if len(arr) <= 1 {
    return arr
}
pivot := arr[0]
left, right := 0, len(arr)-1
for i := 1; i <= right; {
    if arr[i] < pivot {
        arr[left], arr[i] = arr[i], arr[left]
        left++
        i++
    } else if arr[i] > pivot {
        arr[right], arr[i] = arr[i], arr[right]
        right--
    } else {
        i++
    }
}
quickSort(arr[:left])
quickSort(arr[left+1:])
return arr

}

The above is the golang language implementation of four basic sorting algorithms Way. In the actual development process, according to the size of the data and the characteristics of the data, it is necessary to select an appropriate sorting algorithm for sorting to achieve better sorting effects.

The above is the detailed content of Sorting algorithm golang implementation. For more information, please follow other related articles on the PHP Chinese website!