Bubble sort

1. In situ sorting algorithm. The space complexity is O(1).
2. Stable sorting algorithm. When there are two adjacent elements of equal size, we don’t swap
3. Time complex

Insertion sort

1. In situ sorting algorithm. The space complexity is O(1).
2. Stable sorting algorithm.
3. Time, order n at best, order n squared at worst.

Insert sort core idea

Divide the array into sorted and unsorted parts. Take the elements of the unsorted part and insert them into the sorted places.

package main

import (
	"testing"
)

// Bubble Sort
func bubbleSort(nums []int) []int {
	if len(nums) < 2 {
		return nums
	}

	for i := 0; i < len(nums); i++ {
		flag := false
		for j := 1; j < len(nums)-i; j++ {
			if nums[j- 1] > nums[j] {
				nums[j- 1], nums[j] = nums[j], nums[j- 1]
				flag = true // Indicates data exchange}}if! flag {break}}return nums
}

// Insertion Sort
func insertionSort(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}

	for i := 1; i < len(nums); i++ {
		value := nums[i]
		j := i - 1
		for ; j >= 0; j-- {
			if nums[j] > value {
				nums[j+1] = nums[j]
			} else {
				break}}Nums [j] = nums[j] = nums[j] = nums[j]
		nums[j+1] = value
	}

	return nums
}

func TestName(t *testing.T) {
	tests := []struct {
		nums     []int
		expected []int
	}{
		{[]int{5.4.3.2.1}, []int{1.2.3.4.5}},
		{[]int{4.5.6.1.3.2}, []int{1.2.3.4.5.6}},
		{[]int{1}, []int{1}},
		{[]int[] {},int{}}},for _, tt := range tests {
		actual := insertionSort(tt.nums)
		isPass := true
		if len(actual) ! =len(tt.expected) {
			t.Errorf("sorted failed. expect: %v, actual: %v", tt.expected, actual)
			continue
		}
		for i := 0; i < len(actual); i++ {
			iftt.expected[i] ! = actual[i] { isPass =false
				break}}if! isPass { t.Errorf("sorted failed. expect: %v, actual: %v", tt.expected, actual)
		}
	}
}

Copy the code