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

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

前言

上一篇:http://www.haodaquan.com/110 介绍了冒泡排序算法,如果单纯的背诵算法的代码,那将是一件枯燥的事情,算法的乐趣在于可以不断的优化,不断的提高算法的速度,这是一件很美妙又有挑战的事情。所以,这里我们试图改进冒泡排序,看是否有更优秀的解法。

分析

对于冒泡算法,目前能想到的优化思路主要有两点:

1、外层循环是否可以提前结束?
2、内层循环是否可以提前结束?

本小节从2开始思考,我们发现冒泡算法(从小到大排列)每次外层循环一遍,总能让较小的元素向前靠近,并且较大的元素总能向后靠近,并且,每次外层循环总能将一个较大的元素找到最合适的位置,又并且,外层第一次循环,可以把最大的元素排到末尾,第二次循环,总能将第二大的元素排到倒数第二的位置,……,依次类推。

代码

不难发现,假设有m个元素,在外层第n次循环的时候,其实后n个元素的位置是排序好的,因此,内层循环是可以提前结束的,也就是说,内层循环j,在区间[0,m-1-n)循环就可以了,基于这种思路:我们有以下golang代码实现冒牌排序:

func Sort2(arr []int) []int {
    len := len(arr)
    if len < 2 {
        return arr
    }
    for i := 0; i < len-1; i++ {
        //内层循环相邻进行比较
        // len-i 之后的数据是排序好的,因为每次外层循环都是把大数字向后排
        for j := 0; j < len-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j+1], arr[j] = arr[j], arr[j+1]
            }
            //fmt.Println(arr)
        }
    }
    return arr
}

当然,外层循环也可以节省一次,即len-2这个元素也不用判断了。
不难发现,这样我们省了不少的无用循环比较,效率肯定是提升的。下面是代码的实现以及测试代码:

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

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

相似文章


345708673

在路上

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