【转载请标明出处】： https://blog.csdn.net/qq_25870633/article/details/82664709

本文章参考：

https://blog.csdn.net/benben_2015/article/details/79231929

https://blog.csdn.net/wangshubo1989/article/details/75135119

https://blog.csdn.net/tuobicui6522/article/details/80392566

首先我为什么要写这篇文章呢？因为我们做区块链的人事需要懂好多东西的，首先各类主流的排序算法也是必须的，虽然看起来和区块链没有什么鸟关系，但是为了提升自己，也算是做点总结了！所以我这里来用golang总结下几种主流的排序算法【当然也是参考了网上各位大神的，然后总结称自己的，因为made in china嘛】，好了不多逼逼了，上代码：

【1】冒泡排序：

【应用】：冒泡排序直观，但比较慢，模比较小的时候应用冒泡排序

原理：两个数比较大小，较大的数后沉，较小的数前冒起来

如图：

                         

如代码：这里我用三种写法来实现冒泡，并且说明哪种写法比较好：

/**
方法一
*/
func bubbleSort(arr []int) {
	var (
		n       = len(arr)
		swapped = true
	)
	for swapped {
		swapped = false
		for i := 0; i < n - 1; i++ {
			/**
			因为外层是个死循环，内层为值遍历到数组的倒数第二个，然后遍历到的每一个都是用当前的和后面一个最对比
			如果发现只要有需要把大的往后推的就把标识位改为true，但是如果在遍历完本次之后发现就没有 i > i + 1 的，那么就属于数组全部都排序好的了
			如果该次数组的遍历有大的就把他逐个往后推到末尾，然后标识位为 true 且 在进入下一轮 遍历之前把下一轮遍历的数组元素遍历个数 减1，【因为最后一个已经是拍好的最大的了】
			这个做法比 方法2的好，因为增加了标识位的判断避免了多余的 for 的遍历次数
			而方法2是预定好一定会做 n - 1次对数组的for，导致真正整体循环的次数是 n的阶乘，而本方法根据实际情况(由标识位来控制)确定是否需要是n的完整阶乘还是一半额阶乘
			  */
			if arr[i] > arr[i+1] {
				arr[i+1], arr[i] = arr[i], arr[i+1]
				swapped = true
			}
		}
		n -= 1
	}
}


/**
方法二
*/
func bubbleSort2(arr []int) {
	n := len(arr)
	for j := 0; j < n - 1; j ++ { //这个代表 需要做多少次对 数组的for
		for i := 0; i < n - j - 1; i++ { //每一次对数组的for
			if arr[i] > arr[i+1] {  // 对数组的各个元素逐个对比，把大的值一直推到末尾
				/**
				对于 for 中的 n - j - 1 解释
				当第一层for 执行第一次时，里面的for就是 n - 0 - 1 把当前数组的所有元素都逐一对比，把最大的推到末尾
				当第一层for执行第二次时，里面的for是 n - 1 - 1 就是把数组减掉最后一个(因为最后一个是最大值)去做逐一对比
				当第一层for执行第三次时，里面的for是 n - 2 - 1 就是把数组减掉最后两个(因为后面两个是数组汇总依次最大的两个值)去做逐一对比
				依次类推当for执行到 第 n - 1次时，里面的for是 n - (n - 2) - 1 == 1 就是剩下的最后一个最小的被排到第一位
				所以是： (n - 0 - 1) * (n - 1 - 1) * (n - 2 - 1) * ... * (n - (n - 2) - 1) == n的阶乘
				 */
				arr[i+1], arr[i] = arr[i], arr[i+1]
			}
		}
	}
}

/**
方法三
*/
func bubblesort3(items []int) {
        /**
	    这一种是做浪费for次数的冒泡，完全就是 n的n次方的运算
	 */
	n := len(items)
	for i := 0; i < n - 1; i++ {
		for j := 0; j < n - 1; j++ {
			if items[j+1] < items[j] {
				items[j], items[j+1] = items[j+1], items[j]
			}
		}
	}
}

【建议】：第一种写法更有效率一点

由此可知，第一种方式是最好的写法。

