Golang排序算法-冒泡排序优化之二

2018-09-11 23:05:04 george518 ...

前言

上一篇:http://www.haodaquan.com/139 介绍了冒泡排序算法的一种优化方法,那就是我们根据冒泡排序的特点,减少了内层循环次数,从而提高了算法的执行速度,那外层循环能否也可以减少一下循环次数呢?

分析

我们假设m个元素需要排序,当我们进行到i次排序的时候,如果发现内层循环的元素都是排好序的,那我们就可以提前结束外层循环。

怎么判断内层循环的元素是排好序呢,很简单,如果内层循环不交换元素位置了,说明排序已经排好了,此时可以提前结束内层循环。

于是,我们有了以下的想法:每次内层循环的时候,设置变量flag=true,即假设内层循环的元素是有序的,然后发现一旦有交换位置的操作,将flag设置为false,我们在内层循环之后判断flag是否为true,如果是,那就可以提前结束外层循环。

代码

我们有了以下的golang代码实现,并且将上一次优化的方法一起结合起来:

func Sort4(arr []int) []int {
    len := len(arr)
    if len < 2 {
        return arr
    }

    for i := 0; i < len-1; i++ {
        flag := true
        for j := 0; j < len-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j+1], arr[j] = arr[j], arr[j+1]
                flag = false
            }
        }
        if flag {
            break
        }
    }
    return arr
}

优缺点

这种算法,对于近乎有序的元素排序,效率是最高的。当然,如果反序的(从大到小排列)的元素排序,因为增加了一个判断,可能效率就不是那么高了。

github代码

下面是代码的实现以及测试代码:

https://github.com/george518/PPGo_algorithm/tree/master/sort/bubble

比较一下,看哪种算法时间最短,是不是和我们理论上的分析是一致,这里我就不贴测试结果了

相似文章


345708673

在路上

技术无止境,一直在路上。 年过而立,惴惴不安,愈加发奋,孜孜求学。