冒泡排序

冒泡排序有三种写法：

• 一边比较一边向后两两交换，将最大值 / 最小值冒泡到最后一位；
• 经过优化的写法：使用一个变量记录当前轮次的比较是否发生过交换，如果没有发生交换表示已经有序，不再继续排序；
• 进一步优化的写法：除了使用变量记录当前轮次是否发生交换外，再使用一个变量记录上次发生交换的位置，下一轮排序时到达上次交换的位置就停止比较。

代码

package main

import (
	"fmt"
)

func main() {
	values1 := []int{4, 93, 84, 85, 80, 37, 81, 93, 27, 12}
	fmt.Println(values1) // [4 93 84 85 80 37 81 93 27 12]
	MySort1(values1)
	fmt.Println(values1) // [4 12 27 37 80 81 84 85 93 93]

	values2 := []int{4, 93, 84, 85, 80, 37, 81, 93, 27, 12}
	fmt.Println(values2) // [4 93 84 85 80 37 81 93 27 12]
	MySort1(values2)
	fmt.Println(values2) // [4 12 27 37 80 81 84 85 93 93]

	values3 := []int{4, 93, 84, 85, 80, 37, 81, 93, 27, 12}
	fmt.Println(values3) // [4 93 84 85 80 37 81 93 27 12]
	MySort1(values3)
	fmt.Println(values3) // [4 12 27 37 80 81 84 85 93 93]
}

// 第一种排序
func MySort1(arr []int) {
	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr) -i - 1; j++ {
			if arr[j+1] < arr[j] {
				arr[j],arr[j+1] = arr[j+1],arr[j]
			}
		}
	}
}

// 第二种排序
func MySort2(arr []int) {
	var swapped bool = true;
	for i := 0; i < len(arr); i++ {
		if !swapped {
			break;
		}
		swapped = false;
		for j := 0; j < len(arr) -i - 1; j++ {
			if arr[j+1] < arr[j] {
				arr[j],arr[j+1] = arr[j+1],arr[j]
				swapped = true;
			}
		}
	}
}

// 第三种排序
func MySort3(arr []int) {
	var swapped bool = true;
	var indexOfLastUnsortedElement int = len(arr) - 1;
	// 上次发生交换的位置
	var swappedIndex int = -1;
	for swapped {
		swapped = false;
		for i := 0; i < indexOfLastUnsortedElement; i++  {
			if arr[i] > arr[i+1] {
				arr[i],arr[i+1] = arr[i+1],arr[i]
				// 表示发生了交换
				swapped = true;
				// 更新交换的位置
				swappedIndex = i;
			}
		}
		// 最后一个没有经过排序的元素的下标就是最后一次发生交换的位置
		indexOfLastUnsortedElement = swappedIndex;
	}
}