Bubble sort
Personal understanding
Two-layer loop, the number of outer loop = the number of elements; When ARR [j] is greater than ARR [j+1], the two values are exchanged. When the inner loop ends, there are at most n-1 swaps, and the maximum value is placed at the tail; When there is no element exchange in an outer loop, it indicates that the sequence is in order and the outer loop can be terminated in advance.
func BubbleSort(arr []int) []int {
length := len(arr)
for i:=0; i<length- 1; i++ {for j:=0; j<length- 1-i; j++{if arr[j]>arr[j+1] {
// Big bubbles go up
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
return arr
}
Copy the codeSelection sort
Personal understanding
Select the smallest (largest) element from the original array and place it at the beginning of the sequence; Then select the smallest (largest) element from the remaining sequence and place it at the end of the sorted sequence.
func SelectSort(arr []int) []int {
for i := 0; i < len(arr)- 1; i++ {
for j := i + 1; j <= len(arr)- 1; j++ {
if arr[j] < arr[i] {
arr[j], arr[i] = arr[i], arr[j]
}
}
}
return arr
}
Copy the codeInsertion sort
Personal understanding
Construct the ordered sequence. For the unordered data, scan the sorted sequence from back to front to find the appropriate position K and insert. Everything after position K needs to be moved back.
func InsertSort(arr []int) []int {
for i := 1; i <= len(arr)- 1; i++ {
for j := i; j > 0; j-- {
if arr[j- 1] > arr[j] {
arr[j- 1], arr[j] = arr[j], arr[j- 1]}}}return arr
}
Copy the codeQuick sort
Personal understanding
The records to be arranged are divided into independent parts A and B through A sorting. Part A is all less than the reference value, and part B is all greater than the reference value. Then in the two parts to do the same processing, has completed the sorting function.
func QuickSort(arr []int, l, r int) []int {
if l < r {
pivot := arr[r]
i := l - 1
for j := l; j < r; j++ {
if arr[j] <= pivot {
i++
arr[j], arr[i] = arr[i], arr[j]
}
}
i++
arr[r], arr[i] = arr[i], arr[r]
QuickSort(arr, l, i- 1)
QuickSort(arr, i+1, r)
}
return arr
}
Copy the codeHill sorting
Personal understanding
The original array is divided into several small arrays for direct insertion sort respectively. When the entire array is “basically ordered”, the whole array is directly inserted in order.
func ShellSort(arr []int, batchSize int) []int {
if batchSize < 1 {
return []int{}}// k: batch index of each batch element, between [0, batchSize)
for k := 0; k < batchSize; k++ {
Insert sort is used
for j := 1; batchSize*j+k < len(arr); j++ { // j: Used to obtain the number of batches in the KTH element of each batch
for n := j; n > 0; n-- {
pre := batchSize*(n- 1) + k
next := batchSize*n + k
if arr[next] < arr[pre] {
arr[next], arr[pre] = arr[pre], arr[next]
}
}
}
}
ShellSort(arr, batchSize/2)
return arr
}
Copy the codeMerge sort
Personal understanding
Divide the large array into n small arrays, first make the small arrays orderly, and then merge all the small arrays according to the size, get the sorting result.
func MergeSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
i := len(arr) / 2
left := MergeSort(arr[0:i])
right := MergeSort(arr[i:])
result := make([]int.0)
m, n := 0.0 // Left and right index positions
l, r := len(left), len(right)
for m < l && n < r {
if left[m] > right[n] {
result = append(result, right[n])
n++
continue
}
result = append(result, left[m])
m++
}
result = append(result, right[n:]...)
result = append(result, left[m:]...)
return result
}
Copy the codeThe complete code
package main
import "fmt"
// Bubble sort
func BubbleSort(arr []int) []int {
length := len(arr)
for i:=0; i<length- 1; i++ {for j:=0; j<length- 1-i; j++{if arr[j]>arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j] // Big bubbles go up}}}return arr
}
// Select sort
func SelectSort(arr []int) []int {
for i := 0; i < len(arr)- 1; i++ {
for j := i + 1; j <= len(arr)- 1; j++ {
if arr[j] < arr[i] {
arr[j], arr[i] = arr[i], arr[j]
}
}
}
return arr
}
// Insert sort
func InsertSort(arr []int) []int {
for i := 1; i <= len(arr)- 1; i++ {
for j := i; j > 0; j-- {
if arr[j- 1] > arr[j] {
arr[j- 1], arr[j] = arr[j], arr[j- 1]}}}return arr
}
// Quicksort
func QuickSort(arr []int, l, r int) []int {
if l < r {
pivot := arr[r]
i := l - 1
for j := l; j < r; j++ {
if arr[j] <= pivot {
i++
arr[j], arr[i] = arr[i], arr[j]
}
}
i++
arr[r], arr[i] = arr[i], arr[r]
QuickSort(arr, l, i- 1)
QuickSort(arr, i+1, r)
}
return arr
}
// Hill sort: divide the slices into N batches, and insert sort into each batch; Then reduce the batch, and insert each batch in order; Bathc is equal to one
func ShellSort(arr []int, batchSize int) []int {
if batchSize < 1 {
return []int{}}// k: batch index of each batch element, between [0, batchSize)
for k := 0; k < batchSize; k++ {
Insert sort is used
for j := 1; batchSize*j+k < len(arr); j++ { // j: Used to obtain the number of batches in the KTH element of each batch
for n := j; n > 0; n-- {
pre := batchSize*(n- 1) + k
next := batchSize*n + k
if arr[next] < arr[pre] {
arr[next], arr[pre] = arr[pre], arr[next]
}
}
}
}
ShellSort(arr, batchSize/2)
return arr
}
// merge sort
func MergeSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
i := len(arr) / 2
left := MergeSort(arr[0:i])
right := MergeSort(arr[i:])
result := make([]int.0)
m, n := 0.0 // Left and right index positions
l, r := len(left), len(right)
for m < l && n < r {
if left[m] > right[n] {
result = append(result, right[n])
n++
continue
}
result = append(result, left[m])
m++
}
result = append(result, right[n:]...)
result = append(result, left[m:]...)
return result
}
func main(a) {
nums := []int{5.6.4.7.3.8.2.9.1.0}
temNum := BubbleSort(nums)
fmt.Println(Bubble sort)
fmt.Println(temNum)
temNum = SelectSort(nums)
fmt.Println("Selection sort")
fmt.Println(temNum)
temNum = InsertSort(nums)
fmt.Println("Insert sort")
fmt.Println(temNum)
temNum = QuickSort(nums, 1.2)
fmt.Println(Quicksort)
fmt.Println(temNum)
temNum = ShellSort(nums, 8)
fmt.Println(Hill sort)
fmt.Println(temNum)
temNum = MergeSort(nums)
fmt.Println(Merge sort)
fmt.Println(temNum)
}
Copy the codeIf there is any improper please correct.
There are other bucket sorts, heap sorts, count sorts, etc., all sorts of fancy stuff. I’m just going to save you a little bit of time and not worry about the number of ways to write the sort, and just go ahead and do the force buckle.
Refer to the content
Js implementation of ten classic sorting algorithms (GIF demo)