Go 语言实现常见排序算法

插入排序，英文名（insertion sort）是一种简单且有效的比较排序算法。,思想：在每次迭代过程中算法随机地从输入序列中移除一个元素，并将改元素插入待排序序列的正确位置。重复该过程，直到所有输入元素都被选择一次，排序结束。,类比：抓牌,详见文章：跟着动画学 Go 数据结构之插入排序,冒泡排序是一种最简单的交换排序算法。,什么是交换？交换就是两两进行比较，如果不满足次序就可以交换位置。比如，我们想要从小到大排序，通过两个位置上的值两两比较，如果逆序就交换，使关键字大的记录像泡泡一样冒出来放在末尾。重复执行若干次冒泡排序，最终得到有序序列。,类比： 值较小的元素如同”气泡“一样逐渐漂浮到序列的顶端。,选择排序（selection sort）是一种原地（in-place)排序算法，适用于数据量较少的情况。由于选择操作是基于键值的且交换操作只在需要时才执行，所以选择排序长用于数值较大和键值较小的文件。,详见文章：跟着动画学Go数据结构之选择排序,堆排序是一种树形选择排序算法。堆排序的过程：,构建初始堆,在输出堆的顶层元素后，从上到下进行调整，将顶层元素与其左右子树的根节点进行比较，并将最小的元素交换到堆的顶部；然后不断调整直到叶子节点得到新的堆。,详见文章：跟着动画学Go数据结构之堆排序,详见文章：跟着动画学Go数据结构之希尔排序,利用递归与分治技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列。其中“归”代表的是递归的意思，即递归地将数组折半地分离为单个数组。,给定一组序列含n个元素，首先将每两个相邻的长度为1的子序列进行归并，得到n/2（向上取整）个长度为2或1的有序子序列，再将其两两归并，反复执行此过程，直到得到一个有序序列为止。,高效的排序算法，它采用 分而治之 的思想，把大的拆分为小的，小的再拆分为更小的。,其原理是：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前部分的所有记录均比后部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。