This article describes the methods of implementing bubble sorting, selection sorting, quick sorting and insert sorting in Go language. Share it for your reference. The specific analysis is as follows:
Algorithms are the soul of programs, and sorting algorithms are the most basic algorithms. There are many sorting algorithms. Here are the sorting algorithms in 4: bubble sort, selection sort, quick sort and insert sort, taking from small to large as an example.
1. Bubble sorting
The principle of bubble sorting is to perform multiple traversals on a given array, and each time compare two adjacent numbers. If the previous one is larger than the next one, then exchange these two numbers. After the first traversal, the largest number is on the rightmost; after the second traversal, the second largest number is on the second rightmost position; and so on.
func bubbleSort(nums []int) {
for i := 0; i < len(nums); i++ {
for j := 1; j < len(nums)-i; j++ {
if nums[j] < nums[j-1] {
//exchange
nums[j], nums[j-1] = nums[j-1], nums[j]
}
}
}
}
2. Select sorting
The principle of selecting sorting is to traverse the given array multiple times, each time finding the index of the largest value.
func selectSort(nums []int) {
length := len(nums)
for i := 0; i < length; i++ {
maxIndex := 0
//Find the largest number and save the index value
for j := 1; j < length-i; j++ {
if nums[j] > nums[maxIndex] {
maxIndex = j
}
}
nums[length-i-1], nums[maxIndex] = nums[maxIndex], nums[length-i-1]
}
}
3. Quick sort
The principle of quick sorting is to first find a number, pivot, divide the array into two groups, so that all numbers in one group are larger than the numbers in the other group, and at this time the position of pivot in the array is its correct position. Then, do this again on these two arrays.
func quickSort(nums []int) {
recursionSort(nums, 0, len(nums)-1)
}
func recursionSort(nums []int, left int, right int) {
if left < right {
pivot := partition(nums, left, right)
recursionSort(nums, left, pivot-1)
recursionSort(nums, pivot+1, right)
}
}
func partition(nums []int, left int, right int) int {
for left < right {
for left < right && nums[left] <= nums[right] {
right--
}
if left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
}
for left < right && nums[left] <= nums[right] {
left++
}
if left < right {
nums[left], nums[right] = nums[right], nums[left]
right--
}
}
return left
}
4. Insert sorting
The principle of insertion sort is to traverse to the right starting from the second number, and move the element at that position to the left each time, and place it in the correct position (larger than the left and smaller than the right).
func insertSort(nums []int) {
for i := 1; i < len(nums); i++ {
if nums[i] < nums[i-1] {
j := i - 1
temp := nums[i]
for j >= 0 && nums[j] > temp {
nums[j+1] = nums[j]
j--
}
nums[j+1] = temp
}
}
}
Through multiple tests, we can find that quick sorting is the most efficient.
I hope this article will be helpful to everyone's Go language programming.