插入排序
将未排序的元素同已排序的元素从后往前比较，带排序元素:a,被比较元素：b,如果a<b则， swap(a,)
快速排序
每趟排序把基准值放到对的位置即左边的元素都比它小，右边的元素都比它大
冒泡排序
每一趟排序（包括多次两两比较和交换）找出余下的最大元素放在数组的最后，叫沉底排序更贴切。
选择排序
对未排序的元素找出最小的元素， 放到未排序数组的0号位置
希尔排序
插入排序的改进；插入排序比较移动的步长是1，希尔排序中改进该步长，从大缩小到1
堆排序
利用大顶堆的特点：根的值比左右子树都大
先构造大顶堆
交换堆的第一个元素和最后一个元素，使最大的元素放在数组的最后，再对前面的堆进行调整，重复该操作
归并排序
递归地合并两个有序数组 ,不断一分为二拆分数组,当左右数组长度为1时,开始排序并合并,之后对合并后的数组(已排序)继续归并排序,采用分而治之的思想
每一趟排序（包括多次两两比较和交换）找出余下的最大元素放在数组的最后，叫沉底排序更贴切
func swap(arr *[]int, i, j int) {
temp := (*arr)[i]
(*arr)[i] = (*arr)[j]
(*arr)[j] = temp
}
func bubble(nums []int) []int {
lgh := len(nums)
for i := 0; i < lgh-1; i++ {
for j := 0; j < lgh-i-1; j++ {
if nums[j] > nums[j+1] {
swap(&nums, j, j+1)
}
}
}
return nums
}
func selectSort(nums []int) []int{
lgh:=len(nums)
for i:=0;i<lgh-1;i++{
for j:=i+1;j<lgh;j++{
if nums[j] < nums[i]{
swap(&nums[j], &nums[i])
}
}
}
return nums
}
func swap(v1, v2 *int){
*v1, *v2 = *v2, *v1
}
每一趟排序把本次排序的元素往前插入到合适的位置
func insertSort(nums []int) []int {
lgh := len(nums)
for i:=1;i< lgh;i++{
for j:=i-1;j>=0;j--{
if nums[j+1] < nums[j]{
swap(&nums[j+1], &nums[j])
continue
}
//fmt.Println(nums)
break
}
}
return nums
}
func swap(v1 *int, v2 *int) {
*v1, *v2 = *v2, *v1
}
原理
希尔排序，就是按某个增量值对数据进行分组，每组单独排序好后，再缩小这个增量，然后按新增量对数据分组后每个分组再各自排序。最终增加缩小到1的时候，排序结束。所以希尔排序又叫缩小增量排序(Diminishing Increment Sort)
关于增量
最佳增量值的选择其实是个数学难题，有兴趣的可以自己搜下相关资料。
常用的增量有 n/2(这个又叫希尔增量)、n/3、2^k-1(hibbard增量)等，实际使用中稍微改版增量也可能使排序的性能产生很大的波动。
比如使用n/2的增量，就是初始增量就是 length/2 ,第二轮分组时就再除2：length/4，直至增量值变成1
流程
假设有个数组：[8,12,6,33,12,5,4,94,63,23,75,22,43,27,46]，以n/2为增量，那么整个排序流程就是这样的：
[golang] 数据结构-希尔排序
复杂度
不同增量复杂度不同。n/2时平均的时间复杂度为O(n^2)。
相较直接插入排序，希尔排序减少了比较和交换的次数，在中小规模的排序中，性能表现较好。但随着数据量增大，希尔排序与其他更好的排序算法（快排、堆排、并归等）仍有较大差距。
作者：holdtom
链接：https://www.imooc.com/article/271234
来源：慕课网基本思想
先将整个待排序的记录序列
分割成为若干子序列分别进行直接插入排序 待整个序列中的记录“基本有序”时 再对全体记录进行依次直接插入排序插入排序的改进；插入排序比较移动的步长是1，希尔排序中改进该步长，从大缩小到1
func shell(nums []int) []int {
lgh := len(nums)
// 这里就以n/2为增量
gap := lgh / 2
for gap > 0 {
insertSortStep(nums, gap)
// 缩小增量，直到 增量为1
gap = gap / 2
}
return nums
}
// 插入排序（步长）
func insertSortStep(nums []int, step int) {
for i := step; i < len(nums); i++ {
// 比较 不同分组中 相同位置 的值
for j := i; j < len(nums) && j >= step; j -= step {
if nums[j] < nums[j-step] {
swap(&nums[j], &nums[j-step])
}
}
}
}
func swap(v1 *int, v2 *int) {
*v1, *v2 = *v2, *v1
}
不断一分为二拆分数组,当左右数组长度为1时,开始排序并合并,之后对合并后的数组(已排序)继续归并排序,采用分而治之的思想
func mergeSort(nums []int) []int {
lgh := len(nums)
// 注意：结束递归的条件 是lgh<2,如果是0,1则无法结束地柜，因为数组长度为1的数组会一直被分成数组长度为0，数组长度为1
if lgh < 2 {
return nums
}
left := lgh / 2
return merge(mergeSort(nums[:left]), mergeSort(nums[left:]))
}
func merge(left []int, right []int) []int {
var nums []int
for (len(left) != 0) && (len(right) != 0) {
if left[0] < right[0] {
nums = append(nums, left[0])
left = left[1:]
} else {
nums = append(nums, right[0])
right = right[1:]
}
}
if len(right) != 0 {
nums = append(nums, right...)
}
if len(left) != 0 {
nums = append(nums, left...)
}
return nums
}
func main() {
test := []int{1, 23, 34, 3, 4, 5, 5, 6, 6, 77}
result := mergeSort(test)
fmt.Println(result)
}
func heapSort(nums []int) []int {
lens := len(nums)
buildHeap(nums,lens)
for i:=lens-1;i>=0;i-- {
swap(nums,0,i)
lens -= 1
heap(nums,0,lens)
}
return nums
}
func buildHeap(nums []int,lens int) {
for i := lens/2;i>=0;i-- {
heap(nums,i,lens)
}
fmt.Println(nums)
}
func heap(nums []int,i,lens int) {
left := 2*i + 1
right := 2*i + 2
largest := i
if left < lens && nums[left] > nums[largest] {
largest = left
}
if right < lens && nums[right] > nums[largest] {
largest = right
}
if largest != i {
swap(nums,largest,i)
heap(nums,largest,lens)
}
}
func swap(arr []int,m,n int) []int {
arr[m],arr[n] = arr[n],arr[m]
return arr
}