10 基本排序算法：直接选择排序与堆排序

直接选择排序又被称为简单选择排序，第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。这样共需进行i-1趟比较，直到排序完成所有记录为止。例如当进行第i趟选择时，从当前候选记录中选出关键字最小的k号记录，并和第i个记录进行交换。

对于拥有n个记录的文件的直接选择排序来说，其过程可以经过n-1趟直接选择排序得到一个有序的结果。 具体排序流程如下所示: 1.在初始状态，无序区为R[1..n]，有序区为空。 2.实现第1趟排序。在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 3.实现第i趟排序。

在开始第i趟排序时，当前有序区和无序区分别是R[1..i-1]和Ri..n。该趟排序会从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]进行交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样，n个记录文件的直接选择排序经过n-1趟直接选择排序后，会得到有序结果。

基本思想为每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止，简单选择排序是不稳定排序。 时间复杂度为O(n2），比冒泡好一点。但由于不稳定，实战基本不用。

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

在算法实现时，每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前最小，交换是个比较耗时的操作。 其实我们很容易发现，在还未完全确定当前最小元素之前，这些交换都是无意义的。我们可以通过设置一个变量min， 每一次比较仅存储较小元素的数组下标，当轮循环结束之后，那这个变量存储的就是当前最小元素的下标，此时再执行交换操作即可。

func SelectionSort(list []int) {
	count := len(list)
	// 从头开始循环count-1趟
	for i := 0; i < count-1; i++ {
		// 设置最值的位置，默认为当前
		min := i
		// 从i的下一位开始比较，找出此趟的最小值下标
		for j := i + 1; j < count; j++ {
			if list[j] < list[min] {
				min = j
			}
		}

		// 最小值下标已变化，交换位置
		if min != i {
			list[i], list[min] = list[min], list[i]
		}
	}
}

堆排序树形排序的一种形式，由数组存储的完全二叉树，根据其每个子树的根节点为最大值（或最小值）的特性而实现的排序算法。

堆排序是指在排序过程中，将向量中存储的数据看成一棵完全二叉树，利用完全二叉树中双亲节点和孩子节点之间的内在关系，以选择关键字最小的记录的过程。待排序记录仍采用向量数组方式存储，并非采用树的存储结构（而仅仅是采用完全二叉树的顺序结构的特征进行分析而已）。堆排序是对树形选择排序的改进。当采用堆排序时，需要一个能够记录大小的辅助空间。

堆排序的具体做法是：将待排序的记录的关键字存放在数组r[1..n]之中，将r用一棵完全二叉树的顺序来表示。每个节点表示一个记录，第一个记录r[1]作为二叉树的根，后面的各个记录r[2..n]依次逐层从左到右顺序排列，任意节点r[i]的左孩子是r[2i]，右孩子是r[2i+1]，双亲是r[r/2]。调整这棵完全二叉树，使各节点的关键字值满足下列条件：

r[i].key≥r[2i].key，并且r[i].key≥r[2i+1].key(i=1，2，…，n/2)

将满足上述条件的完全二叉树称为堆，将此堆中根节点的最大关键字称为大根堆。反之，如果此完全二叉树中任意节点的关键字大于或等于其左孩子和右孩子的关键字（当有左孩子或右孩子时），则对应的堆为小根堆。

假如存在如下两个关键字序列都满足上述条件： （10，15，56，25，30，70） （70，56，30，25，15，10）

堆排序的过程主要需要解决如下几个问题：

重建堆的过程非常简单，只需要如下两个移动步骤即可实现。 （1）移出完全二叉树根节点中的记录，该记录称为待调整记录，此时的根节点接近于空节点。 （2）从空节点的左、右孩子中选出一个关键字较小的记录，如果该记录的关键字小于待调整记录的关键字，则将该记录上移至空节点中。此时，原来那个关键字较小的子节点相当于空节点。

重复上述移动步骤，直到空节点左、右孩子的关键字均不小于待调整记录的关键字为止，此时将待调整记录放入空节点即可完成重建。通过上述调整方法，实际上是把待调整记录实现了逐步向下“筛”处理，所以上述过程一般被称为“筛选”法。

我们可以将一个任意序列看作对应的完全二叉树。因为可以将叶节点视为单元素的堆，所以可以反复利用“筛选”法，自底向上逐层把所有子树调整为堆，直到将整个完全二叉树调整为堆。我们可以确定最后一个非叶节点位于[n/2]个元素，n为二叉树节点数目。所以“筛选”必须从第[n/2]个元素开始，逐层向上倒退，直到根节点。

使用堆进行排序的具体步骤如下所示： （1）将待排序记录按照堆的定义建立一个初堆，并输出堆顶元素。 （2）调整剩余的记录序列，使用筛选法将前n-i个元素重新筛选，以便建成为一个新堆，然后再输出堆顶元素。 （3）重复执行步骤（2），实现n-1次筛选，这样新筛选成的堆会越来越小，而新堆后面的有序关键字会越来越多，最后使待排序记录序列成为一个有序的序列，这个过程被称为堆排序。

堆排序：利用数组存储的完全二叉排序树的数据结构实现排序

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

package sort

func HeapSort(list []int) {
	l := len(list)

	// 先初始化构建堆结构
	buildHeap(list,l)

	// 数组尾部开始
	for i := l; i > 1; i-- {
		// 尾部叶子节点和堆顶交换
		list[0], list[i-1] = list[i-1], list[0]
		// 除去尾部元素的其他元素重新构建最大堆
		adjustHeap(list[:i-1], 0)
	}
}

// 构建堆
func buildHeap(list []int,length int) {
	// 一定得从后往前调整
	for i := length; i >= 0; i-- {
		adjustHeap(list, i)
	}
}

// 调整堆结构
func adjustHeap(list []int, n int) {
	// 调整pos位置的结点
	l := len(list)
	for n < l {
		var child = 0

		if 2*n+2 < l {
			if list[2*n+1] > list[2*n+2] {
				child = 2*n + 1
			} else {
				child = 2*n + 2
			}
			// 选出大子节点
		} else if 2*n+1 < l {
			child = 2*n + 1
		}

		if child > 0 && list[child] > list[n] {
			list[n], list[child] = list[child], list[n]
			n = child
		} else {
			break
		}
	}
}

在直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须经过n-1次比较，然后在R[2..n]中选出关键字最小的记录，最后做n-2次比较。事实上，在后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经实现过。但是由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。

堆排序可通过树形结构保存部分比较结果，以减少比较次数。