【2】选择排序：

【应用】：简单选择排序是不稳定排序，比上面的冒泡好一点，当数据量较小的时候适用

原理：在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换， 第二次遍历n-2个数，找到最小的数值与第二个元素交换。。。 第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成

如图：

                            

如代码：这里我用两种方式写出来：

func selectSort(arr []int) {
	var minIndex int
	for i := 0; i < len(arr) - 1; i++ { // 表示对数字做for遍历的次数
		minIndex = i // 初始化下标为0
		/**
		在第一次对数组做for 的遍历中，从第二个元素开始逐一最小的那个对比，如果自己是最小的则把该元素的下标记住然后继续往后对比
		第二次对数组的for是从第三个开始，依次类推
		所以他也是 n的阶乘
		 */
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		if minIndex != i { //这里把最小的那个放到第i位，即第一次对数组的for是下标0，第二次的是下标1依次类推
			arr[i], arr[minIndex] = arr[minIndex], arr[i]
		}
	}
}

func selectSort2(arr []int) {
	length := len(arr)
	for i := 0; i < length; i++ {
		maxIndex := 0
		/**
		第二种做法是，每一次对数组的for都需要把最大的书的下标记录下来，然后放置本次for的数组的末尾(本次for的数组是除去上次for之后的某尾数的元素)
		也是n的阶乘，比第一种写法少了一个if判断，效率提升一些
		 */
		for j := 1; j < length - i; j++ {
			if arr[j] > arr[maxIndex] {
				maxIndex = j
			}
		}
		arr[length - i - 1], arr[maxIndex] = arr[maxIndex], arr[length - i - 1]
	}
}

【建议】：第二种写法比第一种少了一个if，应该效率好一点

【3】快速排序：(效率最高)

【应用】：快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。

原理：如果数组中只有一个元素，直接返回 如果有多个元素，先指定一个数轴(也就是一个基准数，开始第一遍的时候可以是最左边的数) 然后根据数轴把数分成 左右两部分，然后继续递归

如图：

如代码：也是用两种方式，一种有中间变量做互换，一种直接互换(建议写这种)

/**
第一种：有中间量
*/
func quickSort1(nums []int) {
	reSort(nums, 0, len(nums)-1)
}
func reSort(arr []int, left, right int) {
	if left < right {
		i := arrAdjust(arr, left, right)
		reSort(arr, left, i-1)
		reSort(arr, i+1, right)
	}
}

//返回调整后基准数的位置
func arrAdjust(arr []int, left, right int) int {
	x := arr[left] //基准
	for left < right {
		//从右向左找出小于 基准数的下标
		for left < right &&  x <= arr[right] {
			right-- //当出现右边有数小于左边的数时，for停止进入下面if
		}
		if left < right { // 如果 右边的下标已经 <= 左边的下标那么说明，上面的for已经找过头了，右边往左缩进缩过头了
			// 用上面for找出来的下标的那个元素的值替换掉基准数所在的位置，且开始把左游标由基准数位置往右移 一位开始找左边的数来和基准数对比
			arr[left] = arr[right]
			left++
		}

		//从左向右找大于或等于x的数来填从 之前右侧找出来的那个值的位置，且把右游标往左移一位
		for left < right &&  x > arr[left]{
			left++
		}
		if left < right {
			arr[right] = arr[left]
			right--
		}
		/**
		然后重复 从新的右游标和左右表做上面的动作，直到本次左的所有数都小于基准数，右侧的数都大于基准数
		 */
	}
	arr[left] = x //退出前把基准放到最后一次左往右移时找出的数的那个位置，可以认为是 一个逻辑中间的位置
	/**
	到这里的操作步骤就是：先从右往左注意和基准数对比，把小于基准数的都移到左侧；
	再从左到右把大于等于基准数的都移到右边，不管是从左到右还是从右到左，的每一次for都是逐一往中心靠拢的游标
	最后把，基准数放置最后一次替换的那个位置，这样纸最终就达到了 以该基准数的新位置为新的左右分割点，形成左侧都是小于基准数，右侧都是大于基准数
	最终把新的基准位置返回，并进入下次左右两个 数组的迭代上述重复动作，知道最终排完
	 */

	return left
}
//////////////////////////////////////////////////////////////////////////////////////////

