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

2018-09-11 23:59:38 george518 ...

前言

上一篇http://www.haodaquan.com/139 我们一起讨论了冒泡算法的第二种优化方式:提前结束外层循环。并且也加上了第一种优化方式,提前结束内层循环,但是,这种算法对于反序排列的元素(如:9,8,7,6,5,4,3,2,1)排序,效率低下。

分析

假设:有一个数组[7,1,2,3,4,6,8,9,10],我们发现,1234与8910其实是排好序的,能不能这两部分不参与循环呢?

问题的关键我们需要找到最后一个不需要排序的索引值(当然,不一定准确的索引值),这个索引值等于内层循环的交换的值中的最大值。

Golang代码

我们结合上一次优化的方法,给出以下golang的排序代码:

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

    k := len - 1
    lastIndex := 0

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

        k = lastIndex
    }
    return arr
}

优缺点:

这种算法对于近乎有序的元素排序,那是相当的酸爽,算法时间复杂度直接优化成O(1),相反,对于一个反序的元素组排序,算法复杂度会变成O(n^2),并且因为多了判断和赋值,时间会比其他冒泡算法效率会更低。

Github完整代码

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

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

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

相似文章


345708673

在路上

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