Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法

本文实例讲述了Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法。分享给大家供大家参考。具体分析如下:

算法是程序的灵魂,而排序算法则是一种最基本的算法。排序算法有许多种,这里介绍4中排序算法:冒泡排序,选择排序,快速排序和插入排序,以从小到大为例。

一、冒泡排序

冒泡排序的原理是,对给定的数组进行多次遍历,每次均比较相邻的两个数,如果前一个比后一个大,则交换这两个数。经过第一次遍历之后,最大的数就在最右侧了;第二次遍历之后,第二大的数就在右数第二个位置了;以此类推。

//冒泡排序(排序10000个随机整数,用时约145ms)  
func bubbleSort(nums []int) {  
    for i := 0; i < len(nums); i++ {  
        for j := 1; j < len(nums)-i; j++ {  
            if nums[j] < nums[j-1] {  
                //交换  
                nums[j], nums[j-1] = nums[j-1], nums[j]  
            }  
        }  
    }  
}

二、选择排序

选择排序的原理是,对给定的数组进行多次遍历,每次均找出最大的一个值的索引。

//选择排序(排序10000个随机整数,用时约45ms)  
func selectSort(nums []int) {  
    length := len(nums)  
    for i := 0; i < length; i++ {  
        maxIndex := 0  
        //寻找最大的一个数,保存索引值  
        for j := 1; j < length-i; j++ {  
            if nums[j] > nums[maxIndex] {  
                maxIndex = j  
            }  
        }  
        nums[length-i-1], nums[maxIndex] = nums[maxIndex], nums[length-i-1]  
    }  
}

三、快速排序

快速排序的原理是,首先找到一个数pivot把数组‘平均'分成两组,使其中一组的所有数字均大于另一组中的数字,此时pivot在数组中的位置就是它正确的位置。然后,对这两组数组再次进行这种操作。

//快速排序(排序10000个随机整数,用时约0.9ms)  
func quickSort(nums []int) {  
    recursionSort(nums, 0, len(nums)-1)  
}  
 
func recursionSort(nums []int, left int, right int) {  
    if left < right {  
        pivot := partition(nums, left, right)  
        recursionSort(nums, left, pivot-1)  
        recursionSort(nums, pivot+1, right)  
    }  
}  
 
func partition(nums []int, left int, right int) int {  
    for left < right {  
        for left < right && nums[left] <= nums[right] {  
            right--  
        }  
        if left < right {  
            nums[left], nums[right] = nums[right], nums[left]  
            left++  
        }  
 
        for left < right && nums[left] <= nums[right] {  
            left++  
        }  
        if left < right {  
            nums[left], nums[right] = nums[right], nums[left]  
            right--  
        }  
    }  
    return left  
}

四、插入排序

插入排序的原理是,从第二个数开始向右侧遍历,每次均把该位置的元素移动至左侧,放在放在一个正确的位置(比左侧大,比右侧小)。

//插入排序(排序10000个整数,用时约30ms)  
func insertSort(nums []int) {  
    for i := 1; i < len(nums); i++ {  
        if nums[i] < nums[i-1] {  
            j := i - 1  
            temp := nums[i]  
            for j >= 0 && nums[j] > temp {  
                nums[j+1] = nums[j]  
                j--  
            }  
            nums[j+1] = temp  
        }  
    }  
}

通过多次测试可以发现,快速排序是效率最高的。

希望本文所述对大家的Go语言程序设计有所帮助。

原文发布于微信公众号 - Golang语言社区(Golangweb)

原文发表时间:2016-09-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏take time, save time

初级程序员面试不靠谱指南(三)

二、指针的好基友的& 1.&的意义。说&是指针的好基友其实不恰当,因为&这个符号在C/C++不止有一种含义,但是因为其经常会和指针一起出现在被问的问题列表上,所...

33890
来自专栏彭湖湾的编程世界

【JavaScript】 JS面向对象的模式与实践

参考书籍 《JavaScript高级语言程序设计》—— Nicholas C.Zakas 《你不知道的JavaScript》  —— KYLE SIMPSON ...

37660
来自专栏和蔼的张星的图像处理专栏

212. 空格替换先扩充,从后往前处理

设计一种方法,将一个字符串中的所有空格替换成 %20 。你可以假设该字符串有足够的空间来加入新的字符,且你得到的是“真实的”字符长度。 你的程序还需要返回被替...

9120
来自专栏大数据钻研

Java到底是不是一种纯面向对象语言?

Java——是否确实的 “纯面向对象”?让我们深入到Java的世界,试图来证实它。 在我刚开始学习 Java 的前面几年,我从书本里知道了 Java 是遵循 ...

300110
来自专栏青玉伏案

在Objective-C中浅谈面向对象

  接触面向对象也有一段时间了,当时是通过C++学习的OOP,后来又接触到了PHP和Java。每种OOP的语言在面向对象上或多或少都会有不同的地方,现在在学习O...

19260
来自专栏达摩兵的技术空间

js原型入门

本文主要是根据《head first javascript程序设计》摘抄学习而成,学习采用这本书主要是一位阿里大佬的建议,经过近期的学习阅读,发现确实比其他的j...

17410
来自专栏和蔼的张星的图像处理专栏

638. 字符同构哈希映射

给定两个字符串 s 和 t ,确定它们是否是同构的。 两个字符串是同构的如果 s 中的字符可以被替换得到 t。 所有出现的字符必须用另一个字符代替,同时保留...

7830
来自专栏追不上乌龟的兔子

为什么Python中的None is None is None == True

最近在StackOverflow上看到了一个问题,为什么Python中的None is None is None返回True,看到大家的讨论后对Python中的...

98270
来自专栏布尔

想起温习一下JS中的this apply call arguments

很多时候讲到语言入门,大家会认为就是要了解一下语言的语法、数据类型和常用函数。这一课对于所有的计算机专业的毕业生来说都可以自学,然而在最近的实践中(带了两个实习...

225100
来自专栏转载gongluck的CSDN博客

python笔记:#008#变量的命名

变量的命名 目标 标识符和关键字 变量的命名规则 0.1 标识符和关键字 1.1 标识符 标示符就是程序员定义的 变量名、函数名 名字 需要有 见名知义 的...

37840

扫码关注云+社区

领取腾讯云代金券