/**
第二种：直接互换
*/

func quickSort2(arr []int) {
	recursionSort(arr, 0, len(arr) - 1)
}

func recursionSort(arr []int, left int, right int) {
	if left < right { // 加一个强制限定 左边小于右边的下标，否则结束快排,这个也是结束递归的方式
		pivot := partition(arr, left, right)
		recursionSort(arr, left, pivot-1)
		recursionSort(arr, pivot+1, right)
	}
}
// 精华就在这个里面
func partition(arr []int, left int, right int) int {
	for left < right { // 为什么要这么做 因为看里面的逻辑我们知道，left和right是逐渐往中间(不是二分中心点)靠拢的
		for left < right && arr[left] <= arr[right] { //先逐个缩进遍历右侧的元素，由右到左，到发现有小于基准数的时候则记住当前下标 往下走
			right--
		}
		if left < right {
			// 互换基准数和 对比数的位置，注意现在 基准数是在 之前对比数的位置的，然后开始从之前基准数所在的下一个位置开始启动左边对比
			arr[left], arr[right] = arr[right], arr[left]
			left++
		}

		for left < right && arr[left] <= arr[right] { // 逐个缩进遍历新的左侧(从之前右侧对比的基准的下一个位置开始)，由左到右和基准数对比(注意次时基准数的下标是和之前右侧查找的数下标互换了)，直到发现有大于等于基准数的时候记住下标 往下走
			left++
		}
		if left < right {
			// 把基准数和对比数互换位置
			arr[left], arr[right] = arr[right], arr[left]
			right--
		}
	}
	/**
	直到最后 基准数被调节到某个位置，且该位置左边的元素都小于基准数，右边的元素都大于等于基准数，且返回该基准数最终的位置，把数组分为左右两部分各自进入新的递归
	 */
	return left
}

【建议】：第一种是做了个中间变量来实现数据互换的，这个是直接互换，写法简洁一点

【4】插入排序：

【应用】：插入排序在数组元素随机排列的情况下，插入排序还是要优于选择和冒泡两种排序的，数据量小时使用。并且大部分已经被排序

原理：在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面已排序的有序数列中（从后向前扫描，找到相应位置并插入），使得这n个数也是排好顺序的。如此反复循环，直到全部排号顺序

如图：

如代码：

func insertSort1(arr []int) {
	for i := 0; i < len(arr) - 1; i++ {
		/**
		第一层for指的是对数组的位置做遍历，第二层for是对第一层for遍历到的位置的后一个元素往前做遍历，并逐一和前面的元素做对比，把小的元素往前推,这样来实现插入到某一个位置
		 */
		for j := i + 1; j > 0; j-- {
			if arr[j] < arr[j-1] {
				arr[j], arr[j-1] = arr[j-1], arr[j]
			}else {
				break
			}
		}
	}
}


func insertSort2(arr []int) {  // 总之，不建议这种比较绕的写法
	for i := 1; i < len(arr); i++ {
		if arr[i] < arr[i-1] {
			j := i - 1
			temp := arr[i]
			for j >= 0 && arr[j] > temp {
				arr[j+1] = arr[j]
				j--
			}
			arr[j+1] = temp
		}
	}
}


func insertSort3(arr []int) {
	var n = len(arr)
	for i := 1; i < n; i++ { // 从第二个开始遍历
		j := i
		for j > 0 { // 依次往前对比
			if arr[j-1] > arr[j] {
				arr[j-1], arr[j] = arr[j], arr[j-1]
			}
			j = j - 1
		}
	}
}

 

【建议】：不要用第二种写法

【5】希尔排序 ：

【应用】：希尔排序适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的

递减增量排序算法，是插入排序的一种高速而稳定的改进版本

原理：在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序

如图：

                    

上面第二个图有点问题。正确的图应该是我代码中方法2注释中所画的：

