Sort: To arrange data in some order. For example, a list of words in alphabetical order; A group of words sorted by word length.

Sorting conditions:

  1. Sizes can be compared between elements according to certain rules;
  2. Make it clear if the order is out of order

Suppose that slice array [10, 1, 5, 3] data is required to be sorted in ascending order, using the bubble sort algorithm as the sorting algorithm:

  1. Bubble sort traverses the slice array multiple times. It compares adjacent elements and switches out of order elements.
  2. Each round of traversal puts the next maximum in the correct position. Essentially, each element “bubbles” to its place.
  3. When sorting in ascending order, you move the larger elements backward so that at the end of each iteration, the larger data is in the correct position.

In the first round of traversal, all elements need to be traversed, as shown in the following figure (the colored boxes indicate the elements being compared) :

  1. We start with element 0, which has value 10, and element 1, which has value 1. Because 10 is greater than 1, we need to switch positions;
  2. At this point, the slice array is [1, 10, 5, 3]. Now we have traversed element 1. Compare element 1, whose value is 10, with element 2, whose value is 5.
  3. At this point, the slice array is [1, 5, 10, 3], and now we have traversed element 2. Compare element 2, whose value is 10, with element 3, whose value is 3. Since 10 is greater than 3, we need to exchange positions with each other.
  4. At this point, the slice array is [1, 5, 3, 10], the first round of traversal is over, and the largest number is in the correct position.

In the second round, since the last element is already in the correct position, we only need to traverse element 0 to the second to last element, namely [1, 5, 3]. See the following figure for details (the colored box indicates the element being compared) :

  1. In this case, the slice array is [1, 5, 3, 10], and the first step is to iterate from element 0. The value of element 0 is 1, and the value of element 1 is 5.
  2. At this point, the slice array is [1, 5, 3, 10]. Now we have traversed the element 1, and compared the element 1, whose value is 5, with the element 2, whose value is 3. Since 5 is greater than 3, we need to exchange positions with each other.
  3. At this point, the slice array is [1, 3, 5, 10], the second round of traversal is over, and the second largest value is in the correct position.

The third round takes time, because after the sorting of the first two rounds, now we only need to traverse [1, 3], see the following figure for details (the colored boxes represent the elements being compared) :

  1. In this case, the slice array is [1, 3, 5, 10], and the first step is to iterate from element 0. The value of element 0 is 1 and the value of element 1 is 3 for comparison. Because 1 is less than 3, there is no need to switch positions.
  2. At this point, the slice array is [1, 3, 5, 10], and the third round of traversal is over.

The whole slice values have been sorted in ascending order as [1, 3, 5, 10].

Time complexity: O(n²) From the sorting process above, it takes n-1 times to bubble sort the slices of n elements, and then the number of comparisons in each traverse is n-1, n-2, N-3… 2, 1, so it’s 1+2+3+… Plus n minus 2 plus n minus 1, which is ½n squared minus ½n, which is O(n squared).

The following is the bubble sort code implemented with Golang:

package main

import (
	"fmt"
)

func bubbleSort(numList []int) {
	for needToSortNums := len(numList); needToSortNums > 0; needToSortNums-- {
		// Mark whether an element exchange has occurred within the loop
		swap := false
		for idx := 0; idx < needToSortNums- 1; idx++ {
			if numList[idx] > numList[idx+1] {
				temp := numList[idx]
				numList[idx] = numList[idx+1]
				numList[idx+1] = temp
				swap = true}}// If no element exchange occurs, the order is correct and the function exits
		if! (swap) {return}}}func main(a) {
	//numList := []int{10, 1, 5, 3}
	numList := []int{10.1.5.3.2.7}
	//numList := []int{10, 1, 5, 3}
	fmt.Println(numList)
	// [10 1 5 3]
	bubbleSort(numList)
	fmt.Println(numList)
	// [1 3 5 10]
}
Copy the code

Selection sort is a sort algorithm optimized on the basis of bubble sort.