排序 Go入门

目录

写在前面

冒泡排序

冒泡排序升级版

选择排序

插入排序

希尔排序

快速排序

---

写在前面

权当Go练习打的娱乐，Go有很多编程语言的影子，相对于C C++ Python Java而言，Go有C和C++的指针，有面向对象，输入像C，输出和Java、python差不多。

但Go的循环只有for，go的for有几种形式，分别和传统的for、while和do while对应。

和C、C++一样，传参都是创建副本，可能是因为有指针，像python和Java没有指针，传的都是自己。

冒泡排序

两个循环嵌套，外循环n-1次，内循环n-1次，每次找到大小顺序不对的就交换两个数的位置。

package main
 
import "fmt"
 
func bubble(number []int, n int) {
	for i := 0; i < n-1; i++ {
		for j := 0; j < n-1; j++ {
			if number[j] > number[j+1] {
				number[j], number[j+1] = number[j+1], number[j]
			}
		}
	}
}
func main() {
	number := []int{1, 3, 6, 8, 2, 5, 4, 9, 0, 7}
	bubble(number, 10)
	for i := 0; i < 10; i++ {
		fmt.Print(number[i], " ")
	}
}

冒泡排序升级版

也许并不需要循环这么多次就已经排序好了，所以我们在发现有一轮循环中没有发生交换就跳出循环。

func bubble(number []int, n int) {
	for i := 0; i < n-1; i++ {
		tag := 0
		for j := 0; j < n-1; j++ {
			if number[j] > number[j+1] {
				number[j], number[j+1] = number[j+1], number[j]
				tag = 1
			}
		}
		if tag == 0 {
			break
		}
	}
}

选择排序

对于一串待排序的数字，假如是要升序排序，那么先在这串数字中找到最小的那一个放在第一位，然后再在剩下的数字中找到最小的放在第二位，以此类推，完成排序。

那么怎么知道哪个是最小的呢？

一般假设第一个是最小的，然后拿这个去和后面的数字进行比较，发现比它更小的，就把它们进行交换。

func select(number []int, n int) {
	for i := 0; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			if number[i] > number[j] {
				number[j], number[i] = number[i], number[j]
			}
		}
	}
}

插入排序

基本思路是，一般先孤立这堆数字的第一个数，那么它自己一个就是有序了，再拿后面的数和它比较，找到大小位置合适的插进去，完了之后这一小堆还是有序的，再拿后面的来和前面的比较，找到合适的位置插进去，直到全部插完。

func insert(number []int, n int) {
	for i := 0; i < n; i++ {
		for j := i; j > 0; j-- {
			if number[j-1] > number[j] {
				number[j], number[j-1] = number[j-1], number[j]
			}
		}
	}
}

希尔排序

从上面插入排序的思想可以知道，如果这堆数原本就比较有序了，那么直接插入排序是非常高效的，因为交换次数会少很多。但有一种情况是，假设是从小到大排序，前面已经排好了一万个有序数，到这10001个数的时候，恰好它是最小的那一个，那么就要和前面的数全部交换一次，，这就出现了交换距离过长的问题，这是我们不希望看到的。插入排序的这两个特点，我们引入了它的升级版——希尔排序。

希尔排序又被称作缩小增量排序。

为了解决直接插入排序交换距离过长问题，我们设想如果能让这一堆待排序的数中比较小的数在一边，比较大的数在另一边，那么发生交换的时候就不用跨过千山万水了。

也就是说，我们要先对这一堆数进行预排序，具体操作是，先选定一个数interval（一般是数字的总数的一半）作为第一增量，然后把间隔为interval的数作为一个小组，对这个小组进行直接插入排序，然后缩小interval（一般是让interval减半）作为第二增量，继续分小组进行直接插入排序，以此类推，操作下去，到interval等于1的时候，小组间间隔为1，也就是对全部元素进行直接插入排序，但整个时候，这一堆数已经相对有序了，直接插入排序这个时候就十分高效了。

func insert(number []int, n int) {
	interval := n / 2
	for interval > 0 {
		for i := 0; i < n; i += interval {
			for j := i; j > 0; j -= interval {
				if number[j-interval] > number[j] {
					number[j], number[j-interval] = number[j-interval], number[j]
				}
			}
		}
		interval /= 2
	}
}

快速排序

快速排序的基本思想是：首先找一个基准数，一般选第一个数或者最后一个数作为基准数，然后先把这一串数以基准数为界限分成两部分，一部分比基准数小，另一部分比基准数大。然后用分治法的思想，进行递归调用，对每一部分继续操作下去，直到每一部分只剩下一个数。

package main
 
import "fmt"
 
func fastsort(number []int, first, last int) { //从小到大排序
	if first >= last { //大于或者相同都说明这一小部分已经排序完毕了
		return
	}
	standard, i, j := number[first], first, last //选取第一个作为基准数
	for i != j {//从两边出发，比基准数小的扔在一边，大的扔在另一边
		for j > i && number[j] >= standard { //从右边出发寻找比基准数小的
			j = j - 1
		}
		for j > i && number[i] <= standard { //从左边出发寻找比基准数大的
			i = i + 1
		}
		if j > i { //找到了就交换
			number[i], number[j] = number[j], number[i]
		}
	}
	number[first] = number[j]
	number[j] = standard //把基准数放在中间，这里的中间指的是不在两边
	fastsort(number, first, i-1) //继续排基准数左边部分的
	fastsort(number, i+1, last)  //继续排基准数右边部分的
}
func main() {
	number := []int{1, 3, 6, 8, 2, 5, 4, 9, 0, 7}
	fastsort(number, 0, 9)
	for i := 0; i < 10; i++ {
		fmt.Print(number[i], " ")
	}
}