func shellSort(arr []int) {  // 这个没有第二个好理解，但是和第二个的执行是一样的
	increment := len(arr) // 设置初初始步进为 数组的长度
	for {
		increment = increment / 2 // 第一次排序用 1/2 数组长度
		for i := 0; i < increment; i++ { // 每次外层遍历只 遍历至和步进一样的次数
			for j := i + increment; j < len(arr); j = j + increment { // 以 步进来取需要做 插入排序的数组段
				for k := j; k > i; k = k - increment { // 由起点往前做插入排序
					if arr[k] < arr[k-increment] {
						arr[k], arr[k-increment] = arr[k-increment], arr[k]
					} else {
						break
					}
				}
			}
		}
		if increment == 1 { // 当最终步进为 1 时，停止排序
			break
		}
	}
}
// 以下只拿第一次的来说，后面的依次类推
/**
	以下为下面代码中第一次排序的逻辑
	6 5 5 9 3 4 8 7 11 8 10 2
	|_________| 4 和 6 做排序 == 4 5 9 3 6 8 7 11 10 2
	|_________|_____________|  2 和 6 做排序，再和4做排序 == 2 5 5 9 3 4 8 7 11 8 10 6
	第二次是 1/4 数组长度
	2 5 5 9 3 4 8 7 11 8 10 6
	|___|  5 和 2 排序 == 2 5 5 9 3 4 8 7 11 8 10 6
	|___|_____| 4 和 5 做排序 再和 2 做排序 == 2 5 4 9 3 5 8 7 11 8 10 6
	|___|_____|______| 11 和 5 做排序再和4做排序再和2做排序 == 2 5 4 9 3 5 8 7 11 8 10 6
	|___|_____|______|______| 6和11做排序再和5做排序再和4做排序再和2做排序 == 2 5 4 9 3 5 8 7 6 8 10 11
	然后再次缩短步进，重复上面的操作，依次类推直到步进 == 1

 */
func shellSort2(arr []int) {

	// 确定步长，第一次先为 1/2 的数组长度，往后每一次遍历都逐渐减半
	for gap := len(arr) / 2; gap >= 1; gap /= 2 {
		// 对每一个步长对应的数组进行插入排序，从从第一个步进处开始
		for i := gap; i < len(arr); i += gap {
			flag := i - gap //从0个开始
			temp := arr[i] // 步进处的值
			for flag >= 0 && arr[flag] > temp { // 如果第零个的值大于第一个步进处的值，则把第零个值置赋值给第一个步进处
				arr[flag+gap] = arr[flag]
				flag -= gap	// 从第零处往前减一个步进
			}
			arr[flag+gap] = temp // 目前这是第零个，把之前缓存的步进处的值赋给第零个，完成了置换
		}
	}
}

func shellSort3(items []int) {
	var (
		n    = len(items)
		gaps = []int{1}
		k    = 1
	)

	for {
		gap := pow(2, k) + 1
		if gap > n-1 {
			break
		}
		gaps = append([]int{gap}, gaps...) // 原先步进小的都往尾部增加，大的步进都在 切片前面
		k++
	}

	for _, gap := range gaps { // 这块逻辑和方法2 一致
		for i := gap; i < n; i += gap {
			j := i
			for j > 0 {
				if items[j-gap] > items[j] {
					items[j-gap], items[j] = items[j], items[j-gap]
				}
				j = j - gap
			}
		}
	}
}
// 求间隙
func pow(a, b int) int {
	p := 1
	for b > 0 {
		if b&1 != 0 {
			p *= a
		}
		b >>= 1
		a *= a
	}
	return p
}

【建议】：第二种写法我个人觉得不错，第三种逼格最高

【6】归并排序：

【应用】：  如果需要稳定，空间不是很重要，请选择归并

原理：先递归分解数组，再合并数组。先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，【谁小就先取谁】，取了后相应的指针就往后移一位。 然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。再考虑递归分解，基本思路是将数组分解成left和right， 如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分， 直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可

如图：

                                                    

如代码：

func mergeSort(arr []int) {
	length := len(arr)
	temp := make([]int, length) // 提前开辟一块内存空间存放临时数据
	mSort(arr, 0, length-1, temp)
}

