排序

基于比较的排序算法：冒泡，插入，选择，快排，归并

不基于比较的排序算法：桶，计数，基数

稳定性

待排序的序列中存在值相同的元素，经过排序后相同元素之间原有的先后顺序不变。

冒泡排序

image.png

优化：在每次冒泡操作时可以加入有序标志位，如果一次冒泡操作后没有进行过数据交换，则认为数据集为有序，可以提前退出冒泡排序

冒泡排序是原地排序，只需要常量级别的临时空间作为交换数据使用；

冒泡排序是稳定的排序算法，只要在两个相邻元素比较时，相同大小不进行交换就可以保证；

冒泡排序的时间复杂度：最好情况为有序数据集，仅需要一次冒泡操作，所以最好的时间复杂度为O(n)，最坏情况为倒序数据集，时间复杂度为O(n2)，平均时间复杂度为O(n2);

插入排序

插入排序是原地排序算法，不需要额外空间；

插入排序中，对于值相同的元素我们可以选择将后面出现的元素插入到前面出现的元素后面，可以保证插入排序为稳定排序；

插入排序时间复杂度：最好情况为有序数据集，时间复杂度为O(N)，如果数组是倒序的，则每次插入操作都相当于在数组的第一个位置插入新的数据，所以时间复杂度为O(n2)，平均时间复杂度为O(n2);

选择排序

选择排序是原地排序算法，不需要额外空间；

选择排序是不稳定的排序算法，在未排序数组中选出最小值并与未排序数组中第一个进行交换时会破坏相同数值的相对位置，例如5，8，5，2，9，在选择出2时第一个5会到第二个5的后面；

选择排序的时间复杂度在最好和最坏的情况下都是O(n2),因为每次选择出未排序部分的最小值时都需要对这一部分进行一次遍历，所以平均时间复杂度也是O(n2)；

为什么插入排序要比冒泡排序更受欢迎

冒泡排序涉及到元素之间的交换，需要3次赋值过程，而插入排序仅需要1次赋值过程，这两种排序的交换次数其实都是数据集的逆序度，所以交换次数是一样的，在交换次数相同的情况下，插入排序自然更具有优势。

image.png

代码实现（golang）

type Sort struct {
    data []int
}

func (s Sort) Change(i, j int) {
    if i >= len(s.data) || j >= len(s.data) {
        panic("wrong index!")
    }
    temp := s.data[i]
    s.data[i] = s.data[j]
    s.data[j] = temp
}

func (s Sort) Show() {
    fmt.Println(s.data)
}

func (s Sort) Bubble_sort() {
    length := len(s.data)
    sorted := true
    for i := length - 1; i >= 0; i-- {
        sorted = true
        for j := 0; j < i; j++ {
            if s.data[j] > s.data[j+1] {
                s.Change(j, j+1)
                sorted = false
            }
        }
        if sorted {
            return
        }
    }
}

func (s Sort) Choose_sort() {
    length := len(s.data)
    for i := 0; i < length-1; i++ {
        min := i
        for j := i + 1; j < length; j++ {
            if s.data[j] < s.data[min] {
                min = j
            }
        }
        s.Change(i, min)
    }
}

func (s Sort) Insert_sort() {
    for i := 1; i < len(s.data); i++ {
        now := s.data[i]
        j := i - 1
        for ; j >= 0; j-- {
            if s.data[j] > now {
                s.data[j+1] = s.data[j]
            } else {
                break
            }
        }
        s.data[j+1] = now
    }
}