The Go language implements bubble sort selection sort quick sort and insertion sort methods
- 2020-05-17 05:40:33
- OfStack
This article illustrates the methods of bubble sort, selection sort, quicksort and insertion sort in Go. Share with you for your reference. The specific analysis is as follows:
Algorithm is the soul of the program, and sorting algorithm is one of the most basic algorithms. There are many kinds of sorting algorithms. Here are four kinds of sorting algorithms: bubble sorting, selection sorting, quicksort and insertion sorting. Take small to large as an example.
Bubble sort
Bubble sort works by iterating over a given array several times, comparing two adjacent Numbers each time, and swapping them if the first is larger than the second. After the first iteration, the largest number is on the far right; After the second pass, the second largest number is in the second position on the right; And so on.
// Bubble sort (sort 10000 Random integers, which takes about time 145ms )
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 sort
Selection sort works by iterating through a given array several times, each time finding the index of the largest value.
// Select sort (sort 10000 Random integers, which takes about time 45ms )
func selectSort(nums []int) {
length := len(nums)
for i := 0; i < length; i++ {
maxIndex := 0
// Looking for the biggest 1 Number, 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. Quicksort
The principle of quicksort is to find a number, pivot, and divide the array 'on average' into two groups, so that all the Numbers in one group are greater than the Numbers in the other group, and pivot's position in the array is its correct position. Then, do this again for the two sets of arrays.
// Quicksort (sort 10000 Random integers, which takes about time 0.9ms )
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 sort
The principle of insertion sort is to traverse to the right from the second number, and move the element of this position to the left each time, and put it in a correct position (larger than the left and smaller than the right).
// Insert sort (sort 10000 Integers, which takes about time 30ms )
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, quicksort is found to be the most efficient.
I hope this article has helped you with your Go programming.