func mSort(arr []int, left, right int, temp []int) {
	if left < right {
		mid := (left + right) / 2 // 先去中位数
		mSort(arr, left, mid, temp)
		mSort(arr, mid+1, right, temp)
		//两边的子序列都是有序的，
		//如果左边的最大的元素比右边最小的元素大才需要合并
		if arr[mid] > arr[mid+1] {
			merge(arr, left, mid, right, temp)
		}
	}
}

func merge(arr []int, left, mid, right int, temp []int) {
	i := left
	j := mid + 1
	t := 0 //临时slice的指针
	for i <= mid && j <= right { // 开始同时遍历左边和右边两部分数组 【该循环会一直执行到左右其中一个数组为空】
		if arr[i] <= arr[j] { // 左边数组的第N个和右边数组的第M个作比较， 当右边的 大于左边的时，开始把左边的放入 临时数组的第K位中
			temp[t] = arr[i]
			i++ // 取完后，相应的指针向后移一位
		} else {
			temp[t] = arr[j] // 同上
			j++
		}
		t++
	}
	// 等上述对比完之后， 临时数组中刚好存完且空出最后一个空位 (因为上面做了 t++)
	//将左序列剩余元素填充进temp中
	for i <= mid {
		temp[t] = arr[i]
		t++
		i++
	}
	//将右序列剩余元素填充进temp中
	for j <= right {
		temp[t] = arr[j]
		t++
		j++
	}
	t = 0
	//将temp中的元素全部拷贝到原数组中，【因为到这里位置，可能做也可能右的某个数组剩下的那部分根本还没排序】
	// 我们先从左到右把临时数组中的元素逐一放回原数组中，然后再次做递归
	for left <= right {
		arr[left] = temp[t]
		left++
		t++
	}
}

func mergeSort2(arr []int){
	// 把排好序且返回的临时数组,从新逐个加入原数组中
	for i, v := range mergeSortTemp(arr) {
		arr[i] = v
	}
}
// 这一种比第一种耗的内存多一点，临时数组起的太多了
func mergeSortTemp(arr []int) []int {
	var n = len(arr)

	if n == 1 {
		return arr
	}

	middle := int(n / 2)
	var (
		leftArr  = make([]int, middle)
		rightArr = make([]int, n-middle)
	)
	for i := 0; i < n; i++ {
		if i < middle { // 把原来数组中左右两部分分别拆分到 两个临时数组中
			leftArr[i] = arr[i]
		} else {
			rightArr[i-middle] = arr[i]
		}
	}

	return merge2(mergeSortTemp(leftArr), mergeSortTemp(rightArr)) // 因为一直这样递归的拆分，所以，最终导致最底层的临时数组只会有一个元素
}
// 合并左右两个临时数组【这个才是排序的精髓】
func merge2(leftArr, rightArr []int) (result []int) {
	result = make([]int, len(leftArr) + len(rightArr)) // 临时的回收数组

	i := 0 // result 的下标
	for len(leftArr) > 0 && len(rightArr) > 0 { // 一直对比到左右两个数组有一个比完为止
		if leftArr[0] < rightArr[0] { // 当左边第一个比右边第一个大时，把左边的加入回收数组中
			result[i] = leftArr[0]
			leftArr = leftArr[1:] // 且左数组截除第一位
		} else {
			result[i] = rightArr[0] // 右边的同上
			rightArr = rightArr[1:]
		}
		i++
	}

	for j := 0; j < len(leftArr); j++ { // 如果左边有剩余，则把剩下的追加到 回数数组末尾，以便开启新的一轮递归
		result[i] = leftArr[j]
		i++
	}
	for j := 0; j < len(rightArr); j++ { // 同理
		result[i] = rightArr[j]
		i++
	}
	return
}

/**
建议 这种写法
 */
func mergeSort3 (arr []int) {
	// 把排好序且返回的临时数组,从新逐个加入原数组中
	for i, v := range mergeSort3Temp(arr) {
		arr[i] = v
	}
}
func mergeSort3Temp(arr []int) []int{
	if len(arr) <= 1 {
		return arr
	}
	var middle int = len(arr)/2
	left := mergeSort3Temp(arr[:middle])
	right := mergeSort3Temp(arr[middle:])
	return merge3(left, right)
}

