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

2018-09-12 10:06:57 george518 ...

前言

上一篇http://www.haodaquan.com/140 我们一起讨论了冒泡算法的第三种优化方式:即找出不需要排序的索引,作为内层循环的边界,这次讨论一个冒泡排序的优化变种:鸡尾酒排序法。

所谓鸡尾酒排序法:

鸡尾酒排序也就是定向冒泡排序, 鸡尾酒搅拌排序, 搅拌排序 (也可以视作选择排序的一种变形), 涟漪排序, 来回排序 or 快乐小时排序, 是冒泡排序的一种变形。此演算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。 —-from 百度百科

思路分析

冒泡排序有一个特点,每次外层循环一次,可以将待排序元素中最大值(或者最小值)交换的正确位置,基于这点,我们想能否在内层循环中,分为两部分,一部分从尾部开始,每次循环将待排序元素的最小值交换到合适位置,一部分从首部开始,每次排序将待排序元素的最大值交换到合适位置。相当于头尾一起开工,效率应该会高一些。

看一些百度百科的说法:

数组中的数字本是无规律的排放,先找到最小的数字,把他放到第一位,然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位,再找到第二大的数字放到倒数第二位。以此类推,直到完成排序。

Golang代码

给出以下golang的排序代码:

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

    for i := 0; i < len/2; i++ {
        for j := i; j < len-1-i; j++ {
            if arr[j] > arr[j+1] {
                arr[j+1], arr[j] = arr[j], arr[j+1]
            }
        }
        for j := len - i - 1; j > i; j-- {
            if arr[j] < arr[j-1] {
                arr[j-1], arr[j] = arr[j], arr[j-1]
            }
        }
    }
    return arr
}

优缺点:

这种排序比较稳定。

Github完整代码

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

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

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

相似文章