排序

• 冒泡排序
• 选择排序
• 插入排序
• 归并排序
• 快速排序
• 希尔排序
• 堆排序

冒泡排序

原理：对于一个数组里所有的元素进行两两比较，发生大于则变换数组下标则为升序排序，发生小于则变换数据下标的则为降序排序

package bubblesort

func Sort[T constraints.Ordered](buf []T) {
    for i := 0; i < len(buf)-1; i++ {
        flag := false
        for j := 1; j < len(buf)-i; j++ {
            if buf[j-1] > buf[j] {
                tmp := buf[j-1]
                buf[j-1] = buf[j]
                buf[j] = tmp
                flag = true
            }
        }
        if !flag {
            break
        }
    }
}

选择排序

一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

package choicesort

func Sort[T constraints.Ordered](buf []T) {
    for i := 0; i < len(buf)-1; i++ {
        min := i
        for j := i; j < len(buf); j++ {
            if buf[min] > buf[j] {
                min = j
            }
        }
        if min != i {
            tmp := buf[i]
            buf[i] = buf[min]
            buf[min] = tmp
        }
    }
}

插入排序

一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法

package insertsort

func Sort[T constraints.Ordered](buf []T) {
    for i := 1; i < len(buf); i++ {
        for j := i; j > 0; j-- {
            if buf[j] < buf[j-1] {
                tmp := buf[j-1]
                buf[j-1] = buf[j]
                buf[j] = tmp
            } else {
                break
            }
        }
    }
}

归并排序

建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

package mergesort

func Sort[T constraints.Ordered](buf []T) {
    tmp := make([]T, len(buf))
    merge_sort[T](buf, 0, len(buf)-1, tmp)
}

func merge_sort[T constraints.Ordered](a []T, first, last int, tmp []T) {
    if first < last {
        middle := (first + last) / 2
        merge_sort(a, first, middle, tmp)       //左半部分排好序
        merge_sort(a, middle+1, last, tmp)      //右半部分排好序
        mergeArray[T](a, first, middle, last, tmp) //合并左右部分
    }
}

func mergeArray[T constraints.Ordered](a []T, first, middle, end int, tmp []T) {
    i, m, j, n, k := first, middle, middle+1, end, 0
    for i <= m && j <= n {
        if a[i] <= a[j] {
            tmp[k] = a[i]
            k++
            i++
        } else {
            tmp[k] = a[j]
            k++
            j++
        }
    }
    for i <= m {
        tmp[k] = a[i]
        k++
        i++
    }
    for j <= n {
        tmp[k] = a[j]
        k++
        j++
    }

    for ii := 0; ii < k; ii++ {
        a[first+ii] = tmp[ii]
    }
}

快速排序

对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

package quicksort

func Sort[T constraints.Ordered](buf []T) {
    quick(buf, 0, len(buf)-1)
}

func quick[T constraints.Ordered](a []T, l, r int) {
    if l >= r {
        return
    }
    i, j, key := l, r, a[l] //选择第一个数为key
    for i < j {
        for i < j && a[j] > key { //从右向左找第一个小于key的值
            j--
        }
        if i < j {
            a[i] = a[j]
            i++
        }

        for i < j && a[i] < key { //从左向右找第一个大于key的值
            i++
        }
        if i < j {
            a[j] = a[i]
            j--
        }
    }
    a[i] = key
    quick(a, l, i-1)
    quick(a, i+1, r)
}

希尔排序

插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

package shellsort

func Sort[T constraints.Ordered](buf []T) {
    length := len(buf)
    incre := length
    for {
        incre /= 2
        for k := 0; k < incre; k++ {
            for i := k + incre; i < length; i += incre {
                for j := i; j > k; j -= incre {
                    if buf[j] < buf[j-incre] {
                        tmp := buf[j-incre]
                        buf[j-incre] = buf[j]
                        buf[j] = tmp
                    } else {
                        break
                    }
                }
            }
        }

        if incre == 1 {
            break
        }
    }
}

堆排序

利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

pachage heapsort

func Sort[T constraints.Ordered](buf []T) {
    n := len(buf)
    for i := (n - 1) / 2; i >= 0; i-- {
        minHeapFixdown[T](buf, i, n)
    }

    for i := n - 1; i > 0; i-- {
        temp := buf[0]
        buf[0] = buf[i]
        buf[i] = temp
        minHeapFixdown[T](buf, 0, i)
    }
}

func minHeapFixdown[T constraints.Ordered](a []T, i, n int) {
    j := 2*i+1
    for j < n {
        if j+1 < n && a[j+1] < a[j] {
            j++
        }

        if a[i] <= a[j] {
            break
        }

        temp := a[i]
        a[i] = a[j]
        a[j] = temp

        i = j
        j = 2*i + 1
    }
}