func merge3(left, right []int) []int {
	leftLen, rightLen := len(left), len(right)
	var result []int = make([]int, leftLen + rightLen) // 起一个临时的回收数组
	k := 0//数组切片result的下标
	i, j := 0, 0//a、b起始下标均未0
	for i < leftLen && j < rightLen  {
		if left[i] < right[j] {
			result[k] = left[i]
			i++
		} else {
			result[k] = right[j]
			j++
		}
		k++
	}
	// 左和右哪个有剩余，把剩余的追加到 回收数组的末尾以便之后的递归
	for i != leftLen {
		result[k] = left[i]
		k++
		i++
	}
	for j != rightLen {
		result[k] = right[j]
		k++
		j++
	}
	return result
}

【建议】：用第三种写法比较简洁~

【7】堆排序：

【应用】：  堆排序适合于数据量非常大的场合（百万数据）

原理：先把待排序的序列构造成最大化堆，然后把第一位和末尾一位互换，再把不包含末尾一位的剩余元素再次构造新的最大花堆， 再把新堆的首位和新堆的末尾位(也就是原数组的倒数第二位)互换。如此重复，知道最后的堆只有两个数然后 R0 与 R1互换。

堆排序是一种选择排序 

n个元素的序列{k1，k2，…,kn}当且仅当满足下列关系之一时，称之为堆。　　

情形1：ki <= k2i 且ki <= k2i+1 （最小化堆或小顶堆）　　

情形2：ki >= k2i 且ki >= k2i+1 （最大化堆或大顶堆）　　其中i=1,2,…,n/2向下取整;

若将和此序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。
例如，下列两个序列为堆，对应的完全二叉树：

若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。堆排序，只需要一个记录元素大小的辅助空间（供交换用），每个待排序的记录仅占有一个存储空间。

一般用数组来表示堆，若根结点存在序号0处， i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2i+1和2i+2。（注：如果根结点是从1开始，则左右孩子结点分别是2i和2i+1。当然一般我们构造堆的时候选择的是 n/2开始的）如第0个结点左右子结点下标分别为1和2。如最大化堆如下：左图为其存储结构，右图为其逻辑结构：

操作过程如下：

     1)  初始化堆：将序列R[1... n] 构造为堆；

     2)  将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。

因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。

堆排序适合于数据量非常大的场合（百万数据），时间复杂度是 O(nlogn)

 

【1】构造最大堆（最小堆类似）：若数组下标范围为  0~n ，考虑到单独一个元素是大根堆，则从下标【n/2】开始的元素均为大根堆。于是只要从【n/2-1】开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。

【2】 堆排序：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0...n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0...n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。

【3】最大堆调整：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点 。

如代码：

func heapSort(a []int) {
	length := len(a)
	if length == 0 {
		return
	}
	//构造初始堆
	for i := length/2 - 1; i >= 0; i-- {
		heapAdjust(a, i, length-1)
	}
	// 取出最大的数，然后对剩下的再次调整成新的堆
	for j := length - 1; j >= 0; j-- {
		a[0], a[j] = a[j], a[0]
		heapAdjust(a, 0, j-1)
	}
}

//调整堆 【是用了中间变量】
func heapAdjust(a []int, start, end int) {
	temp := a[start]

	for k := 2*start + 1; k <= end; k = 2*k + 1 { //从i结点的左子结点开始，也就是2i+1处开始
		//选择出左右孩子较大的下标
		if k < end && a[k] < a[k+1] {
			k++
		}
		//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
		if a[k] > temp {
			a[start] = a[k]
			start = k
		} else {
			break
		}
	}
	a[start] = temp //插入正确的位置
}

