Skip to content

1A.md

Latest commit

 

History

History
86 lines (76 loc) · 4.79 KB

1A.md

File metadata and controls

86 lines (76 loc) · 4.79 KB

简单排序

　　很多时候我们希望得到有序数组，于是需要进行排序。虽说排序的核心操作只有比较和腾挪，可是玩法也有多种多样。

冒泡排序

　　冒泡排序以腾挪为切入点考虑问题，其思路非常简单：尽量往合适的位置挪，挪一步是一步，到挪不动的时候就好了。现实中，我们排队出操就经常这么干：看看旁边的小伙伴，不合适就换个位置，然后个子高的自然就到后面去了。而鱼缸里的气泡往上浮，石子往下沉，大概也是这种感觉。

func BubleSort[T cmp.Ordered](list []T) {
    for i := 0; i < len(list)-1; i++ {
        for j := len(list) - 1; j > i; j-- {
            if list[j] < list[j-1] {
                list[j], list[j-1] = list[j-1], list[j] //不合适就换位
}   }   }   }

　　冒泡排序看上去挺简洁，其实犯了目光短浅的大忌，于是比较次数和挪移次数都到了O(N2)。

　　不过它也并非一无是处。由于冒泡排序只会交换逆序的相邻元素，因此相等元素的前后次序不会被打乱，它是稳定排序。只是这种稳定性来得太贵，在数据规模稍大时很难体现价值。

选择排序

　　选择排序则是以比较为切入点考虑问题的，其思路也很简单：每次从剩下的中选出最合适的一个，最终排成一列。

func SelectSort[T cmp.Ordered](list []T) {
    for i := 0; i < len(list)-1; i++ {
        pos := i
        for j := i + 1; j < len(list); j++ {
            if list[j] < list[pos] {
                pos = j                                 //找到最佳
        }   }
        list[pos], list[i] = list[i], list[pos]
}   }

　　在一番精挑细选之后，选择排序把挪移次数限制在O(N)，可是比较次数却到了O(N2)，真可谓顾此失彼。

　　和冒泡排序不同，选择排序通常是不稳定的。因为它会把后面找到的“最优人选”直接换到前面，途中可能跨过若干个相等元素，从而打乱它们原本的先后关系。用它来处理只关心大小、不关心相对次序的数据还行，但若元素还带有额外信息，就要小心这种副作用。

插入排序

　　插入排序和选择排序一样把数据分作有序和无序两部分，不同的是后者是留了坑找人填，而前者是先来人后找坑。

func InsertSort[T cmp.Ordered](list []T) {
    for i := 1; i < len(list); i++ {
        key := list[i]
        a, b := 0, i
        for a < b {                                     //二分查找
            m := a + (b-a)/2
            if key < list[m] {
                b = m
            } else {
                a = m + 1
            }
        }
        for j := i; j > a; j-- {
            list[j] = list[j-1]                         //腾个空
        }
        list[a] = key                                   //挪进来
}   }

　　插入排序借助二分查找，可以让比较次数降到O(NlogN)，遗憾的是腾挪次数在最坏情况下还是O(N2)。不过，其平均的腾挪次数只有最坏情况下的一半，故实际应用中插入排序要比选择排序要快。

　　插入排序也是稳定的，因为新元素会插到“第一个严格大于它的元素”之前，而不会越过那些与自己相等的元素。于是，相等元素仍能保持原有顺序。这一点在后续归并排序、基数排序中还会再次出现，因为稳定性经常能被拿来作为更复杂算法的一块基础积木。

func SimpleSort[T cmp.Ordered](list []T) {      //InsertSort的变种
    if len(list) < 2 { return }
    for i := 1; i < len(list); i++ {
        key := list[i]
        if key < list[0] {
            for j := i; j > 0; j-- {
                list[j] = list[j-1]
            }
            list[0] = key
        } else {
            pos := i
            for ; list[pos-1] > key; pos-- {            //O(n^2)的比较
                list[pos] = list[pos-1]                 //和挪移一步到位
            }
            list[pos] = key
}   }   }

　　如果我们不拘泥于比较操作的阶，可以巧妙地将其与挪移整合起来，小规模下通常会更快。

　　这也是工程实现中常见的思路：理论上看，二分查找版插入排序减少了比较次数；但在小数组上，少写几层逻辑、让循环更紧凑，往往反而更快。所以附属代码里保留了 SimpleSort 这样的变种，后面的内省排序、归并排序也会在小区间退化到简单排序，而不是死守某一种“理论上更优”的方案。

小结

　　这三种排序算法反映了排序的三种重要思路，而后来的归并排序、快速排序以及堆排序将会把它们发扬光大。

目录　上一节　下一节