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 code

Selection 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 code

Insertion 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 code

Quick 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 code

Hill 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 code

Merge 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 code

The 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 code

If 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)