func heapSort2(arr []int) {
	N := len(arr)
	var first int = N/2    //最后一个非叶子节点
	// 初始化 最大化堆
	for start := first; start > -1; start-- {    //构造大根堆
		max_heapify(arr, start, N-1)
	}
	// 堆排序，并调整新堆
	for end := N-1; end > 0; end-- {    //堆排，将大根堆转换成有序数组
		arr[end],arr[0] = arr[0],arr[end]
		max_heapify(arr, 0, end-1)
	}
}
func max_heapify(arr []int, start int, end int) {
	root := start
	for true {
		child := root*2 + 1    //调整节点的子节点
		if child > end {
			break
		}
		if child + 1 <= end && arr[child] < arr[child+1] {
			child = child + 1    //取较大的子节点
		}
		if arr[root] < arr[child] {
			arr[root], arr[child] = arr[child], arr[root]    //较大的子节点成为父节点
			root = child
		} else {
			break
		}
	}
}

/**
建议用这个
 */
func heapSort3(arr []int) {
	//从最后一个非叶子节点（也就是最左侧的那个非叶子结点）开始调整(len(s)/2-1)
	/**
	【1】 若根结点存在序号0处， i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2i+1和2i+2
	【2】 只要从n/2-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆
	比如现在有一个序列长度为15，序号0代表根节点则：


							0
						     /    
					            1      2
	 	                                 /       /   
	                                       3     4    5     6        那么我们就是从 6 = 15/2 - 1 开始构造堆
	                                     /     /   /    /  
	  		                   7    8 9 10  11 12 13  14


	 */
	for i := len(arr)/2 - 1; i >= 0; i-- { // 先从 6 = 15/2 - 1 处开始构造最大化堆结构，然后依次从 5, 4, 3处构建最大化堆结构
		heapAdjust3(arr, i, len(arr))
	}
	// 经过上面的for初始化堆结构，则其实在 这个堆的二叉树上其实数字已经是有序的了
	// 下面这个for是把最大的依次取出来，并重新调整堆结构
	for i := len(arr) - 1; i > 0; i-- {
		//将第一个和最后一个交换然后继续调整堆
		arr[0], arr[i] = arr[i], arr[0] // 如 14 和 0 置换后(这时候14位置是个最大值，被取出来)
		heapAdjust3(arr, 0, i)  // 把剩下的 0 -> n-2  的数由0位置(现在是14位置的值了)，再次往下和各个子节点的值对比
	}
}

func heapAdjust3 (arr []int, parent, length int) {
	var i int
	for 2 * parent + 1 < length { //确保是非叶子节点

		lchild := 2 * parent + 1 // 左儿子的下标
		rchild := lchild + 1	 // 右儿子的下标
		i = lchild
		//取出两个叶子节点中最大的一个
		if rchild < length && arr[lchild] < arr[rchild] {
			i = rchild
		}
		//如果最大的叶子节点大于父节点则交换，否则推出循环
		if arr[i] > arr[parent] { //这样纸就会把 最大的数依次上顶到根
			arr[parent], arr[i] = arr[i], arr[parent]
			parent = i // 然后设置该位置为新的父亲,因为该位置和根置换了，所以对该位子原先下属的各个子节点的值又需要重新比较了
			// 就这样一路比下去
			// 【其实这个只是针对上面除了6之外的非叶子节点才有用】
			//同时注意，如果进到这里面来了，比方说：说明叶子节点上的最大的那个值已经和6位置的更换了，
			// 然后当parant == 2 时 6又是2的其中一个非叶子节点
			// 则，在进入这里时就是把之前6为根时的子节点上的最大值置换根后的值再次置换到2上面，
			// 依次类推最终形成0索引是最大的数，这样的最大化堆结构
		} else {
			break
		}
	}
}


func heapAdjust4(arr []int, parent, length int) {
    
    i := parent
	for {
		left := 2 * parent + 1
		right := 2 * parent + 2

		if left < length && arr[left] > arr[i] {
			i = left
		}
		if right < length && arr[right] > arr[i] {
			i = right
		}

		if i != parent {
			arr[i], arr[parent] = arr[parent], arr[i]
			parent = i
		}else{
			break
		}
	}
}

【建议】：我个人建议用第三种写法比较简洁~

下面我们开汇总对比一下各个排序算法：

(注：该图是我网上扣得)。好了本low菜鸡码农对于7大排序算法的写法和分析就给大家抄到这里了。。谢谢！