冒泡排序 与 插入排序

排序算法在面试和工作中其实使用的地方还是蛮多的，一个人在上海空闲时间巨大。这边整理一批常用的算法解法，做做笔记记录下来~

冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。

思路

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

经过优化的冒泡算法

1. 右边已经为有序，所以每次子循环会跳过 count-i
2. 如果一次循环下来没有需要交换的元素，证明已经完成排序，所以直接break掉

func sortArray(nums []int) []int {
	count := len(nums)
	for i := 0; i < count; i++ {
		flag := false
		for j := 0 ; j < (count-i-1); j++ {
			if nums[j] > nums[j+1] {
				temp := nums[j]
				nums[j] = nums[j+1]
				nums[j+1] = temp
				flag = true
			}
		}
		if (!flag) {
			break
		}
	}
	return nums
}

是否稳定算法	平均时间复杂度	空间复杂度
是	o(n^2)	o(1)

遍历法

这个方法是我自己取的，因为我没在排序算法中找打它的描述。但是它在我看来的确是最简单的排序方法。大概思路就2个循环，第一个循环控制数组元素的移动，第二个做比对，如果条件表达式不满足就交换个位置。其实一开始我认为这种排序方法就是冒泡的，但是冒泡的定义是 比较相邻的元素。

func sortArray(nums []int) []int {
	count := len(nums)
	for i := 0; i < count; i++ {
		for j := i ; j < count; j++ {
			if nums[j] > nums[i] {
				temp := nums[j]
				nums[j] = nums[i]
				nums[i] = temp
			}
		}
	}
	return nums
}

是否稳定算法	平均时间复杂度	空间复杂度
是	o(n^2)	o(1)

插入排序

插入排序就是把一个数组分配成左右2部分，左边和右边。左边是排序好的右边是未排序的。
类似 4,5,6,3,2,1 字符串。我们分别为左右2边，4,5 | 6,3,2,1 排序时用右边的第一个数 6 和左边的数依次做对比，如果满足条件表达式就把 左边的数依次后移然后把6插入进去

技巧：其实算法本身的思路很好理解，关键点是如何用程序去实现。在这个算法中我们只要理解下面几个表达式基本上就理解了插入排序的精髓了

• for i:=1; i<count ; i++ 数组为0开头，这边 赋值为1 主要目的是忽略第一位直接从第2位元素开始比较

• heard := nums[i] 这边的heard变量是一个临时变量，因为在找到插入位后。左边的数组会依次后移，这样原先的比较位（右1 会被覆盖掉

• j := i-1 是为了取到 4,5 | 6,3,2,1 左边最后一位的小标。即 i=2，j=2-1, j = 1,下标对应的值是5,然后 j– , 5 -> 4 ->end 依次去寻找插入位。

• 为什么heard > nums[j] 一旦不满足就马上跳出循环，因为插入排序左边的数都是有序的，有一个不满足都表示缘分未到（不是当前排序位

func sortArray(nums []int) []int {
	count := len(nums)
	for i:=1; i<count ; i++ {
		heard := nums[i]
		j := i-1
		for ; j >= 0; j -- {
			if (heard > nums[j]) {
				nums[j+1] = nums[j]
			} else  {
				break
			}
		}
		nums[j+1] = heard
	}
	return nums
}

是否稳定算法	平均时间复杂度	空间复杂度
是	o(n^2)	o(1)

图片来源：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html