专栏首页Golang语言社区Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法

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)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Golang编程实现生成n个从a到b不重复随机数的方法

    package test import ( "fmt" "math/rand" "time" ) //生成若干个不重复的随机数 func...

    李海彬
  • 【Go 语言社区】关于select和channel数组的配合使用--转

    package main import ( "fmt" "math/rand" "reflect" "time" ) type ...

    李海彬
  • 原子读写性能简单测试

    代码如下: package main import ( "fmt" "sync/atomic" "time" ) func benc...

    李海彬
  • 旋转排序的数组

    ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

    羽翰尘
  • 【leetcode刷题】20T39-颜色分类

    https://leetcode-cn.com/problems/sort-color

    木又AI帮
  • 移动零

    一份执着✘
  • LeetCode 75. 颜色分类(JAVA)

    给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

    freesan44
  • 剑指Offer LeetCode 面试题57. 和为s的两个数字

    输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

    TrueDei
  • LeetCode 75. 颜色分类(双指针)

    给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

    Michael阿明
  • Find Peak Element

    Tyan

扫码关注云+社区

领取腾讯云代金券