08 基本排序算法：冒泡排序与快速排序

冒泡排序是一种简单的交换类排序方法，能够将相邻的数据元素进行交换，从而逐步将待排序序列变成有序序列。冒泡排序的基本思想是：从头扫描待排序记录序列，在扫描的过程中顺次比较相邻两个元素的大小。 下面以升序为例介绍排序过程:

1.在第一趟排序中，对n个记录进行如下操作。 ①对相邻的两个记录的关键字进行比较，逆序时就交换位置。 ②在扫描的过程中，不断向后移动相邻两个记录中关键字较大的记录。
③将待排序记录序列中的最大关键字记录交换到待排序记录序列的末尾，这也是最大关键字记录应在的位置。
2.进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是使次大的记录被放在第n-1个记录的位置上。 3.继续进行排序工作，在后面几趟的升序处理也反复遵循了上述过程，直到排好顺序为止。如果在某一趟冒泡过程中没有发现一个逆序，就可以马上结束冒泡排序。整个冒泡过程最多可以进行n-1趟。

冒泡排序法运行效率较低，但概念上最简单,由于太慢，实战基本不用

• 平均时间复杂度：O(n²)
• 最坏时间复杂度：O(n²)
• 最好时间复杂度：O(n)
• 空间复杂度：O(1)
• 稳定性：稳定

1.对未排序的各元素从头到尾依次比较相邻的两个元素大小关系 2.如果左边的元素大，则两元素交换 3.向右移动一个位置，比较下面的两个元素 4.当走到最右端时，最大的元素一定被放在最右边 5.按照这个思路从左端开始依次类推

冒泡排序的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换， 这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。时间复杂度为O(n2）

// 冒泡排序的第一种实现：直接使用内层循环参数，外层循环参数只规定轮数
func BubbleSort(list []int, asc bool) {
	count := len(list)
	for i := 0; i < count-1; i++ { // 冒泡的轮次：选定一个元素，轮数为n-2次
		flag := true
		for j := 0; j < count-1-i; j++ { // 每轮冒泡的过程：比较选定元素和其他元素，每轮冒泡比较的元素逐渐减少
			if asc {
				// 从左到右升序，保持最大的在最右边
				if list[j] > list[j+1] {
					list[j], list[j+1] = list[j+1], list[j]
					flag = false
				}
			} else {
				// 从左到右降序，保持最大的在最左边
				if list[j] < list[j+1] {
					list[j], list[j+1] = list[j+1], list[j]
					flag = false
				}
			}
		}
		if flag {
			break
		}
	}
}

在前面介绍的冒泡排序中，在扫描过程中只比较相邻的两个元素，所以在互换两个相邻元素时只能消除一个逆序。其实也可以通过两个不相邻的元素进行交换，这样做的好处是消除待排序记录中的多个逆序，这样会加快排序的速度。由此可见，快速排序方法就是通过一次交换而消除多个逆序的过程。

快速排序的基本思想如下所示： 1.从待排序记录序列中选取一个记录，通常选取第一个记录，将其关键字设为K1 。 2.将关键字小于K1 的记录移到前面，将关键字大于K1 的记录移到后面，结果会将待排序记录序列分成两个子表。 3.将关键字为K1 的记录插到其分界线的位置。

我们通常将上述排序过程称作一趟快速排序，通过一次划分之后，会形成以关键字K1 这个记录作为分界线，并且将待排序序列分成了两个子表，前面子表中所有记录的关键字都不能大于K1 ，后面子表中所有记录的关键字都不能小于K1 。我们可以对分割后的子表继续按上述原则进行分割，直到所有子表的表长不超过1为止，此时待排序记录序列就变成了一个有序表。

快速排序算法基于分治策略，可以把待排序数据序列分为两个子序列，具体步骤如下所示： 1.从数列中挑出一个元素，将该元素作为“基准”。 2.扫描一遍数列，将所有比“基准”小的元素排在基准前面，所有比“基准”大的元素排在基准后面。 3.使用递归将各子序列划分为更小的序列，直到把小于基准值元素的子数列和大于基准值元素的子数列排序。

快速排序：是一个就地排序，分而治之，大规模递归的算法。它是冒泡排序的加强版，但从本质上来说，它是归并排序的就地版本。

• 平均时间复杂度：O(nlogn)
• 最坏时间复杂度：O(n²)
• 最好时间复杂度：O(n)
• 空间复杂度：O(1)
• 稳定性：不稳定

快速排序可以由下面四步组成： （1）如果不多于1个数据，直接返回。 （2）一般选择序列最左边的值作为支点数据。 （3）将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。 （4）对两边利用递归排序数列。 快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。 快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。时间复杂度是 O(nlogn)，空间复杂度最差是O(n), 平均是O(logn)。

func QuickSort(list []int) {
	count := len(list)
	quickSort(list, 0, count-1)
}

// 分而治之思想，递归函数
func quickSort(list []int, left, right int) {
	// 小于两个的不用排序
	count := len(list)
	if count < 2 {
		return
	}

	// 符合排序条件
	if left < right {
		// 找基准并排序
		benchmark := getAdjust(list, left, right)
		// 左边递归排序
		quickSort(list, left, benchmark-1)
		// 右边递归排序
		quickSort(list, benchmark+1, right)
	}

}

// 找基准
func getAdjust(list []int, left, right int) int {

	// 最简单找最左为基准数
	x := list[left]
	i, j := left, right

	// 从右向左找小于x的数，发现此数则退出此循环
	for i < j && list[j] >= x {
		j--
	}
	// 从左向右找大于x的数，发现此数则退出此循环
	for i < j && list[i] <= x {
		i++
	}
	// 交换
	if i < j {
		list[i], list[j] = list[j], list[i]
	}

	// 基准数归位，现在左边的序列小于基准数，右边的序列大于基准数
	list[left], list[i] = list[i], list[left]
	return i

}